Nested function application

Question

It's quite easy to define an operator like

(@) :: [x -> y] -> [x] -> [y]

which takes a list of functions and a list of inputs and returns a list of outputs. There are two obvious ways to implement this:

1. Apply the first function to the first input, the second function to the second input, etc.
2. Apply every function to every input.

Either is equally trivial to define. The nice thing about it is that you can now do something like

foo :: X -> Y -> Z -> R

bar :: [X] -> [Y] -> [Z] -> [R]
bar xs ys zs = [foo] @@ xs @@ ys @@ zs

This generalises to an arbitrary number of function arguments.

---

So far so good. Now for the problem: How to I change the type signature for @@ such that the type signature for bar becomes

bar :: [X] -> [Y] -> [Z] -> [[[R]]]

It's not hard to implement a function with this type; either of these will do it:

bar xs ys zs = map (\ x -> map (\ y -> map (\ z -> foo x y z) zs) ys) zs
bar xs ys zs = map (\ z -> map (\ y -> map (\ x -> foo x y z) xs) ys) zs

I'm not fussy about which result I get. But I can't figure out how to tweak the @@ operator to do this.

---

An obvious thing to try is

(@@) :: [x -> y] -> [x] -> [[y]]

It's not hard to implement this, but it won't help you. Now you have

[foo] @@ xs :: [[Y -> Z -> R]]

which is not a valid input to @@. There's no obvious way to know how many levels of lists to reach through to get to the function; clearly this approach is a dead end.

I've tried several other possible type signatures, but none of them takes me closer to the answer. Can somebody either give me a solution, or explain why none exists?

Answer 1

You've already hit upon why this is troublesome. Your function (@@) is applied to inputs of different types (e.g. [x->y], [[x -> y]], etc. This means that your type signature for @@ is too restrictive; you will need to add some polymorphism to make it more general enough to use it with nested lists. Since Haskell implements polymorphism with type classes, that's a good direction to try.

As it happens, with this problem if you know the type of the LHS, you can uniquely determine both the RHS and the result. When the input has type [a->b], the RHS must be [a] and the result must be [[b]]. This can be simplified to an input of a->b, RHS of [a], and result of [b]. Since the LHS determines the other parameters and result, we can use either fundeps or type families to represent the other types.

{-# LANGUAGE TypeFamilies, UndecidableInstances #-}

class Apply inp where
  type Left inp    :: *
  type Result  inp :: *
  (@@) :: inp -> [Left inp] -> [Result inp]

Now that we have a type class, we can make the obvious instance for a function:

instance Apply (a -> b) where
  type Left (a -> b)   = a
  type Result (a -> b) = b
  (@@) = map

The list instance isn't too bad either:

instance Apply f => Apply [f] where
  type Left [f]   = Left f
  type Result [f] = [Result f]
  l @@ r = map (\f -> f @@ r) l
  -- or    map (@@ r) l

Now our class method @@ should work with arbitrarily deep lists. Here are some tests:

*Main> (+) @@ [1..3] @@ [10..13]
[[11,12,13,14],[12,13,14,15],[13,14,15,16]]'s

let foo :: Int -> Char -> Char -> String
    foo a b c = b:c:show a

*Main> foo @@ [1,2] @@ "ab" @@ "de"
[[["ad1","ae1"],["bd1","be1"]],[["ad2","ae2"],["bd2","be2"]]]

You might want to look at the printf implementation for further inspiration.

Edit: Shortly after posting this, I realized that one could generalize the container type in my Apply class from List to an Applicative, then use the applicative instance instead of map. This would allow for both regular list and ZipList behavior.

Answer 2

Actually, this doesn't need type classes at all! You lose a little bit of convenience by avoiding type classes, but that's all.

The key point is that, despite reusing a single combinator, polymorphism allows the type of each use to be different. This is the same principle behind Applicative-style expressions like f <$> xs <*> ys <*> zs, and the end result here will look similar. As such, we'll do it for any Functor, not just lists.

The difference between this and the Applicative version is that we go deeper into the nested Functors with each step. The necessary polymorphism requires flexibility at the innermost layer, so to accomplish this we'll use a continuation-ish trick where the result of each combinator is a function that accepts a transformation to use at the innermost layer.

We'll need two operators, one that starts the chain and one that continues it incrementally. Starting with the latter:

(@@) :: (Functor f) => (((a -> b) -> f c) -> r) -> f a -> (b -> c) -> r
q  @@ xs = \k -> q (\f -> k . f <$> xs)

This takes a new argument on the right, and the expression in progress on the left. The result takes a function k, which specifies what to do to get the final result. k is combined with whatever the expression in progress already has, and both are mapped over the new argument. This is convoluted, but should look familiar to anyone who's taken CPS-style code apart.

(<@) :: (Functor f, Functor g) => f (a -> b) -> g a -> (b -> c) -> f (g c)
fs <@ xs = (<$> fs) @@ xs

The chain is started by simply mapping everything else over the first argument.

Unlike the simpler Applicative case, we also need to explicitly end the chain. As with the Cont monad, the simplest way to do this is apply the result to the identity function. We'll give that a helpful name:

nested = ($ id)

Now, we can do things like this:

test2 :: [X -> Y -> R] -> [X] -> [Y] -> [[[R]]]
test2 fs xs ys = nested (fs <@ xs @@ ys)

test3 :: [X -> Y -> Z -> R] -> [X] -> [Y] -> [Z] -> [[[[R]]]]
test3 fs xs ys zs = nested (fs <@ xs @@ ys @@ zs)

Not quite as pretty as the type class version, but it works.