CODEWITHSUNDEEP
haskell
Grebalb
Grebalb

Reputation: 113

Flatten a list of arbitrary depth in Haskell

I'm trying to figure out how to flatten a list of n arbitrary depth in Haskell. Right now my function looks like:

data NestedList a = Regular [a] | Nested [NestedList a]

flatten::(Num a, Eq a)=> NestedList a -> [a]
flatten (Regular as) = as
flatten (Nested as) = concatMap flatten as

But then I try to invoke it:

*Main> flatten [1,2,3,[1,[1,2]],2]

I get this error message:

    • Couldn't match expected type ‘NestedList a’
                  with actual type ‘[[[Integer]]]’
    • In the first argument of ‘flatten’, namely
        ‘[1, 2, 3, [1, [1, 2]], ....]’
      In the expression: flatten [1, 2, 3, [1, [1, 2]], ....]
      In an equation for ‘it’: it = flatten [1, 2, 3, ....]
    • Relevant bindings include it :: [a] (bound at <interactive>:25:1)

I haven't programmed in Haskell in quite son time so I can't really remember how to fix this error, or if my function is just plain wrong. Any help would be appreciated.

Upvotes: 1

Views: 177

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476699

You did not construct a nested list, but a "simple" list. Furthermore the definition of the nested list, does not really allow to write the list you describe, you can wrap the elements in singleton lists, but that will make it more complicated.

You can implement such nested list as:

data NestedList a = Leaf a | Nested [NestedList a]

If you use the -XDeriveFoldable option you do not even need to implement flatten yourself, but can let Haskell do the work for you:

{-# LANGUAGE DeriveFoldable #-}

data NestedList a = Leaf a | Nested [NestedList a] deriving Foldable

Then we can call this with:

import Data.Foldable

toList (Nested [Leaf 1, Leaf 2, Leaf 3, Nested [Leaf 1,Nested [Leaf 1, Leaf 2]], Leaf 2])

For the given sample list, this gives us:

Prelude Data.Foldable> toList (Nested [Leaf 1, Leaf 2, Leaf 3, Nested [Leaf 1,Nested [Leaf 1, Leaf 2]], Leaf 2])
[1,2,3,1,1,2,2]

Upvotes: 7

Related Questions