Is there a smoothing function for a nested list of items?

Question

How can I flatten a nested list like this:

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

Answer 1

Since no one has given this, you can define a function that will smooth out lists of arbitrary depth using MultiParamTypeClasses. I actually did not find it useful, but I hope it could be considered an interesting hack. I got the idea from the implementation of the multivarian function of Oleg.

 {-# LANGUAGE MultiParamTypeClasses, OverlappingInstances, FlexibleInstances #-} module Flatten where class Flatten io where flatten :: [i] -> [o] instance Flatten aa where flatten = id instance Flatten io => Flatten [i] o where flatten = concatMap flatten 

Now, if you download 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> :ti i :: [[[Integer]]] *Flatten> flatten i :: [Integer] [1,2,3,4,5,6] 

Note that it is usually necessary to provide an annotation of the result type, since otherwise ghc cannot determine where to stop recursively applying the flatten class flatten . If you use a function with a monomorphic type, which, however, is sufficient.

 *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 

Answer 2

Yes, its concat from the standard foreplay, given

 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] 

Answer 3

As others have pointed out, concat :: [[a]] -> [a] is the function you are looking for and it cannot smooth nested lists of arbitrary depth. You must call it several times to smooth it to the desired level.

However, the operation generalizes to other monads. Then it is known as join and is of type Monad m => m (ma) -> ma .

 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 

Answer 4

As Hammar pointed out, join is a "monadic" way to smooth out a list. You can use do -Notation to write easily-smoothed functions of several levels:

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

Answer 5

 import Data.List let flatten = intercalate [] flatten $ flatten [[[1,2],[3]],[[4]]] [1,2,3,4] 

Answer 6

A sliding list can be approximated by the Data.Tree symbol, which can be flattened by the corresponding flatten function.

I speak approximately because Data.Tree allows to attach a data element to each node, and not just to sheets. However, you can create Data.Tree (Maybe a) and attach Nothing to the nodes of the body and smooth it with catMaybes . flatten catMaybes . flatten .

Answer 7

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

It is impossible to write a function that removes an arbitrary level of nesting, because it is impossible to express a type of function that accepts an arbitrary nested list and returns a flat list using a Haskell type system (using the list data type - you can write your own data type for arbitrary nested lists and write for its smoothing function).