tree.hs

-- Searching an n'ary tree returning the char or null
-- Benjamin Blundell
-- [email protected]
--
-- https://www.reddit.com/r/haskellquestions/comments/3han54/how_do_you_flatten_a_nested_list_of_arbitrary/

module Main where

data Tree a = Leaf a | Branch a [Tree a] deriving (Show)

-- cheating by flattening into a list and then searching
-- I couldn't figure out how best to return the char OR
-- None, so I let a builtin function do that :/

-- The many part of this is weird. We use map to apply
-- find to every item in the list, but for some reason
-- map returns [[a]] not [a] so we need to 'unwrap' it
-- with concat $. The dollar is a way of avoidng ()s.
-- could also use concatMap?
flatten :: Tree a -> [a] 
flatten (Branch a (xs)) = a : concat (map flatten xs)
flatten (Leaf a) = [a]

-- Apparently there is no such thing a Null value
-- so we make a monad (yay!) that deals with that
-- https://stackoverflow.com/questions/35198674/can-i-declare-a-null-value-in-haskell
-- data Maybe a
--    = Just a
--    | Nothing
--
--    Or I could just try a Bool?

-- Because we are using 'a' and not 'char' we have to add an Eq clause
find :: Eq a => a -> [a] -> Maybe a
find x (h:t) = if x == h then Just h else find x t
find x [] = Nothing

main :: IO ()
main  =
   do
      putStrLn "Print Tree" 
      let tree1 = Branch 'a' [Branch 'b' [ Leaf 'd', Leaf 'e', Leaf 'f' ], Branch 'c' [ Branch 'g' [ Leaf 'h']]]
      print tree1

      putStrLn "Find letter 'g'"
      --- For some reason, we MUST put the result into a variable, 
      -- otherwise haskell tries to print it :/ Makes sense when
      -- you think about it. 
      let res = find 'g' $ flatten $ tree1
      print res 
      let res = find 'z' $ flatten $ tree1
      print res
      putStrLn "End program"