How to convert a Tree in Haskell to a flat list

Question

I have a tree defined in Haskell like:

data NTree a = Nil | Tree a [NTree a] deriving Show

I want to 'flatten' the tree so that all the nodes appear in a list. I'm trying to do so by:

arrayify :: NTree Int -> [Int]

arrayify (x:xs) = x ++ arrayify xs

I can kind of tell that this is wrong, but I have no idea how to fix this. For reference, this is the error I'm getting:

• Couldn't match expected type ‘NTree Int -> [Int]’
              with actual type ‘[Int]’
• Possible cause: ‘(++)’ is applied to too many arguments
  In the expression: x ++ arrayify xs
  In an equation for ‘arrayify’: arrayify = x ++ arrayify xs

Answer 1

Since arrayify expects an NTree Int, you probably want to pattern match on the two data constructors, so:

arrayify :: NTree Int -> [Int]
arrayify Empty = …
arrayify (Tree v ts) = …

For the Empty case, you should return an empty list, for the Tree v ts you can make a list that starts with v and then has the arrayifys of the elements of ts as children. You can use the (:) :: a -> [a] -> [a] and concatMap :: Foldable f => (a -> [b]) -> f a -> [b] for this.

But instead of writing arrayify yourself, you can let Haskell derive an instance of Foldable for your NTree:

{-# LANGUAGE DeriveFoldable #-}

data NTree a = Nil | Tree a [NTree a] deriving (Foldable, Show)

Then you can call toList :: Foldable f => f a -> [a] on an NTree object.