How to write a Haskell function that takes a variadic function as an argument

Question

I'm trying to create a function that gets a variadic function as an argument, i.e.

func :: (a -> ... -> a) -> a

how can I accomplish this?

I've read about polyvariadic functions and I'm sure that Oleg already did it, however I'm lost trying to apply the pattern on a function with a variadic function as an argument. Especially Olegs approach seems to work with glasgow extensions only and I want the solution to work in pure Haskell 98 (like Text.Printf does).

The reason that I ask is that I'm trying to build a function which takes a boolean function as an argument and checks whether it is a tautology, i.e.

isTautology :: (Bool -> ... -> Bool) -> Bool

so that one could type:

isTautology (\x -> x && not x)
isTautology (\x y -> x && y || not y)

My problem is that I keep reading about the trick was to make the return type a type variable (so that it can be the result or another function), but my return type is fixed (Bool).

Is there a specific reason you want to stick with Haskell 98? GHC is practically the only seriously maintained Haskell compiler these days. — Dan Burton
@DanBurton I'm actually a teaching assistant and neither does the curriculum allow me to introduce fancy stuff nor do I think that it is helpful for the students (first semester) to dig into extensions of haskell 98. I'm currently preparing this as an exercise. — scravy
By all means stick to the standard, but go with the times and stick to Haskell2010. — Daniel Fischer
@DanielFischer There is nothing in Haskell2010 which would help me too much in this case, or do I miss something? (as to my understanding Haskell2010 is mostly about Syntax and standardizing de facto behavior of hugs and GHC?) — scravy
Yes, H2010 vs H98 doesn't make a difference for this problem. But H98 doesn't have hierarchical modules, and has (n+k)-patterns. As of GHC 7.2, a package or programme cannot depend on haskell98 and base together (at least not without contortions). NPlusKPatterns are disabled by default since GHC 7.0. Sticking to H98 leads to unpleasant experiences for the learners. — Daniel Fischer

hammar hammar · Accepted Answer · 2011-12-02T09:40:47

The trick is to make a type class for which you will define an instance for functions, and an instance for the return type. The fact that it's a Bool is not a problem at all.

We're trying to write a function which takes a variadic argument and returns a Bool, so we'll define a type class with such a function.

class Stmt a where
    tautology :: a -> Bool

Next, we define an instance for the return type of the variadic function. In this case, that's Bool.

-- A Bool is a tautology if it's True.
instance Stmt Bool where
    tautology = id

The key part is the next instance for functions that take a Bool argument, and whose return type is some type from our class. That way, this instance will be applied multiple times if a function takes multiple arguments.

-- A function is a tautology if it always returns a tautology.
instance Stmt b => Stmt (Bool -> b) where
    tautology f = tautology (f True) && tautology (f False)

Writing it this way requires FlexibleInstances because of the Bool in the second instance head. To do the same with pure Haskell 98, we'll need to use a suitably-constrained type variable instead. We can for example use Bounded and Enum (there are instances for both for Bool), or you can make your own class that will let you construct the appropriate inputs.

instance (Enum a, Bounded a, Stmt b) => Stmt (a -> b) where
    tautology f = all (tautology . f) [minBound .. maxBound]

And we're done. Let's try it out:

> tautology $ \x y -> (not x && not y) == not (x && y)
False
> tautology $ \x y -> (not x && not y) == not (x || y)
True

How to write a Haskell function that takes a variadic function as an argument

1 Answers