How to create a polyvariadic haskell function?

Question

I need a function which takes an arbitrary number of arguments (All of the same type), does something with them and afterwards gives a result back. A list of arguments is impracticable in my specific case.

As I looked through the haskell libs, I saw that the function printf (from module Text.Printf) uses a similar trick. Unfortunately, I couldn't understand that magic by looking at the source.

Can somebody explain how to achieve this, or at least some webpage/paper/whatever where I could find a good description for this?

Motivation:

The reason I need this is really quite simple. For school (computer science class), we are required to write a module that is able to "record" a mathematical expression, express it as a string (Via writing an instance of Num/Real/etc for an own datatype), and perform various operations on it.

This datatype contains a special constructor for a variable, which may be replaced by a value or whatever by a specified function. One of the goals is to write a function, which takes such an expression with some number of variables (pairs of type (Char,Rational)) and calculates the result of the expression. We should look at how to express the goal of the function best. (My idea: The function returns another function which takes exactly as many arguments as vars that are defined in the function - seems to be impossible).

Gotham

It would be interesting to see your use case for this. – Synagogue

Just some project for school. I'll edit the question and post the purpose. – Gotham

You might consider other approaches - a function taking a list: evaluate :: [(Char, Rational)] -> Expr -> Rational; a function taking a function: (Char -> Rational) -> Expr -> Rational; a function taking a map: Data.Map.Map Char Rational -> Expr -> Rational. – More

Note that using such a variadic function means that users of your module will receive very cryptic error messages when their code doesn't type-check. It's much easier to understand an error like "this is not a list" than an error like "missing instance of PrintfType ... for ...". – Gambill

Answer 1

The key points of printf is the ability to either return a String or a function. Copied from http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/Text-Printf.html,

printf :: (PrintfType r) => String -> r
printf fmts = spr fmts []

class PrintfType t where
    spr :: String -> [UPrintf] -> t

instance (IsChar c) => PrintfType [c] where
    spr fmts args = map fromChar (uprintf fmts (reverse args))

instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) where
    spr fmts args = \a -> spr fmts (toUPrintf a : args)

and the basic structure we can extract out is

variadicFunction :: VariadicReturnClass r => RequiredArgs -> r
variadicFunction reqArgs = variadicImpl reqArgs mempty

class VariadicReturnClass r where
   variadicImpl :: RequiredArgs -> AccumulatingType -> r

instance VariadicReturnClass ActualReturnType where
   variadicImpl reqArgs acc = constructActualResult reqArgs acc

instance (ArgClass a, VariadicReturnClass r) => VariadicReturnClass (a -> r) where
   variadicImpl reqArgs acc = \a -> variadicImpl reqArgs (specialize a `mappend` acc)

For instance:

class SumRes r where 
    sumOf :: Integer -> r

instance SumRes Integer where
    sumOf = id

instance (Integral a, SumRes r) => SumRes (a -> r) where
    sumOf x = sumOf . (x +) . toInteger

then we could use

*Main> sumOf 1 :: Integer
1
*Main> sumOf 1 4 7 10 :: Integer
22
*Main> sumOf 1 4 7 10 0 0  :: Integer
22
*Main> sumOf 1 4 7 10 2 5 8 22 :: Integer
59

Halford

@KennyTM: Do you know, whether there is a tag for polyvariadic functions? – Gotham

@FUZxxl: On this site? There is one for variadic-functions but it is C/C++-centric. – Halford

Hm... AFAIK (poly)variadic functions are a big topic in haskell programming. I don't no the guidelines, but maybe just create a tag for this purpose. (Or should I use variadic-functions)? – Gotham

@FUZxxl: If it is distinct enough from variadic functions of C, create a new tag. – Halford

I haven't the required reputation to create a new tag. – Gotham

It actually is far away from C-style polyvariadic stuff, because in C they`re unsafe, threaten as a list and builtin, in Haskell they are rather a programming technique than a real language feature, and also extremely different in their handling. – Gotham

@FUZxxl: Added [polyvariadic] in, together with [variadic-functions]. – Halford

In C it's unsafe (but then the language is, as a whole), but in C++0x variadic templates allow for type safe polyvariadic functions. – Eun

nice! your first sentence explain all! – Panfish

How does Haskell know which of the instances to use? The one that returns the integer or the one that returns a function? Is it because of the :: Integer you tacked on the end? – Masterstroke

What kind of type inference algorithm allows one to ask for the result type to specify the input type? It sounds kind of like a logic language feature. – Masterstroke

I noticed that this kind of works without the :: Integer in GHCI. Of course the type returned is weird. However I changed your implementation to append strings instead, and I had to use 2 language pragmas (TypeSynonymInstances and FlexibleInstances), but in that case, I needed :: String or GHCI complains about ambiguous instances. So how come integers don't come with ambiguous instances? – Masterstroke

@Masterstroke Integer gets chosen by GHCi's ExtendedDefaultRules mechanism, as the first type in the list (), Integer, Double which has all the instances needed. In files normally ordinary numeric defaulting is used, which has stricter requirements and so doesn't trigger here. – Cenis

@Masterstroke W.r.t. your older comment: Haskell type inference uses unification, which is also used by logic languages like Prolog. So yes, definitely related. – Cenis

Would the solution to applying a list of arguments to a polyvariadic function be to recursively apply the function while iterating over the list? – Masterstroke

@Halford Why did you call the class SumRes? – Cricket

@Cricket Summation Result. The class name isn't important, though. – Halford

I tried using Int instead of Integer and instance (SumRes r) => SumRes (Int -> r) where, I managed to compile (I had to set XFlexibleInstances flag), but when I try to run it, I have to use sumOf (1 :: Int) (2 :: Int) :: Int... Ok, maybe it's a silly comment, but I can't understand clearly what is going on. Why can't Haskell infer the type in this case? – Cricket

@Cricket Perhaps you could ask a question, but I guess it is related to the FlexibleInstances, and that a number is not a concrete type but a Num a => a. – Halford

Answer 2

KennyTM's answer is great. Below is an example of the exec process of sumOf 1 4 7 10 :: Integer to give a better illustration.

sumOf 1 4 7 10
(( \ x -> ( sumOf . (x +) . toInteger ) 1 ) 4 7 10
((sumOf . (1 + ) . toInteger) 4 ) 7 10
( sumOf 5 ) 7 10
( sumOf . (5 + ) . toInteger ) 7 10
sumOf 12 10
sumOf . (12 + ) . toInteger 10
sumof 22
id 22
22

Newmark

Answer 3

Lots of people are telling you how to create variadic functions, but I think in this case you're actually better off just using a list of type [(Char,Rational)].

Loyalist

Please look, delnan has said exactly this. Yes, I know, that this would be easier, but it's very usefull to understand, how such mechanics works by implementing it in an own program. – Gotham

Also something to note: This is the idiomatic way to write it as well. The only variadic function that I think I've used is printf; I'd expect your function to take a list. – Purser

The only other sensible usage of a variadic function I can think of (except printf) would be designing a DSL for which there is such a specific requirement. – Gambill

Answer 4

In the wiki article on variadic functions, this article was referenced. I suppose this is what printf does, but I don't understand it either. Anyway, this is certainly an overkill, especially since your arguments are all of the same type. Just put them all in one list. That's what lists are good for - an arbitary number of things of the same type. Fine, it's not very beautiful, but it will hardly be uglier than a complete polyvariadic function.

Statutable

Although this is a bit confusing, this seems to be that, what I need. – Gotham

Answer 5

I took a look at an example linked from the article that delnan referenced. After staring at it for a bit, I think I finally comprehend what is going on:

It starts with this type class:

class BuildList a r  | r-> a where
    build' :: [a] -> a -> r

That bit after the pipe (|) is a functional dependency. It says that the type represented by a can be determined by the type represented by r. In other words, you are prevented from defining two instances of the BuildList typeclass with the same r (return type), but different a.

Jumping ahead a bit to where the build' function is actually used:

> build True :: [Bool]

Since build is just calling build' with an empty list as the first parameter, this is the same as:

> build' [] True :: [Bool]

In this example, build' is clearly returning a list. Because of the functional dependency, we can only be binding to this instance of the BuildList type class:

instance BuildList a [a] where
    build' l x = reverse$ x:l

Pretty straightforward. The second example is more interesting. Expanding the definition of build, it becomes:

> build' [] True False :: [Bool]

What's the type of build' in this case? Well, the precedence rules of Haskell mean that the above could also be written like this:

> (build' [] True) False :: [Bool]

Now it becomes clear that we are passing two parameters to build' and then applying the result of that expression to a parameter with value 'False'. In other words, the expression (build' [] True) is expected to return a function of type Bool -> [Bool]. And that binds us to the second instance of the BuildList typeclass:

instance BuildList a r => BuildList a (a->r) where
    build' l x y = build'(x:l) y

In this invocation, l = [] and x = True and y = False, so the definition expands to build' [True] False :: [Bool]. That signature binds to the first instance of build', and it's fairly obvious where it goes from there.

Mcgurn

This description is extremely straightforward and very usefull. The only thing which remains unclear for me is that definition build' l x = reverse $ x:l. But in my opinion, the answer of KennyTM is more usefull, because I rather want to iterate over the parameters than having them presented as a list. – Gotham