Geek asks and answers

Haskell fold operation on a tree

data Tree a = Tree a [Tree a]

Please note that we do not allow empty trees and that the leaf is a tree with an empty list of subtrees.

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

Given the above information, I don’t understand how the tree bending function returns the result by recursively applying the addition operation to subtrees, then applying the function to the label in the root and the results returned from the subtrees.

I also don't understand how the Fold tree function takes only one argument instead of 2 when it is passed as an argument to the map function, and it still compiles and works correctly.

For example, the tree size function below counts the nodes of the tree.

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

So, run the treeSize tree , where it tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]sets the tree size to 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

.

+5
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

... :

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, - .

+9

, ... : " , , ".:- : 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 , . treeFold , , , x. . .

+1

More articles:


All Articles