The Author Online Book Forums are Moving

The Author Online Book Forums will soon redirect to Manning's liveBook and liveVideo. All book forum content will migrate to liveBook's discussion forum and all video forum content will migrate to liveVideo. Log in to liveBook or liveVideo with your Manning credentials to join the discussion!

Thank you for your engagement in the AoF over the years! We look forward to offering you a more enhanced forum experience.

steshaw (13) [Avatar] Offline
#1
The book "injects" the initial value (acc) first into the left subtree, then uses that result as the acc for the right subtree, and finally on the element at the node. AFAIK, the usual implementation evaluates the right subtree, the element at the node, and then the left subtree.

The code demonstrates the difference:

data Tree elem
  = Empty
  | Node (Tree elem) elem (Tree elem)

Eq elem => Eq (Tree elem) where
  (==) Empty Empty = True
  (==) (Node l e r) (Node l' e' r') = l == l' && e == e' && r == r'
  (==) _ _ = False

Foldable Tree where
  foldr func init Empty = init
  foldr func init (Node l e r) = let left  = foldr func init l
                                     right = foldr func left r
                                 in  func e right

[alt] Foldable Tree where
  foldr func init Empty = init
  foldr func init (Node l e r) = let right = foldr func init r
                                 in  foldr func (func e right) l

t : Tree Integer
t = Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)

-- [2,3,1]
ta : List Integer
ta = foldr (::) [] t

-- [1,2,3]
ta' : List Integer
ta' = foldr @{alt} (::) [] t