Ninety-Nine Haskell Problems: #7

-- Problem 7: flatten a nested list

import Data.List (subsequences)

-- Haskell lists won't do because they're homogeneous, hence the new
-- type:

data NestedList a = Elem a
  | List [NestedList a]
  deriving Show

variants :: [NestedList Integer]
variants = Elem 1 : map List (subsequences
  [ Elem 1
  , List []
  , List [Elem 2]
  , List [List []]
  , List [List [Elem 3]]
  ])

flatten :: NestedList a -> [a]
flatten (List []) = []
flatten (Elem x) = [x]
flatten (List (x:xs)) = flatten x ++ go xs
  where
    go [] = []
    go [y] = flatten y
    go (y:ys) = flatten y ++ go ys

formatter :: Show a => NestedList a -> [Char]
formatter x = show x ++ " -> " ++ show (flatten x)

main :: IO ()
main = mapM_ (putStrLn . formatter) variants

-- Elem 1 -> [1]
-- List [] -> []
-- List [Elem 1] -> [1]
-- List [List []] -> []
-- List [Elem 1,List []] -> [1]
-- List [List [Elem 2]] -> [2]
-- List [Elem 1,List [Elem 2]] -> [1,2]
-- List [List [],List [Elem 2]] -> [2]
-- List [Elem 1,List [],List [Elem 2]] -> [1,2]
-- List [List [List []]] -> []
-- List [Elem 1,List [List []]] -> [1]
-- List [List [],List [List []]] -> []
-- List [Elem 1,List [],List [List []]] -> [1]
-- List [List [Elem 2],List [List []]] -> [2]
-- List [Elem 1,List [Elem 2],List [List []]] -> [1,2]
-- List [List [],List [Elem 2],List [List []]] -> [2]
-- List [Elem 1,List [],List [Elem 2],List [List []]] -> [1,2]
-- List [List [List [Elem 3]]] -> [3]
-- List [Elem 1,List [List [Elem 3]]] -> [1,3]
-- List [List [],List [List [Elem 3]]] -> [3]
-- List [Elem 1,List [],List [List [Elem 3]]] -> [1,3]
-- List [List [Elem 2],List [List [Elem 3]]] -> [2,3]
-- List [Elem 1,List [Elem 2],List [List [Elem 3]]] -> [1,2,3]
-- List [List [],List [Elem 2],List [List [Elem 3]]] -> [2,3]
-- List [Elem 1,List [],List [Elem 2],List [List [Elem 3]]] -> [1,2,3]
-- List [List [List []],List [List [Elem 3]]] -> [3]
-- List [Elem 1,List [List []],List [List [Elem 3]]] -> [1,3]
-- List [List [],List [List []],List [List [Elem 3]]] -> [3]
-- List [Elem 1,List [],List [List []],List [List [Elem 3]]] -> [1,3]
-- List [List [Elem 2],List [List []],List [List [Elem 3]]] -> [2,3]
-- List [Elem 1,List [Elem 2],List [List []],List [List [Elem 3]]] -> [1,2,3]
-- List [List [],List [Elem 2],List [List []],List [List [Elem 3]]] -> [2,3]
-- List [Elem 1,List [],List [Elem 2],List [List []],List [List [Elem 3]]] -> [1,2,3]