0

我最近开始学习 ocaml 并且无法解决问题。

目标：

给定一个整数列表和一个函数，根据给定函数将整数排序为等价类，作为另一个列表中的列表。等价列表的顺序必须与原始列表中给出的顺序相同。

更新：我决定尝试让它在没有库功能的情况下工作。

到目前为止，这是我的代码。它编译但不运行。任何有关语法的帮助将不胜感激。

let buckets f lst =
  let rec helpfunction f lst newlist = 
     match lst with
      | [] ->newlist
      | h::t -> match newlist with
             | [] -> helpfunction f lst [h]@newlist
             | [a]::_ -> if f h a 
                  then helpfunction f t [a::h]@newlist
                  else helpfunction f t ([a]::[h]@mylist

重要提示：这是一个家庭作业问题，所以我不是在寻找为我粘贴的代码。我试图在我的家中通过它对整体思维过程和语法有所帮助。一旦我得到它的工作，我会努力使它更有效率

4

2 回答 2

0

好吧，让我们尝试在不实际执行的情况下解决任务:)

粗略地说，该算法如下所示：

  1. x从源列表中取整数

  2. 如果列表的目标列表（每个列表都包含相同等价类的整数）包含适当等价类的列表，则添加x到此列表

  3. 否则，创建一个包含单个值 ( [x]) 的新等价类列表并将其添加到目标列表中

  4. 对目标列表中的其他整数重复 1-3。

(1)、(3) 和 (4) 似乎很容易实现。

挑战在于如何实施（2）以及如何有效地做到这一点:)

“目标列表包含……的列表”可以改写为“lst在目标列表中存在一个列表，例如……”——这给了我们一个强有力的提示，List.exists可以在这里以某种方式使用。测试什么也或多或少清楚：同一个等价类列表的每个成员在定义上都是等价的，所以我们可以只取头部并与xusing进行比较p。

问题是如何将整数添加到另一个列表中的列表中。列表是不可变的，所以我们不能把它放在那里......但是我们可以获取目标列表并进行转换，或者将其折叠到另一个列表中。我打赌你得到了提示：List.fold_left是另一个难题。

因此，总结所有这些我们可以得出以下“更精确”的算法

  1. 从空的目标列表开始res

  2. x从源列表中取一个整数l

  3. 用于List.exists检查是否有一个列表lst，res例如它的头部h p x h = true

  4. 如果是，则用于List.fold_left将当前res转换为新的，lst替换为x::lst和所有其他等价类列表按原样复制

  5. 如果否，则引入一个新的等价类（添加[x]到res）

  6. 对源列表中的下一个整数重复 2-5，直到它为空。

（几乎）字面上遵循该算法的实现相对简单。但它不会很有效，因为exists并且fold会在同一个列表上迭代两次，做同样的检查。通过一些调整，应该可以在一次运行中完成它，但是这个低效率的应该足以作为起点......

于 2020-02-19T13:40:17.720 回答
0

您要尝试的是获取输入中的每个元素，然后将其插入列表结果列表中的某个位置。让我提出一个不同的方法。

你从一个“输入列表”和一个空的“你构建的结果列表”开始。

如果输入为空，则您的结果是完整的，您将其返回。

否则将输入分成头部和尾部（模式匹配已经这样做了）。接下来将输入列表划分为与头等价的项目和不等价的项目。使用第二个列表作为新输入和 (first list :: result) 作为新结果进行递归。

于 2020-02-19T14:04:38.983 回答