尾遞歸在樹上

我有一個數據結構，尾遞歸在樹上

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

，我想寫一些爲了遍歷這棵樹的功能。它沒有關係，所以它可能是treefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b。我可以寫這個函數是這樣的：

fun treefold f acc1 Leaf = acc1 
    | treefold f acc1 (Branch (left, a, right)) = 
    let val acc2 = treefold acc1 left 
     val acc3 = f (a, acc2) 
     val acc4 = treefold acc3 right 
    in acc4 end

但因爲我不可避免地在最後一種情況下兩個分支，這不是一個尾遞歸函數。

是否有可能創建一個，即允許類型簽名被允許擴展以及花費多少？我也懷疑它是否值得嘗試;也就是說，它在實踐中是否會帶來速度上的好處？

來源

2013-09-28 Simon Shine

看到這個：http://stackoverflow.com/questions/9323036/tail-遞歸函數查找樹的深度 – david

可以使用延續傳遞風格實現尾遞歸treefold：

fun treefold1 f Leaf acc k = k acc 
    | treefold1 f (Branch (left, a, right)) acc k = 
    treefold1 f left acc (fn x => treefold1 f right (f(a, x)) k) 

fun treefold f t b = treefold1 f t b (fn x => x)

例如：

fun sumtree t = treefold op+ t 0 

val t1 = Branch (Branch(Leaf, 1, Leaf), 2, Branch (Leaf, 3, Leaf)) 

val n = sumtree t1

結果如預期N = 6。

來源

2013-09-29 13:45:28 seanmcl

像@seanmcl寫道，將函數轉換爲尾遞歸的系統方法是使用continuation-passing樣式。

之後，你可能希望你的具體化和延續使用了更具體的數據類型，例如像列表：

fun treefoldL f init tree = 
    let fun loop Leaf acc [] = acc 
      | loop Leaf acc ((x, right) :: stack) = 
      loop right (f(x,acc)) stack 
      | loop (Branch (left, x, right)) acc stack = 
      loop left acc ((x, right) :: stack) 
    in loop tree init [] end

來源

2013-10-06 19:43:23 kfl

謝謝，肯。我最主要的問題是因爲我變得急躁潛伏在其他人問SML問題，並認爲我會問一個人們可能想回答的問題。 :)（H＆R的新F＃書中似乎增加了有關延續的新章節。） –

尾遞歸在樹上

回答

相關問題