31

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
Improve this question
1
  • 3
    consider adding .NET tag to Interesting Tags on the right panel ;) Commented Mar 15, 2010 at 18:55

4 Answers 4

Reset to default
42

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

what a delightful and useful idea to have a seemingly free in (Predicate b) => Predicate (a -> b)...
Using SEC notation, you can also write your instance for functions as complement = result complement which is equivalent to Norman's "mysterious" version, written to look less mysterious / more regular.
Does this rely on the function being homogeneous? For example, how would I use type classes to define a "comparator" function of 1..n tuples, that gives the result of uncurry compare $ Tm for the first tuple Tm where the result is not EQ?
@Dominic: I don't think I understand your question. But it works for any function returning Bool, no matter what the type of the arguments. Arguments of heterogeneous types are fine. For example, given member :: Eq a -> a -> [a] -> Bool, complement member does just what you would expect.
Right; I didn't explain that well. Say I want to do "arbitrary arity with type classes" but the function defined in the typeclass isn't a -> a, but does something else. A trivial example is an arbitrary arity function which counts its arguments. I apparently can't write this: class Count a where count :: a -> Int count _ = 1 instance (Count b) => Count (a -> b) where count _ = 1+ (count (undefined :: b)) With the intended effect that count 1 => 1 and count 1 'a' Nothing => 3. GHC complains that b is ambiguous in that last line.
41

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.

Improve this answer

1 Comment

I like this explanation of SECs. For more, see the blog post. Small correction: I call not an "editor" and result, left, second etc the "editor combinators", because they transform editors an they compose.
12

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.

Improve this answer

1 Comment

Or as result.result, result.result.result, etc. And you can intersperse other SECs like first, second & fmap. I suspect it's simply the infix-ness of function composition notation that keeps people from thinking of it as unary, and hence composable in this powerful way.
9

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.

Improve this answer

1 Comment

It works in ghci too. let g::(Ord a) => (a->a->Bool); g = n f

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.