Search code examples
functionhaskellfunctional-programmingcomposition

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

  • 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.