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

Question

I am trying to create a function that receives a variational function as an argument, i.e.

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

How can i do this?

I read about polyvariadic functions , and I am sure that Oleg has already done this , however I have lost the attempt to apply the template to a function with a variational function as an argument. Especially Oleg’s approach seems to work only with extensions in Glasgow, and I want the solution to work in pure Haskell 98 (e.g. Text.Printf ).

The reason why I ask is because I am trying to create a function that takes a logical function as an argument and checks if it is a tautology, i.e.

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

so that you can enter:

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

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

Answer 1

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

We are trying to write a function that takes a variational argument and returns Bool , so we will 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 variational function. In this case, Bool .

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

The key part is the following instance for functions that take a Bool argument, and the type of the return type is some type from our class. Thus, this instance will be applied several times if the function takes several 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 this method requires FlexibleInstances due to the Bool in the second instance. To do the same with pure Haskell 98, we will need to use a type variable with a limited constraint. For example, we can use Bounded and Enum (there are instances for Bool ), or you can create your own class that allows you to build the corresponding inputs.

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

And you're done. Try:

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