Map over a list of lists of arbitrary depth in Haskell

Question

One can map over a list of lists of arbitrary depth as follows:

map           :: (a -> b) ->   [a]   ->   [b]
(map.map)     :: (a -> b) ->  [[a]]  ->  [[b]]
(map.map.map) :: (a -> b) -> [[[a]]] -> [[[b]]]

Is it possible to write a single function handling all such cases? Uiua has the ∵ each function which does this on an array of arbitrary rank. Such functions are called pervasive functions in array languages.

Answer 1

Nested lists are probably too general to guide type inference effectively, so even though it's pretty simple to implement deepmap as a type class:

class DeepMap a b a' b' where
  deepmap :: (a -> b) -> [a'] -> [b']

instance DeepMap a b a b where
  deepmap = map
instance (DeepMap a b a' b') => DeepMap a b [a'] [b'] where
  deepmap = map . deepmap

you have to provide a lot of guidance to the type checker to use it:

main = do
  print $ deepmap @Int @Int @Int @Int (*2) $ [1,2]
  print $ deepmap @Int @Int @[Int] @[Int] (*2) $ [[1],[2]]

If all four type parameters for the DeepMap class are resolved by context, then it works okay:

main = do
    print $ (deepmap ord ["ab","c"] :: [[Int]])

In real code, you'd probably introduce a new data type to represent such arrays, like this GADT with type-level indexing of the array rank. (Indexing by a type of kind [Int] representing the dimensions would probably make even more sense, if you were really trying to represent terms in an "array language".)

data Nat = Z | S Nat

data Array n a where
  Scalar :: a -> Array Z a
  Array :: [Array n a] -> Array (S n) a
deriving instance (Show a) => Show (Array Z a)
deriving instance (Show (Array n a)) => Show (Array (S n) a)

This type allows a pretty straightforward deepmap implementation:

deepmap :: (a -> b) -> Array n a -> Array n b
deepmap f (Scalar x) = Scalar (f x)
deepmap f (Array xs) = Array (fmap (deepmap f) xs)

main = do
  print $ deepmap (*2) $ Scalar 1
  print $ deepmap (*2) $ Array [Scalar 1, Scalar 2]
  print $ deepmap (*2) $ Array [Array [Scalar 1], Array [Scalar 2]]