# KolmogorovFlatMaps

17 Apr 2014

As of March 2020, School of Haskell has been switched to read-only mode.

### Sections

We will show how to define in Haskell a `flatten` and `prioritiesMap`. Both of them quite standard and known to Haskell programmers. The first mapping is essentially a flatMap on NestedLists:

``````data NestedList a = Elem a | List [NestedList a]
deriving (Show)

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

main = do
print (flatten list)
where
list = List [List[List [Elem (2,15)]], List [ List[Elem (7,5)], List[Elem (6,4)]]]    ``````

A discussion of `NestedList` one can find at 99 Haskell problems. More specifically, this is problem 7 and the above solution is one of the listed solutions.

Now let us improve on the pretty printing side

``````data NestedList a = Elem a | List [NestedList a]
deriving (Show)

-- simple pretty print, a slightly better pp' below

pp :: Show a => NestedList a -> IO ()
pp = (mapM_ putStr) . bracketing
where
bracketing (Elem a)             = [show a]
bracketing (List x)             = ["("]++(concatMap bracketing x)++[")"]

main = do
pp list
where
list = List [List[List [Elem (2,15)]], List [ List[Elem (7,5)], List[Elem (6,4)]]]       ``````

Now let us improve even further adding commas in appropriate places

``````data NestedList a = Elem a | List [NestedList a]
deriving (Show)

-- The ordered pairs (n,m) are kept unchanged and
-- lists are indicated by braces { and }. The number of braces to the right
-- is the implicit parity index (see prioritiesMap below)

pp' :: Show a => NestedList a -> IO ()
pp' = (mapM_ putStr) . bracketing
where
bracketing (Elem a)             = [show a]
bracketing (List (x:[]))        = ["{"]++(bracketing x)++["}"]
bracketing (List (x:xs))        = ["{"]++(bracketing x)++[","]++(concatMap bracketing xs)++["}"]

main = do
pp' list
where
list = List [List[List [Elem (2,15)]], List [ List[Elem (7,5)], List[Elem (6,4)]]]   ``````

We are ready to define `prioritiesMap`

``````data NestedList a = Elem a | List [NestedList a]
deriving (Show)

prioritiesMap (x) = prioritiesMap'(x,0)

prioritiesMap' :: (NestedList a, Int) -> [Int]
prioritiesMap' (Elem a,n)   = [n]
prioritiesMap' (List (x:[]), n) =  prioritiesMap' (x,n+1)
prioritiesMap' (List (x:y:xs),n) = prioritiesMap' (x,0) ++ prioritiesMap' (List( y:xs),n)
prioritiesMap' (List [],n)     = []

main = do
print (prioritiesMap list)
where
list = List [List[List [Elem (2,15)]], List [ List[Elem (7,5)], List[Elem (6,4)]]]    ``````

Some links related to the paper: