gistfile1.hs

-- A friend interviewed at Google and was given the task of
-- making a linked list from a binary tree where an element's
-- next element is its sibling, or null where there is none.

-- Example:
--        A
--       / \
--      /   \
--     B     C
--    /     / \
--   D     F   G
--
-- should become A -> B -> C -> D -> null -> F -> G.

-- While half-asleep the next morning, I realized that the path
-- to each element in the tree is just the bits of its index in
-- the list, so

data Tree a = Tree a (Maybe (Tree a)) (Maybe (Tree a))

toList :: Tree a -> [Maybe (Tree a)]
toList tree = map (lookupByPath tree . reverse . toBits) [1 .. maxIndex tree]

maxIndex :: Tree a -> Int
maxIndex tree = maxIndex' 1 tree
  where
    maxIndex' n (Tree _ Nothing   Nothing)   = n
    maxIndex' n (Tree _ (Just t)  Nothing)   = maxIndex' (2*n) t
    maxIndex' n (Tree _ Nothing   (Just t))  = maxIndex' (2*n+1) t
    maxIndex' n (Tree _ (Just t1) (Just t2)) =
        max (maxIndex' (2*n) t1) (maxIndex' (2*n+1) t2)

lookupByPath :: Tree a -> [Bool] -> Maybe (Tree a)
lookupByPath t [] = Just t
lookupByPath (Tree _ Nothing  _) (False : path) = Nothing
lookupByPath (Tree _ (Just t) _) (False : path) = lookupByPath t path
lookupByPath (Tree _ _ Nothing)  (True  : path) = Nothing
lookupByPath (Tree _ _ (Just t)) (True  : path) = lookupByPath t path

toBits :: Int -> [Bool]
toBits n
  | n <= 1 = []
  | otherwise = odd n : toBits (n `div` 2)

content :: Tree a -> a
content (Tree a _ _) = a

example :: Tree Char
example = Tree 'A' (Just b) (Just c)
  where
    b = Tree 'B' (Just d) Nothing
    c = Tree 'C' (Just f) (Just g)
    d = Tree 'D' Nothing  Nothing
    f = Tree 'F' Nothing  Nothing
    g = Tree 'G' Nothing  Nothing

-- map (fmap content) (toList example)
-- => [Just 'A',Just 'B',Just 'C',Just 'D',Nothing,Just 'F',Just 'G']