How do I define Lisp’s apply in Haskell?

Question

Shouldn’t this definition be allowed in a lazy language like Haskell in which functions are curried?

apply f [] = f apply f (x:xs) = apply (f x) xs 

It’s basically a function that applies the given function to the given list of arguments and is very easily done in Lisp for example. Are there any workarounds?

Answer 1

It is hard to give a static type to the apply function, since its type depends on the type of the (possibly heterogeneous) list argument. There are at least two ways one way to write this function in Haskell that I can think of:

Using reflection

We can defer type checking of the application until runtime:

import Data.Dynamic import Data.Typeable  apply :: Dynamic -> [Dynamic] -> Dynamic apply f []      = f apply f (x:xs)  = apply (f `dynApp` x) xs 

Note that now the Haskell program may fail with a type error at runtime.

Via type class recursion

Using the semi-standard Text.Printf trick (invented by augustss, IIRC), a solution can be coded up in this style (exercise). It may not be very useful though, and still requires some trick to hide the types in the list.

Edit: I couldn't come up with a way to write this, without using dynamic types or hlists/existentials. Would love to see an example

Answer 2

I like Sjoerd Visscher's reply, but the extensions -- especially IncoherentInstances, used in this case to make partial application possible -- might be a bit daunting. Here's a solution that doesn't require any extensions.

First, we define a datatype of functions that know what to do with any number of arguments. You should read a here as being the "argument type", and b as being the "return type".

data ListF a b = Cons b (ListF a (a -> b)) 

Then we can write some (Haskell) functions that munge these (variadic) functions. I use the F suffix for any functions that happen to be in the Prelude.

headF :: ListF a b -> b headF (Cons b _) = b  mapF :: (b -> c) -> ListF a b -> ListF a c mapF f (Cons v fs) = Cons (f v) (mapF (f.) fs)  partialApply :: ListF a b -> [a] -> ListF a b partialApply fs          []     = fs partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs  apply :: ListF a b -> [a] -> b apply f xs = headF (partialApply f xs) 

For example, the sum function could be thought of as a variadic function:

sumF :: Num a => ListF a a sumF = Cons 0 (mapF (+) sumF)  sumExample = apply sumF [3, 4, 5] 

However, we also want to be able to deal with normal functions, which don't necessarily know what to do with any number of arguments. So, what to do? Well, like Lisp, we can throw an exception at runtime. Below, we'll use f as a simple example of a non-variadic function.

f True True True  = 32 f True True False = 67 f _ _ _ = 9  tooMany = error "too many arguments" tooFew  = error "too few arguments" lift0 v = Cons v tooMany lift1 f = Cons tooFew (lift0 f) lift2 f = Cons tooFew (lift1 f) lift3 f = Cons tooFew (lift2 f)  fF1 = lift3 f  fExample1 = apply fF1 [True, True, True] fExample2 = apply fF1 [True, False] fExample3 = apply (partialApply fF1 [True, False]) [False] 

Of course, if you don't like the boilerplate of defining lift0, lift1, lift2, lift3, etc. separately, then you need to enable some extensions. But you can get quite far without them!

Here is how you can generalize to a single lift function. First, we define some standard type-level numbers:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeFamilies, UndecidableInstances #-}  data Z = Z newtype S n = S n 

Then introduce the typeclass for lifting. You should read the type I n a b as "n copies of a as arguments, then a return type of b".

class Lift n a b where     type I n a b :: *     lift :: n -> I n a b -> ListF a b  instance Lift Z a b where     type I Z a b = b     lift _ b = Cons b tooMany  instance (Lift n a (a -> b), I n a (a -> b) ~ (a -> I n a b)) => Lift (S n) a b where     type I (S n) a b = a -> I n a b     lift (S n) f = Cons tooFew (lift n f) 

And here's the examples using f from before, rewritten using the generalized lift:

fF2 = lift (S (S (S Z))) f  fExample4 = apply fF2 [True, True, True] fExample5 = apply fF2 [True, False] fExample6 = apply (partialApply fF2 [True, False]) [False]