how to map functions to multi-level lists in Haskell -

this first post here, , have introduce myself saying haskell beginner. love promise of pure functional programming, after 20 years of imperative programming (mostly java), haskell not come naturally me.

so here's first question. trying map function multi-level list. code works, depth level of list mapping occurs preset @ 3:

(map . map . map) (+1) [[[1,4],[2,3]],[[5]]] 

i need more general, specify level mapping happens (depth parameter in line below), so:

let depth = 3 :: int (foldl (.) id (replicate depth map)) (+1) [[[1,4],[2,3]],[[5]]] 

unfortunately, not work, error:

occurs check: cannot construct infinite type: t0 = [t0] expected type: ([[[t0]]] -> [[[t0]]]) -> [[[t0]]] -> [[[t0]]]   actual type: ([[[t0]]] -> [[[t0]]]) -> [[[[t0]]]] -> [[[[t0]]]] in second argument of `replicate', namely `map' in third argument of `foldl', namely `(replicate depth map)' in expression:   (foldl (.) id (replicate depth map))     (+ 1) [[[1, 4], [2, 3]], [[5]]] 

however, code works:

foldl (.) id (replicate 3 negate) $ 7 

so again, questions is: how map function onto multi-level list, depth of list known in advance. like:

(foldl (.) id (replicate 3 map)) (+1) [[[1,4],[2,3]],[[5]]] 

and result back:

[[[2,5],[3,4]],[[6]]] 

thank in advance.

what you're asking impossible (at least difficult) though it's difficult see @ first.

the proper tool analysis here compile-time/runtime distinction appearing in code. in particular, let's have function maps such maps 3 f maps f third layer of list. type? well, can write them out

maps 1 :: (a -> b) -> [a]     -> [b] maps 2 :: (a -> b) -> [[a]]   -> [[b]] maps 3 :: (a -> b) -> [[[a]]] -> [[[b]]] ... 

this may strange, if doesn't yet take careful note of what's going on here: ultimate type of maps n f depends upon value of n, can known @ runtime.

since have typecheck things @ compile time , existence of maps mean couldn't know type of maps n without knowing runtime value of n we're sunk. such function, maps, cannot exist.

---

in theory anyway. in practice, can solve kind of situation. but, usual when there type errors, first must become more clear we're trying achieve.

the first interpretation of function we'd extend map operation on n-dimensional array. long we're fixing n @ compile time (which, again, going bit challenging escape from) may explicit idea

newtype twod   = twod   { getlists2d :: [[a]] } newtype threed = threed { getlists3d :: [[[a]]] } newtype fourd  = fourd  { getlists4d :: [[[[a]]]] } -- etc... 

now each 1 of these has natural extension of map. indeed, idea of many kinds of types being "mappable" intuition of functor typeclass, can instantiate them functors

instance functor twod   fmap f (twod   lists) = twod   ((map . map)       f lists) instance functor threed fmap f (threed lists) = threed ((map . map . map) f lists) -- etc... 

in fact, such natural idea ghc implements extension derive these functor instances us.

{-# language derivefunctor #-}  newtype twod   = twod   { getlists2d :: [[a]] }     deriving functor newtype threed = threed { getlists3d :: [[[a]]] }   deriving functor newtype fourd  = fourd  { getlists4d :: [[[[a]]]] } deriving functor -- etc... 

and fmap can used on of our n-dimensional array types quite naturally.

---

another possible interpretation we'd not represent n-dimensional array instead "rose tree". difference in n-dimensional arrays "index sequence" of every value n elements long. instance, upper left value indexed @ [0,0,0] in threed. in rose tree, have mixtures of lists , not each value @ same depth. means no longer have static guarantee of depth of list way types [a] versus [[[[a]]]], means of depth information occurs @ runtime.

which right want it.

let's define rose first.

data rose = rose [rose a] | l deriving functor -- functor free! 

we can produce sample value of rose char make more clear how rose works.

rose [rose [l 'f', l 'o', l 'o', rose [l 'x', l 'y', l 'z']], l 'b', l 'a', l 'r'] 

i think of rose being similar "lisp"-style lists, i.e. arbitrarily nested trees.

(('f' 'o' 'o' ('x', 'y' 'z')) 'b' 'a' 'r') 

again, however, fun part since leave depth of rose tree runtime (and indeed can vary dynamically @ runtime) can use runtime information map on it.

mapr :: int -> (a -> a) -> rose mapr 0 f (l a)     = l (f a) mapr n f (l a)     = l mapr n f (rose as) = rose (map (mapr (n-1) f) as) 

note unlike normal map, mapr's function parameter cannot change type of rose. because we're mapping on particular "layer" of rose tree , cannot uniformly change types of every value inside of it. that, still must use fmap our derived functor instance.