functional-programming - 如何组合相等的序列元素(函数式编程)？

Question

我想编写一个函数，它接受序列 <1,1,2,2,3> 并返回具有相同元素的序列，这些元素分组为 <<1,1>、<2,2>、<3>>。

我使用的是序列，而不是列表，但有些功能是相似的。我正在考虑使用的一些功能是 map、reduce、tabulate、filter、append 等。

Reduce 接受一个关联函数并返回被该运算符“减少”的序列。因此，减少 op+ 0 <1,2,3> = 6。

我的第一个想法是使用 map 将序列提高一个级别。所以，<1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>。

然后，我在考虑使用 reduce，我在其中创建了一个函数，该函数接受成对的元素，例如 (x,y)。如果 x == y，那么我返回 else，我什么都不做。但是......这并不完全有效，因为函数在两种情况下都必须返回相同类型的东西。

有人可以给我一些关于正确路径的提示，比如我可以使用哪些高阶函数？我正在使用 SML，但我不要求任何人给我一个完整的答案，所以任何高级提示将不胜感激(老实说，在任何功能语言中)

Answer 1

我猜你指的reduce函数和F#中的fold函数是一样的:

val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State

这需要一个值列表，以及一个初始状态和一个在遍历列表值时转换状态的函数。

你可以在一个折叠中做你想做的事。您需要将一些东西保存在该州。假设您位于 1,1,2,2,3 中间的某个位置(例如，在第二个 2 上)。现在您需要:

• 您当前正在收集的值 - 即 2
• 包含当前收集值的值列表 - 即 [2](序列中的第一个 2)
• 您之前收集的值列表的列表 - 即 [ [1; 1] ].

您将从初始状态 -1, [], [] 开始(使用 -1 作为一些不会出现在您的输入中的值)。然后，您需要编写根据当前值转换状态的函数。这需要处理几种情况:

• 当值与您一直收集的值不相同时，您需要将收集的值列表添加到列表列表中(除非它是空的)
• 当值相同时，需要将其添加到现在收集的值列表中，然后继续

希望这能为您提供足够的信息来弄清楚如何执行此操作，而无需实际透露完整的源代码!