Trees DFS/BFS

trees-dfs-bfs.hs

-- https://web.cecs.pdx.edu/~mpj/pubs/springschool95.pdf
-- https://patternsinfp.wordpress.com/2015/03/05/breadth-first-traversal/
-- https://researchspace.auckland.ac.nz/handle/2292/3470

class Tree t where
  subtrees :: t -> [t]

data BinTree a = Leaf a
               | BinTree a :^: BinTree a

data STree a = Empty
             | Split a (STree a) (STree a)

data RoseTree a = Rose a [RoseTree a]
                  deriving Show

instance Tree (BinTree a) where
  subtrees (Leaf _) = []
  subtrees (l :^: r) = [l, r]

instance Tree (STree a) where
  subtrees Empty = []
  subtrees (Split _ l r) = [l, r]

instance Tree (RoseTree a) where
  subtrees (Rose _ ts) = ts

dfs :: Tree t => t -> [t]
dfs t = t : concat (map dfs (subtrees t))

bfs :: Tree t => t -> [t]
bfs = concat . lev
 where lev t = [t] : foldr cat [] (map lev (subtrees t))
       cat   = combine (++)

combine :: (a -> a -> a) -> ([a] -> [a] -> [a])
combine f (x:xs) (y:ys) = f x y : combine f xs ys
combine f []     ys     = ys
combine f xs     []     = xs

find :: Tree t => (t -> Bool) -> t -> t
find p = head . filter p . dfs

--      5
--     / \
--    3   7
--   / \
--  1   4

rt = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]

p :: Int -> RoseTree Int -> Bool
p n (Rose x _) = x == n

rdfs n = head . filter (p n) . dfs $ rt

rbfs n = head . filter (p n) . bfs $ rt

till :: (a -> Bool) -> [a] -> [a]
till p [] = []
till p (x:xs) | p x       = [x]
              | otherwise = x:(till p xs)

label :: RoseTree a -> a
label (Rose a _) = a

rbfs' p = (till p) . (map label) . bfs

t = rbfs' (==1) rt