1

我对函数式编程完全陌生；这是 SML 的家庭作业。

我有一个整数列表，我正在尝试获取有序对的列表，其中该对的第二个条目是第一个条目出现在初始列表中的次数。

例如：

[2,3,3,5] => [(2,1),(3,2),(5,1)]

我不希望有人实现这个，而是让我知道我正在寻找什么样的高阶函数，和/或正确方向的指针。同样，对函数式编程来说是全新的，对 SML 语言来说更是新的。

我最初的想法是我想使用map，但我不知道如何跟踪或合并相似的项目。我只能成功地将每个项目变成一个有序对，第二个条目等于 1 ......非常没用。

4

2 回答 2

3

因此，为此您可能需要使用折叠，例如foldl.

一般来说，在决定是使用map还是折叠时（这里我将 fold 表示为foldl或foldr），您可以使用以下经验法则：

如果您想要的列表与您进入的列表具有完全相同数量的元素，您可能需要一个map. 否则，你会想要弃牌。

推理如下：对于列表中的每个元素，map在输出中生成一个转换后的元素。另一方面，折叠更通用，可以做任何你想做的事情。（而且您确实可以map使用折叠来实现。这并不意味着您当然不需要使事情变得不必要地复杂）

为了完整起见，让我简要解释一下折叠的工作原理。折叠遍历列表（foldl从左到右foldr，因此是名称），一次在累加器中建立一个结果。

让我们看一个例子：

foldl (fn (e, a) => e + a) 0 [5, 3, 7, 10]

这e是我们当前正在使用的元素，以及a累加器变量（即当前结果）。我们从 开始a = 0，因为我们指定0为起始值。

|  e | a  | new a
-------------------------
| 5  | 0  |  5 +  0 = 5
| 3  | 5  |  3 +  5 = 8
| 7  | 8  |  7 +  8 = 15
| 10 | 15 | 10 + 15 = 25
|    | 25 |

这给了我们一个 final a，25我们看到该函数总结了列表中的元素。请注意，在任何迭代中， 的值a是迄今为止列表中元素的总和，以及我们如何在每个步骤中扩展此列表以包含更多元素。

这是我推荐的解决此问题的方法。

  • 考虑a应该是什么基础值。[]（与getting as input的结果相同。）
  • 然后考虑如何从较小的列表中获取结果，并将其扩展为包含另一个元素。
于 2013-06-28T19:40:35.137 回答
0

除了使用折叠之外，这里还有一个提示：由于[(2,1),(3,2),(5,1)]是最终结果，折叠使用的累加函数的返回值可以是这种类型；(int * int) list. 然后，您将问题简化为

foldl (fn (elem, acc) => ...) [] xs

应该在哪里f插入elem，例如5，到accum，例如[(2,1),(3,2)]。f可以被认为是一个插入函数，或者等效地调用这样一个插入函数，只要它产生类似的东西[(2,1),(3,2),(5,1)]（即，查看已经找到的元素，如果找到则增加它，或者如果没有找到则将其插入计数为 1。

于 2013-07-08T11:21:13.807 回答