Is there a function to flatten a nested list of elements?

How can I flatten a nested list like this:

[1, 2, 3, 4] == fla开发者_JS百科tten [[[1,2],[3]],[[4]]]

---

Yes, it’s concat from the Standard Prelude, given by

concat :: [[a]] -> [a]
concat xss = foldr (++) [] xss

If you want to turn [[[a]]] into [a], you must use it twice:

Prelude> (concat . concat) [[[1,2],[3]],[[4]]]
[1,2,3,4]

---

Since nobody else has given this, it is possible to define a function which will flatten lists of an arbitrary depth by using MultiParamTypeClasses. I haven't actually found it useful, but hopefully it could be considered an interesting hack. I got the idea from Oleg's polyvariadic function implementation.

{-# LANGUAGE MultiParamTypeClasses, OverlappingInstances, FlexibleInstances #-}

module Flatten where

class Flatten i o where
  flatten :: [i] -> [o]

instance Flatten a a where
  flatten = id

instance Flatten i o => Flatten [i] o where 
  flatten = concatMap flatten

Now if you load it and run in ghci:

*Flatten> let g = [1..5]
*Flatten> flatten g :: [Integer]
[1,2,3,4,5]
*Flatten> let h = [[1,2,3],[4,5]]
*Flatten> flatten h :: [Integer]
[1,2,3,4,5]
*Flatten> let i = [[[1,2],[3]],[],[[4,5],[6]]]
*Flatten> :t i
i :: [[[Integer]]]
*Flatten> flatten i :: [Integer]
[1,2,3,4,5,6]

Note that it's usually necessary to provide the result type annotation, because otherwise ghc can't figure out where to stop recursively applying the flatten class method. If you use a function with a monomorphic type that's sufficient however.

*Flatten> :t sum
sum :: Num a => [a] -> a
*Flatten> sum $ flatten g

<interactive>:1:7:
    No instance for (Flatten Integer a0)
      arising from a use of `flatten'
    Possible fix: add an instance declaration for (Flatten Integer a0)
    In the second argument of `($)', namely `flatten g'
    In the expression: sum $ flatten g
    In an equation for `it': it = sum $ flatten g
*Flatten> let sumInt = sum :: [Integer] -> Integer
*Flatten> sumInt $ flatten g
15
*Flatten> sumInt $ flatten h
15

---

As others have pointed out, concat :: [[a]] -> [a] is the function you are looking for, and it can't flatten nested lists of arbitrary depth. You need to call it multiple times to flatten it down to the desired level.

The operation does generalize to other monads, though. It is then known as join, and has the type Monad m => m (m a) -> m a.

Prelude Control.Monad> join [[1, 2], [3, 4]]
[1,2,3,4]    
Prelude Control.Monad> join (Just (Just 3))
Just 3
Prelude Control.Monad.Reader> join (+) 21
42

---

import Data.List
let flatten = intercalate []

flatten $ flatten [[[1,2],[3]],[[4]]]
[1,2,3,4]

---

As hammar pointed out, join is the "monadic" way to flatten a list. You can use the do-Notation as well to write easily flatten functions of several levels:

flatten xsss = do xss <- xsss
                  xs <- xss
                  x <- xs
                  return x

---

An arbitrarily nested list can be approximated by a Data.Tree, which can be flattened by the appropriately named function flatten.

I say approximated because Data.Tree allows a data item to be attached to every node, not just the leaves. However, you could create a Data.Tree (Maybe a), and attach Nothing to the body nodes, and flatten with catMaybes . flatten.

---

You can remove one level of nesting using concat, and consequently you can apply n levels of nesting by applying concat n times.

It is not possible to write a function which removes an arbitrary level of nestings, as it is not possible to express the type of a function, which takes an arbitrarily nested list and returns a flat list, using Haskell's type system (using the list datatype that is - you can write your own datatype for arbitrarily nested lists and write a flatten function for that).