在SML中使用fold

Question

我现在正在尝试学习smlnj，但在使用fold函数时遇到了问题。

我要做的是编写一个函数select，它使用折叠模式，并接受一个函数和一个列表。它将把列表的头部放入函数中，以确定是否将该元素添加到列表中。这里有一个例子说明了我的意思。

          select (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10];
          val it = [2,4,6,8,10] : int list

所以，这就是我到目前为止所得到的。

          fun select f l = foldl (fn (x,y) => if (f(x)) then x else 0) 0 l;

这显然不能正常工作。它只返回10。我确定我需要使用op:：以某种方式使其工作，但我不能弄清楚。我的想法是它应该看起来像这样。

          fun select f l = foldl (fn (x,y) => if (f(x)) then op:: else []) [] l;

但这是行不通的。任何帮助都将不胜感激。谢谢!

Answer 1

你已经很接近了。唯一的问题是传递给fold的函数中的if/else用例。

请记住，在您的fn (x,y)中，x是您正在考虑的列表元素，而y是折叠列表其余部分的结果。如果f(x)失败，那么您希望从结果中排除x，因此只需传递y。如果f(x)成功，您希望在结果中包含x，因此返回y@[x]。

请注意，最好避免使用附加操作符(y@[x])，因为它是线性时间操作，而前置(x::y)是常量。当然，在这种情况下，用一个替换另一个将会向后构建列表。你也可以通过向后折叠来解决这个问题，比如使用foldr而不是foldl。

Answer 2

你要实现的东西已经存在了。它被称为filter。

- List.filter (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10];
val it = [2,4,6,8,10] : int list

您在第二个代码示例中的尝试非常接近。我可能会指出几个问题：

• op::是一个运算符，它是一个函数。你可能不想返回一个函数。相反，您可能希望使用运算符从head元素和列表的其余部分创建列表，如下所示：x :: y
• In在else的情况下，您当前返回的是一个空列表，并丢弃y中累积的所有内容。您可能并不想这样做。
• 考虑最适合您的输出

的是左折叠还是右折叠