在SML中使用摺疊

Question

我正試圖學習smlnj，並且在摺疊功能時遇到問題。

我想要做的是編寫一個函數，選擇，使用摺疊模式，並採用一個函數和一個列表。它會將列表的頭部放入函數中，以確定它是否將該元素添加到列表中。這是我的意思的一個例子。

  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::是運營商，這是一個功能。你可能不想返回一個函數。相反，您可能想要使用操作員從頭元素和列表的其餘部分創建列表，如下所示：x :: y

• 在其他情況下，您當前正在返回一個空列表，並將任何積累在y。你可能不想這樣做。

• 想想左倍或對摺是否是最適合你的輸出