Personal tools

99 questions/Solutions/7

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
(Some additional solutions for this question)
m (Added in a new solution)
Line 21: Line 21:
 
flt' (List (x:ls)) xs = flt' x (flt' (List ls) xs)
 
flt' (List (x:ls)) xs = flt' x (flt' (List ls) xs)
 
flt' (List []) xs = xs
 
flt' (List []) xs = xs
  +
</haskell>
  +
or with foldr1
  +
<haskell>
  +
flatten3 :: NestedList a -> [a]
  +
flatten3 (Elem x) = [x]
  +
flatten3 (List xs) = foldr1 (++) $ map flatten xs
 
</haskell>
 
</haskell>
   

Revision as of 23:12, 25 December 2011

(**) Flatten a nested list structure.

data NestedList a = Elem a | List [NestedList a]
 
flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

or without concatMap

flatten :: NestedList a -> [a]
flatten (Elem a   )   = [a]
flatten (List (x:xs)) = flatten x ++ flatten (List xs)
flatten (List [])     = []
flatten2 :: NestedList a -> [a]
flatten2 a = flt' a []
  where flt' (Elem x)      xs = x:xs
        flt' (List (x:ls)) xs = flt' x (flt' (List ls) xs)
        flt' (List [])     xs = xs

or with foldr1

flatten3 :: NestedList a -> [a]
flatten3 (Elem x) = [x]
flatten3 (List xs) =  foldr1 (++) $ map flatten xs

We have to define a new data type, because lists in Haskell are homogeneous. [1, [2, [3, 4], 5]] is a type error. Therefore, we must have a way of representing a list that may (or may not) be nested.

Our NestedList datatype is either a single element of some type (Elem a), or a list of NestedLists of the same type. (List [NestedList a]).