How to compose `not` with a function of arbitrary arity?

When I have some function of type like

f :: (Ord a) => a -> a -> Bool
f a b = a > b

I should like make function which wrap this function with not.

e.g. make function like this

g :: (Ord a) => a -> a -> Bool
g a b = not $ f a b

I can make combinator like

n f = (\a -> \b -> not $ f a b)

But I don't know how.

*Main> let n f = (\a -> \b -> not $ f a b)
n :: (t -> t1 -> Bool) -> t -> t1 -> Bool
Main> :t n f
n f :: (Ord t) => t -> t -> Bool
*Main> let g = n f
g :: () -> () -> Bool

What am I doing wrong?

And bonus question how I can do this for function with more and lest parameters e.g.

t -> Bool
t -> t1 -> Bool
t -> t1 -> t2 -> Bool
t -> t1 -> t2 -> t3 -> Bool

Solution 1:

Actually, doing arbitrary arity with type classes turns out to be incredibly easy:

module Pred where

class Predicate a where
  complement :: a -> a

instance Predicate Bool where
  complement = not

instance (Predicate b) => Predicate (a -> b) where
  complement f = \a -> complement (f a)  
  -- if you want to be mysterious, then
  -- complement = (complement .)
  -- also works

ge :: Ord a => a -> a -> Bool
ge = complement (<)

Thanks for pointing out this cool problem. I love Haskell.

Solution 2:

Unless you want to go hacking around with typeclasses, which is better left for thought experiments and proof of concept, you just don't generalize to multiple arguments. Don't try.

As for your main question, this is most elegantly solved with Conal Elliott's semantic editor combinators. A semantic editor combinator is a function with a type like:

(a -> b) -> F(a) -> F(b)

Where F(x) is some expression involving x. There are also "contravariant" editor combinators which take a (b -> a) instead. Intuitively, an editor combinator selects a part of some larger value to operate on. The one you need is called result:

result = (.)

Look at the type of the expression you're trying to operate on:

a -> a -> Bool

The result (codomain) of this type is a -> Bool, and the result of that type is Bool, and that's what you're trying to apply not to. So to apply not to the result of the result of a function f, you write:

(result.result) not f

This beautifully generalizes. Here are a few more combinators:

argument = flip (.)     -- contravariant

first f (a,b) = (f a, b)
second f (a,b) = (a, f b)

left f (Left x) = Left (f x)
left f (Right x) = Right x
...

So if you have a value x of type:

Int -> Either (String -> (Int, Bool)) [Int]

And you want to apply not to the Bool, you just spell out the path to get there:

(result.left.result.second) not x

Oh, and if you've gotten to Functors yet, you'll notice that fmap is an editor combinator. In fact, the above can be spelled:

(fmap.left.fmap.fmap) not x

But I think it's clearer to use the expanded names.

Enjoy.

Solution 3:

Your n combinator can be written:

n = ((not .) .)

As for your bonus question, the typical way around would be to create several of these:

lift2 = (.).(.)
lift3 = (.).(.).(.)
lift4 = (.).(.).(.).(.)
lift5 = (.).(.).(.).(.).(.)

etc.

Solution 4:

Re: What am I doing wrong?:

I think your combinator is fine, but when you let-bind it at the top level, one of Haskell's annoying 'default rules' comes into play and the binding isn't generalized:

Prelude> :ty (n f)
(n f) :: (Ord t) => t -> t -> Bool
Prelude> let g = n f
Prelude> :ty g
g :: () -> () -> Bool

I think you may be getting clobbered by the 'monomorphism restriction' as it applies to type classes. In any case, if you get out of the top-level loop and put things into a separate file with an explicit type signature, it all works fine:

module X where

n f = (\a -> \b -> not $ f a b)
f a b = a > b

g :: Ord a => a -> a -> Bool
g = n f

Bonus question: to do this with more and more type parameters, you can try playing scurvy tricks with the type-class system. Two papers to consult are Hughes and Claessen's paper on QuickCheck and Ralf Hinze's paper Generics for the Masses.