Tree.hs

module Tree where

data Tree a = Leaf a
            | Node (Tree a) (Tree a)
            deriving Show

type WithCounter a = Int -> (a, Int)

numberOfLeaves :: Tree a -> Integer
numberOfLeaves (Leaf _)   = 1
numberOfLeaves (Node l r) = numberOfLeaves l + numberOfLeaves r

relabel :: Tree a -> WithCounter (Tree a)
relabel (Leaf x)   = \i -> (Leaf x, i+1)
relabel (Node l r) = relabel l `next` \l' ->
                     relabel r `next` \r' ->
                     pure' (Node l' r')

next :: WithCounter a -> (a -> WithCounter b) -> WithCounter b
f `next` g = \i -> let (r, i') = f i
                   in  g r i'

pure' :: a -> WithCounter a
pure' x = \i -> (x, i)