需要幫助瞭解連續函數

Question

這是從教學的例子來說明CPS和尾遞歸：

fun sum [] k = k 0 
    | sum (x::xs) k = sum xs (fn y=>k(x+y)); 

我理解如何匿名函數fn y=>k(x+y)將正確總結輸入列表中的元素問題。

據我所知，匿名函數意味着一個帶有一個參數y的新函數，其中函數體調用原函數k，參數爲y+x。

如果我調用sum [1,2,3,4,5] (fn x=>x);我得到15.如果我有sum [1,2,3,4,5] (fn x=>3x);答案是45。sum功能的用戶，因此必須先了解sum確切的血淋淋的細節，因爲只有中k適當的版本將產生總和給定列表。以這種方式提供用戶提供的功能的真實目的是什麼？

如果我是sum函數的作者，我無法控制用戶通過k的內容。換句話說，我怎麼甚至指定這個函數會精確地做什麼？

Answer 1

我在理解如何正確地總結輸入列表的元素時遇到問題。

嘗試，用手評估你的函數：

sum [1,2,3] id 
sum [2,3] (fn y1=>id(1+y1)) 
sum [3] (fn y2=>(fn y1=>id(1+y1))(2+y2)) 
sum [] (fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 
(fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 0 
(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+0) 
(fn y2=>(fn y1=>id(1+y1))(2+y2)) 3 
(fn y1=>id(1+y1))(2+3) 
(fn y1=>id(1+y1)) 5 
id(1+5) 
id(6) 
6 

所以你可以看到，這個函數建立起匿名函數在堆內存鏈，最終相互調用。一個正常的遞歸函數會使用等價的堆棧空間。

sum函數的用戶因此必須首先理解sum的確切血統細節，因爲只有適當版本的k將產生給定列表的總和。以這種方式提供用戶提供的功能的真實目的是什麼？

正如Bergi寫道的，用戶不需要了解sum函數的工作方式，只需要繼續作爲參數並在其基本情況下解決它。正如Bergi也寫到的那樣，它不必評估其基本情況下的k值。這個函數另一種方法是：

fun sum [] k = k 
    | sum (x::xs) k = sum xs (fn y=>k(x+y)); 

一個應用在這裏，和對於用一個回調作爲參數和返回值輸出求和函數的理由，就是你可以懶洋洋鏈職能一起這樣。例如，通過上面的函數，您可以對列表進行求和;

fun sumMany [] k = k 
    | sumMany (xs::xss) k = sumMany xss (sum xs k) 

，你可能會評估它像

val result = sumMany [[1,2,3],[4,5,6],[7,8,9]] (fn x=>x) 0 

Answer 2

總和功能的用戶，因此必須先了解sum僅作爲k合適的版本準確的血淋淋的細節會產生定列表的總和。

不可以。與往常一樣，閱讀文檔應該足夠了，不需要查看實現細節。你的k是給出清單的確切總和 - 這就是所有重要的。你應該明白k就像output parameter（儘管沒有突變）;它基本上是一個callback

如果我SUM函數的作家，我無法控制哪些用戶會通過在k。換句話說，我怎麼甚至指定這個函數會精確地做什麼？

您不需要關心用戶通過什麼。您只需記錄該功能的功能：使用提供的xs列表的總和調用提供的k。這個回報值並不重要。

以這種方式提供用戶提供的功能的真實目的是什麼？

如果出現極端情況，您不需要返回continuation-passing style中的任何值 - 只需將它傳遞給回調即可。這使得調用堆棧變得多餘。從另一個角度來看，每個函數都會在尾部調用中結束，可以優化而不是返回。