BFS on Trees.md

BFS on Trees.md

BFS on Trees

Implement bread-first-search, bfs, on trees of type a

data Tree a = Empty | Node a (Tree a) (Tree a) 
							 deriving Show
bfs :: Tree a -> [a]
bfs x = traverse [x]
traverse :: [Tree a] -> [a]  
traverse [] = []
traverse ts = rootlabels ++ traverse children
  where  rootlabels = [ x | Node ...] 
            –both need list comprehension & pattern matching
            children = [... | ... ]   

Example:

t = Node 1 (Node 10 Empty (Node 16 Empty Empty))
           (Node 17 
                    (Node 14 Empty Empty)
                    (Node 20 Empty Empty)) 
bfs t = [1, 10, 17, 16, 14, 20]

bfs.hs

data Tree a = Empty 
            | Node a (Tree a) (Tree a) 
                deriving Show
                
bfs :: Tree a -> [a]
bfs x = traverse' [x]

-- use traverse will trigger Ambiguous occurrence traverse, so when execute need change to traverse'
traverse' :: [Tree a] -> [a]  
traverse' [] = []
traverse' ts = rootlabels ++ traverse' children
    where rootlabels = [ x | Node x _ _ <- ts] 
          children = concat [ [y] ++ [z] | Node _ y z <- ts ]
              
main =  do
        print $ bfs (Node 1 (Node 10 Empty (Node 16 Empty Empty)) (Node 17 (Node 14 Empty Empty) (Node 20 Empty Empty)))