SML foldl函數 - 在條件列表中添加

Question

我有一門關於函數式編程的大學課程，我使用SML。作爲考試的準備，我正在研究一些沒有解決方案的老考試。

一個唯一的問題我真的有問題，是使用foldl以下問題：

考慮程序框架：樂趣 addGtķXS = List.foldl（...）... XS ; 填充兩個缺件 （用點表示），以便 addGt k xs是xs中那些元素的總和，它們大於 k。例如，addGt 4 - [1,5，2，7， 4,8] = 5 + 7 + 8 = 20

我相信這是很容易的，但我有一個非常很難理解的foldl和foldr功能。

我現在有如下（這似乎如果你問我的編譯器是非常錯誤的！）：

fun addGt(k,xs) = List.foldl (fn x => if x > k then op+ else 0) 0 xs; 

我真的很感激一些幫助這個問題，也許在很短的評論，其會在foldl和foldr功能上投下一些光！

非常感謝。

Answer 1

一個解決方案，我剛纔雖然是以下幾點：

fun addGt(k, xs) = List.foldl (fn (x, y) => if x >= 5 then x + y else y) 0 xs; 

我來解釋一下。首先，檢查List.foldl函數的類型，它是：

('a * 'b -> 'b) -> 'b -> 'a list -> 'b 

所以List.foldl是curried函數，它作爲第一個參數('a * 'b -> 'b)類型的其他功能。您使用了(fn x => if x > k then op+ else 0)，其型號爲int -> int。您應該提供List.foldl函數，該函數需要int * int類型的元組並返回int，所以如下所示：(fn (x, y) => do stuff)。這就是爲什麼你的代碼沒有編譯的原因，你在foldl中傳遞了錯誤的函數類型。

現在，你能想到的foldl這樣：

foldl f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_n, f(x_(n - 1), ..., f(x2, f(x1, b)) ...))其中f是('a * 'b -> 'b)類型的函數，b是'b類型和列表[x_1, x_2, ..., x_(n - 1), x_n]的東西'a list類型。

而對於foldr類似，你可以認爲它是這樣的：

foldr f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_1, f(x_2, ..., f(x_(n - 1), f(x_ n, b))

Answer 2

如果你的列表，ls = [x1, x2, ..., xn]上調用foldl f s ls，那麼你得到的結果是：

f(xn, ... f(x2, f(x1, s))) 

也就是說它首先找到

a1 = f(x1, s) 

然後

a2 = f(x2, a1) 

等等，直到它在列表中。

完成後，它將返回an。

你可以認爲a - 值作爲是一種蓄電池的，那就是，ai是結果，因爲這將是如果清單僅[x1, x2, ..., xi]（或者更確切地說，該列表的第i個元素） 。

你的功能通常有以下形式：

fn (x, a) => ... 

什麼，那麼你需要做的是想：好吧，如果我有在列表中，x(i+1)下一個元素，並將其值ai，這是結果爲列表[x1, x2, ..., xi]，我需要做些什麼才能找到a(i+1)的值，這是列表[x1, x2, ..., xi, x(i+1)]的結果。

s可以被認爲是賦予空列表的值。

foldr以同樣的方式工作，只有你從列表的後面開始而不是從前面開始。