樹上的haskell摺疊操作

Question

data Tree a = Tree a [Tree a] 

請注意，我們不允許空樹，並且葉子是具有空子樹列表的樹。

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

鑑於上述信息，我不明白是怎麼樹摺疊功能 通過遞歸地施加摺疊操作的子樹，然後在根和結果應用的功能標籤返回結果從子樹返回。

我也不明白樹摺疊函數只有一個參數而不是2，當它作爲參數傳遞給map函數，它仍然編譯和正常運行。

例如，樹大小函數下面，計數樹的節點。

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

所以運行的TreeSize樹其中tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]給出了樹的大小爲4

在樹尺寸功能以上，樹摺疊功能也被傳遞一個參數，而不是兩個。另外，傳遞給樹摺疊函數的x在任何地方都沒有被使用，所以你爲什麼需要它。刪除它會導致程序無法編譯，並提供以下錯誤消息。

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

任何幫助將不勝感激。

Answer 1

第一個問題有點棘手，因爲這是遞歸的東西......正如老師所說：「要理解遞歸，你必須學習，遞歸如何工作」。 :-P 一個小建議：嘗試通過應用treeFold與一棵樹或一棵樹與一棵樹內，並由您自己（在紙上或其他）評估它。我認爲，那麼你可以感覺到發生了什麼......（當然，使用一個簡單的函數作爲treeFold的參數;就像你的treeSize使用的那樣）。

treeFold僅得到一個在地圖的身體參數，因爲map需要從a->b功能，並treeFold有型(a -> [b] -> b) -> Tree a -> b.，所以如果你將它傳遞2個參數，將傳遞給map只有一個值，這導致失敗。 （+）需要兩個參數，如果你寫map (+1) [1,2,3]，你會得到[2,3,4] ，因爲（+1）應用於列表中的每個元素（和（+1）顯然需要多一個參數，您treeFold f以上）

你的榜樣的TreeSize： 這是不對的，當你說，它只得到一個參數你可以寫

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

，而不是你定義上面 的x不是。因爲用於計數是沒用的。但是，treeFoldn eeds有一個函數，它有兩個參數，所以你給它的x。這是唯一的原因。您可以傳遞任何其他值。

Answer 2

未使用變

首先，明確標記變量爲未使用的是_替換變量的方式。所以，你真的想：

treeFold (\_ ys -> 1 + sum ys) 

，因爲你寫你有一個編譯器錯誤：

treeFold (\ys -> 1 + sum ys) 

...這是不一樣的東西。

褶皺

其次，我會用手上的例子樹評估treeSize所以你可以看到，有沒有神奇的事情：

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

然而，有一個簡單的方法來記住如何treeFold作品。它所做的就是用您提供的函數替換每個Tree構造函數。

所以，如果您有：

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

...你申請treeFold f到，它會評估爲：

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum只是特殊情況下f = (\_ ys -> 1 + sum ys)：

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

Currying

最後一點是如何在Haskell中進行咖啡的工作。當你定義像函數：

foo x y = x + y 

...的編譯器實際上是desugars兩個嵌套函數：

foo = \x -> (\y -> x + y) 

這就是爲什麼你可以部分應用功能，在Haskell只是一個參數。當你寫foo 1，將其轉換爲：

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

換句話說，它返回一個參數的一個新功能。

在Haskell中，所有函數只需要一個參數，我們通過返回新函數來模擬多個參數的函數。這種技術被稱爲「咖喱」。

如果你喜歡更傳統的主流語言的多參數的方法，你可以通過讓函數接受一個元組參數模擬它：

f (x, y) = x + y 

然而，這不是真正地道的Haskell，並贏得了」不會給你任何性能改善。