Passing list elements as parameters to curried function

Question

Still a Haskell newbie here. I know just enough to get myself into trouble with wrong assumptions. If I have the following function...

quadsum w x y z = w+x+y+z

I want a function that can take a list, use each element as a parameter in a specified function like quadsum, and return a curried function for later use.

I've been trying something to the effect of...

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

With the hope of being able to do this...

magicalFunctionMaker (quadsum) [4,3,2]

Getting a curried function like...:

(((quadsum 4) 3) 2)

Or, alternatively, call:

magicalFunctionMaker (quadsum) [4,3,2,1]

Resulting in...

((((quadsum 4) 3) 2) 1)

Is this possible? How misguided am I?

Answer 1

I think you are misunderstanding the Haskell type system.

First of all, your "quadsum" function is curried already. You can write "quadsum 4 3" and get back a function that expects the 2 and the 1 as extra arguments. When you write "quadsum 4 3 2 1" that is equivalent to "((((quadsum 4) 3) 2) 1)".

In Haskell a list of integers has a different type to an integer or a tuple such as "(4,3,2,1)". Given this, it is rather difficult to understand what you are trying to do. What is supposed to happen if you write this?

magicalFunctionMaker quadsum [5,4,3,2,1]

Your "magicalFunctionMaker" looks rather like "foldl", except that the function you give to foldl only takes two arguments. So you can write:

mySum = foldl (+) 0

This returns a function that takes a list and sums the elements.

(BTW, once you grok this, learn about the difference between foldl and foldr.

Edit:

Having re-read your question, I think you are trying to get:

magicalFunctionMaker quadSum [4,3,2,1] :: Integer
magicalFunctionMaker quadSum [4,3,2] :: Integer -> Integer

This is impossible because the type of magicalFunctionMaker would depend on the length of the list argument, which would imply dynamic typing. As someone said, polyvariadic functions can do something approaching this (although not with a list argument), but that requires quite a few milli-olegs of type hackery.

Answer 2

Paul Johnson's answer pretty much covers it. Just do

quadsum 4 3 2

and the result will be the function you want, with type Integer -> Integer.

But sometimes this isn't good enough. Sometimes you get lists of numbers, you don't know how long the lists are, and you need to apply the elements to your function. This is a bit harder. You can't do:

magicalFunction2 f [] = f
magicalFunction2 f (x1:x2:xs) = f x1 x2

because the results have different types. In the first case the result needs two arguments, and in the second it's a fully-applied function so no more arguments are allowed. In this case, the best thing to do is hold onto the list and your original function until enough arguments are available:

type PAPFunc f a result = Either (f, [a]) result

magicfunc f xs = Left (f,xs)

apply (Left (f,xs)) ys = Left (f,xs++ys)
apply p _              = p

simp2 :: PAPFunc (a->a->b) a b -> PAPFunc (a->a->b) a b
simp2 (Left (f,(x1:x2:xs))) = Right (f x1 x2)
simp2 p = p

now you can do:

Main> let j = magicfunc (+) []
Main> let m = apply j [1]
Main> let n = apply m [2,3]

Main> either (const "unfinished") show $ simp2 m
"unfinished"
Main> either (const "unfinished") show $ simp2 n
"3"

You'll need a separate simplify function for each arity, a problem that's most easily fixed by Template Haskell.

Using lists of arguments (as opposed to an argument of lists) tends to be very awkward in Haskell because the multiple results all have different types, and there's very little support for collections with variable numbers of differently-typed arguments. I've seen three general categories of solutions:

1. Explicitly code for each case separately (quickly becomes a lot of work).

2. Template Haskell.

3. Type system hackery.

My answer mostly deals with trying to make 1 less painful. 2 and 3 are not for the faint of heart.

Edit: It turns out that there are some packages on Hackage that are related to this problem. Using "iteratee":

import qualified Data.Iteratee as It
import Control.Applicative

magic4 f = f <$> It.head <*> It.head <*> It.head <*> It.head

liftedQuadsum = magic4 quadsum
-- liftedQuadsum is an iteratee, which is essentially an accumulating function
-- for a list of data

Main> p <- It.enumChunk (It.Chunk [1]) liftedQuadsum
Main> It.run p
*** Exception: EofException
Main> q <- It.enumChunk (It.Chunk [2,3,4]) p
Main> It.run q
10

But "iteratee" and "enumerator" are likely overkill though.

Answer 3

I came up against this same problem: I have a function like

someFunc :: Int -> Int -> Int -> Int

What I'd love to do is make a magic function such that, for example

listApply :: [Int] -> (Int -> Int -> Int -> Int) -> Int

such that I can say

listApply [1,2,3] someFunc

Instinctively it seems, and John's answer agrees, that it should be possible to do some type system magic in order to do this. There are solutions to similar problems involving making explicitly iso-recursive datatypes with a bunch of explicit rolling and unrolling (see, e.g., chapter 20 of Types and Programming Languages, or the 4th post in this thread).

I hacked on the type solution for a while; it feels possible, but I didn't quite get it working before deciding to try out Template Haskell, and there things are a lot friendlier.

{-# LANGUAGE TemplateHaskell #-}    

import Language.Haskell.TH
import Language.Haskell.TH.Syntax

lApply :: [Int] -> String -> ExpQ
lApply    []  fn = return $ VarE (mkName fn)
lApply (l:ls) fn = [| $(lApply ls fn) l |]

(Remember to use the LANGUAGE pragma or the -XTemplateHaskell commandline switch.)

To use this, you call lApply inside a splice like so:

> $(lApply [1,2] "+")
3

Note that I have to use a string containing the name of the function I want to call: I can't lift a function directly into an ExpQ, but I can refer to its global binding. I can see how this might get annoying. Also, because of the way we traverse the list, arguments must be presented in reverse order in the list.

There are a few other wrinkles: in order to generalize this to other datatypes, those types have to have corresponding instances in the Lift class. For example, Double has no instance, but you can easily make one:

instance Lift Double where
        lift x = return $ LitE (RationalL (toRational x))

The Lit datatype does not have a DoubleL constructor, but RationalL can be used in its place since it'll splice to a general member of the Fractional class.

If you want to use this with functions that take a mix of types as arguments, you won't be able to pass a list, since lists cannot be of mixed types. You could use tuples to do this, which is honestly not much harder using Template Haskell. In that case, you'd make a function that generates the AST of a function that takes a tuple with the appropriate types inside and maps it to the function call you want. Alternatively, you might wrap your argument types inside an appropriately crafted ADT, which incidentally you could also create with Template Haskell. This is left as an exercise to the reader :)

Finally, all of the standard Template Haskell limitations apply. For example, you can't call this function from the module where it's defined because of the GHC stage restriction.

Template Haskell is fun and interesting stuff, but to be completely honest the iso-recursive datatype solution is probably a bit higher performance, and obviously doesn't require the additional use of TH. I'll come back and post a follow-up if/when I get that working :)

Answer 4

You can't even list the cases for different length "manually":

mf f [] = f
mf f [x] = f x
mf f [x,y] = f x y

--Occurs check: cannot construct the infinite type: t = t1 -> t
--Probable cause: `f' is applied to too many arguments
--In the expression: f x
--In the definition of `mf': mf f [x] = f x

That means mf can't take a function of arbitrary "arity", you have to decide for one. For the same reason you can't convert an arbitrary list to a tuple: You can't say how many elements the tuple will hold, but the type system needs to know.

There might be a solution by limiting f to a recursive type a = a -> a by using "forall" (see http://www2.tcs.ifi.lmu.de/~abel/fomega/hm.html). However, I couldn't get it working (it seems I have to tell Leksah to use the flag -XRankNTypes somewhere), and that restriction on f would make your function pretty useless.

[edit]

Thinking about, the closest thing to what you want is probably some kind of reduce function. As Paul pointed out, this is similar to foldl, foldr... (but the version below is without "extra argument" and with a homogenous type compared to foldl. Note the missing base case for empty lists)

mf :: (a → a → a) -> [a] -> a
mf f [x] = x
mf f (x:y:xs) = mf f ((f x y) : xs)

Answer 5

Not going to work I think. (((quadsum 4) 3) 2) has a different type Intger -> Integer for instance than ((((quadsum 4) 3) 2) 1) which has a type of Integer.

Answer 6

I was going to edit my other post, but this is big enough for its own.

Here's one way of doing it with "type magic," but it feels to me like it's somewhat suboptimal, since it requires a lifting function that is specific to functions of a particular number of arguments (more below).

Let's begin by defining a recursive datatype

data RecT a = RecR a
            | RecC (a -> RecT a)

So variables of type RecT can either be just a wrapped result (RecR) or they can be a continued recursion (RecC).

Now,how do we take something and cast it into type RecT a?

Values are easy:

valRecT x = RecR x

RecR x is obviously of type RecT a.

What about a function that takes one argument, like id?

idRecT x = RecC $ \x -> RecR x

RecC wraps a function that takes a variable and returns type RecT a. The expression

\x -> RecR x

is just such a function, since as we observed before RecR x is of type RecT a.

More generally, any one-argument function can be lifted:

lift1RecT :: (a -> a) -> RecT a
lift1RecT fn = RecC $ \a -> RecR $ fn a

We can generalize this by repeatedly wrapping more deeply-nested function calls inside RecC:

lift2RecT :: (a -> a -> a) -> RecT a
lift2RecT fn = RecC $ \b -> RecC $ \a -> RecR $ fn b a

lift3RecT :: (a -> a -> a -> a) -> RecT a
lift3RecT fn = RecC $ \c -> RecC $ \b -> RecC $ \a -> RecR $ fn c b a

OK, so we've done all this work to turn a function of an arbitrary number of arguments into a single type, RecT a. How do we use this?

We can easily write down one level of function application:

reduceRecT :: RecT a -> a -> RecT a
reduceRecT (RecC fn) = fn
reduceRecT  _        = undefined

In other words, reduceRecT takes an argument of type RecT a and another of type a and returns a new RecT a that's been one level reduced.

We can also unroll a finished computation inside a RecT into the result:

unrollRecT :: RecT a -> a
unrollRecT (RecR fn) = fn
unrollRecT  _        = undefined

Now we're ready to apply a list of arguments to a function!

lApply :: [a] -> RecT a -> a
lApply    []  fn = unrollRecT fn
lApply (l:ls) fn = lApply ls $ (reduceRecT fn) l

Let's consider the base case first: if we're finished with the computation, we just unwrap the result and return it. In the recursive case, we reduce the argument list by one, then transform the fn by applying the head of the list to the reduced fn, resulting in a new RecT a.

Let's give this a try:

lApply [2,5] $ lift2RecT (**)
> 32.0

So, advantages and disadvantages of this approach? Well, the Template Haskell version can do partial list application; this isn't true of the isorecursive type solution as presented here (though we could in principle fix this with some ugliness). The type solution also has the disadvantage of having a lot more boilerplate code associated with it: we need a listNRecT for all N that we want to use. Finally, it's a lot less easy to generalize this to the analogous tuple solution if we want to lApply to functions of mixed variable types.

Of course, another interesting possibility is to enhance brevity by using Template Haskell to generate the listNRecT functions; this eliminates some boilerplate, but in a sense buys the disadvantages of both implementations.