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.