How To Negate A Function?

Question

This might be a really dumb question but..

I have written two quick functions that check if three numbers are in descending or ascending order.

IE 2 3 5 would be true for ascending and false for descending.

1 5 3 would be false for both

I need to make a third function that will work by only calling these first two. I am using GHCi. This third function sees if the numbers are not in any order like the second example above

So it would be like

let newfunction = (not)Ascending && (not)Descending

How do I do this though? The /= doesn't work for me

Answer 1

There is actually a not function for booleans, but as always you have to get the types right. Say your existing functions have the following type:

ascending :: (Ord a) => [a] -> Bool
ascending (x1:x2:xs) = x1 <= x2 && ascending (x2:xs)
ascending _ = True

descending :: (Ord a) => [a] -> Bool
descending (x1:x2:xs) = x1 >= x2 && descending (x2:xs)
descending _ = True

Requiring both means that the lists have to be equal, because that's the only way for them to be both ascending and descending in the sense I have defined above:

both xs = ascending xs && descending xs

To invert booleans there is the not function:

not :: Bool -> Bool

Then being neither is expressed with this function:

neither xs = not (ascending xs || descending xs)

This is, of course, the same as:

neither xs = not (ascending xs) && not (descending xs)

You can use applicative style with the reader functor to make this look a bit more pleasing:

import Control.Applicative

both    = liftA2 (&&) ascending descending
neither = not . liftA2 (||) ascending descending

Or alternatively:

neither = liftA2 (&&) (not . ascending) (not . descending)

More: This gives rise to a notion of predicates:

type Predicate a = a -> Bool

A predicate is a boolean function. The two functions ascending and descending defined above are predicates. Instead inverting booleans, you can invert predicates:

notP :: Predicate a -> Predicate a
notP = (not .)

And instead of conjunction and disjunction on booleans, we can have them on predicates, which allows writing composite predicates more nicely:

(^&^) :: Predicate a -> Predicate a -> Predicate a
(^&^) = liftA2 (&&)

(^|^) :: Predicate a -> Predicate a -> Predicate a
(^|^) = liftA2 (||)

This lets us write both and neither really nicely:

both = ascending ^&^ descending

neither = notP ascending ^&^ notP descending

The following law holds for predicates,

notP a ^&^ notP b = notP (a ^|^ b)

so we can rewrite neither even more nicely:

neither = notP (ascending ^|^ descending)

Answer 2

ertes' answer can be generalized further by introducing a type class for Boolean algebras:

import Control.Applicative (liftA2)

-- | A class for Boolean algebras.
class Boolean a where
    top, bot :: a
    notP :: a -> a
    (^&^), (^|^) :: a -> a -> a

    -- Default implementations for all methods
    top = notP bot
    bot = notP top
    a ^&^ b = notP (notP a ^|^ notP b)
    a ^|^ b = notP (notP a ^&^ notP b)

instance Boolean Bool where
    top   = True
    bot   = False
    notP  = not
    (^&^) = (&&)
    (^|^) = (||)

instance Boolean r => Boolean (a -> r) where
    top = const top
    bot = const bot
    notP = (notP .)
    (^&^) = liftA2 (^&^)
    (^|^) = liftA2 (^|^)

{- 
-- We can actually generalize this to any Applicative, but this requires
-- special compiler options: 
instance (Applicative f, Boolean a) => Boolean (f a) where
    top = pure top
    bot = pure bot
    notP = fmap notP
    (^&^) = liftA2 (^&^)
    (^|^) = liftA2 (^|^)
-}

This is similar to the standard Monoid class—a Boolean is in fact two monoids (top with ^&^ and bot with ^|^) related by the DeMorgan laws (the default definitions for ^&^ and ^|^). But now the operators work not just on one-argument predicates, but on arbitrary arity; for example, now we have (<=) == ((<) ^|^ (==)).

In addition, there are other useful "base" instances of Boolean; for example, machine-word types can be made into Boolean instances in terms of bitwise operations.