CODEWITHSUNDEEP
haskell
Raskell
Raskell

Reputation: 158

Composing arbitrarily many maps in Haskell

How is it possible to compose n maps in Haskell? I've tried doing it recursively:

composeMap 0 f = (\x -> x)
composeMap n f = (.) f (composeMap (n-1) f)

And iteratively:

composeMap' n k f g =
  if n == k then g
            else composeMap' n (k+1) f (f . g)

composeMap n f = composeMap' n 0 f (\x -> x)

But to no avail. Haskell thinks I am constructing an infinite type. This is obviously false as the function defined is finite for any n >= 0.

Any suggestions?

Some have posted solutions treating f as having the following type signature:

f :: a -> a

However, I want this to work for f s.t. f is polymorphic in the following way:

f :: a -> a'
f :: a' -> a''

In particular, I want a function that works for the function map, with possible type signatures:

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

The function compiles perfectly fine, but Haskell infers the following type signature, which is not what I want:

composeMap'' :: Int -> (b -> b) -> b -> b

I've even tried wrapping map in a monad, but Haskell still thinks I'm constructing an infinite type:

composeMap n f = foldl (>>=) f (replicate n (\x -> return (map x)))

Edit: I got what I want with the following template Haskell code. Pretty sweet.

This is for declaring the composed map functions:

composeMap :: Int -> Q Dec
composeMap n
  | n >= 1    = funD name [cl]
  | otherwise = fail "composeMap: argument n may not be <= 0"
  where
    name = mkName $ "map" ++ show n
    composeAll = foldl1 (\fs f -> [| $fs . $f |])
    funcs = replicate n [| map |]
    composedF = composeAll funcs
    cl = clause [] (normalB composedF) []

This is for inlining the composed map. It is more flexible:

composeMap :: Int -> Q Exp
composeMap n = do
  f <- newName "f"
  maps <- composedF
  return $ LamE [(VarP f)] (AppE maps (VarE f))
  where
    composeAll = foldl1 (\fs f -> [| $fs . $f |])
    funcs = replicate n [| map |]
    composedF = composeAll funcs

Also, the guys who put the question on hold didn't even understand the question in the first place...

Upvotes: 1

Views: 219

Answers (1)

Sam De Meyer
Sam De Meyer

Reputation: 2381

I am afraid I am missing something. Your first implementation compiles and works fine for me (ghc 8.0.2).

Your second implementation failed to compile because you forgot the ' in the else clause. Here is my complete source file:

composeMap1 0 f = (\x -> x)
composeMap1 n f = (.) f (composeMap1 (n-1) f)

composeMap2' n k f g =
  if n == k then g
            else composeMap2' n (k+1) f (f . g)

composeMap2 n f = composeMap2' n 0 f (\x -> x)

And some tests

λ: :l question.hs
[1 of 1] Compiling Main             ( question.hs, interpreted )
Ok, modules loaded: Main.
λ: doubleQuote = composeMap1 2 (\x -> "'" ++ x ++ "'")
λ: doubleQuote "something"
"''something''"
λ: doubleQuote = composeMap2 2 (\x -> "'" ++ x ++ "'")
λ: doubleQuote "something"
"''something''"
λ: plusThree = composeMap1 3 (+1)
λ: plusThree 10
13
λ: plusThree = composeMap2 3 (+1)
λ: plusThree 10
13

Upvotes: 1

Related Questions