Defining Functions In Relation To Other Functions Without Considering Implementation Details

Question

I have written a function called 'oddOf' that correctly determines whether or not a given value has an odd number of presences in a list. It is defined like so:

oddOf :: (Eq a) => a -> [a] -> Bool
oddOf value list = oddOf' value list False
    where oddOf' val (x:xs) acc = if x == val
                                  then oddOf' val xs (not acc)
                                  else oddOf' val xs acc
          oddOf'  _     _   acc = acc

I would like to write a function that determines whether or not a given value has an even number of presences in a list. When presented with binary choices such as these, it is the best practice to implement one and define the other as 'not its complement'. With that in mind, I tried out the definition:

evenOf = not oddOf

To me, that looks like a reasonable partially-applied function, but it is not valid Haskell code. What is it about the language that I need to understand better? What is the elegant way to define evenOf that I am looking for?

Answer 1

It's good practice to be thinking about code reuse this way, and I'll get to that, but first:

Using function composition to write more neatly

Can I first point out as an aside that I would define your oddOf function more simply using existing functions:

oddOf :: Eq a -> a -> [a] -> Bool
oddOf value list = odd . length . filter (== value) $ list

f $ x = f x but has low precedence, so that's a neater way of writing (not . even . length . filter (== value) ) list.

This works by composing functions; we take the list and filter it so we get just the ones that equal the value, using partial application of (==) in the form of an 'operator section' (== value) :: Eq a => a -> Bool. Next we find the length of that, check if it's even, then finally negate the answer with not. This hints at a concise way of writing evenOf:

evenOf :: Eq a -> a -> [a] -> Bool
evenOf value list = even . length . filter (== value) $ list

In fact, since the prelude defines odd as not . even it would be very slightly simpler to start with evenOf and define oddOf from that.

Why not . oddOf isn't what you wanted

Looking at types, you have

not :: Bool -> Bool
oddOf :: Eq a => a -> [a] -> Bool
(.) :: (b -> bb) -> (a -> b) -> a -> bb  -- function composition

Now -> associates to the right, which means that really,

oddOf :: Eq a => a -> ([a] -> Bool)

Secretly, that means that Haskell functions only ever take one argument! (What we think of as functions that take more than one argument are actually functions that take one argument then return a function that'll take another, etc...) Unfortunately that means we can't match the types up with (.) directly, because we'd need b to be Bool, not [a] -> Bool.

Simple solutions to your problem

OK, sorry I took a while to get to the answer you wanted, but I think that was all worth saying.

• Simple solution 1 is writing evenOf with function composition as I showed you above.

  oddOf  value list =  odd . length . filter (== value) $ list
  evenOf value list = even . length . filter (== value) $ list
  

• Simple solution 2 is writing evenOf directly from oddOf by supplying all the arguments:

  evenOf value list = not $ oddOf value list
  oddOf  value list = odd . length . filter (== value) $ list
  

• Simple solution 3 is writing evenOf value by composing not with oddOf value

  The only problem with not.oddOf was that oddOf doesn't return a Bool directly, it returns a [a]->Bool. We can fix this by supplying one of the arguments. Notice that oddOf value has type Eq a => [a] -> Bool so we can compose that with not, because it does return a Bool:

  evenOf value      = not . oddOf value
  oddOf  value list = odd . length . filter (== value) $ list
  

• Simple solution 4 is putting together simple solutions 1 and 2 to write oddOf using evenOf instead:

  oddOf  value list = not $ evenOf value list
  evenOf value list = even . length . filter (== value) $ list
  

  (You could, of course, do the same thing to simple solutions 1 and 3.)

Awesome brain-changing ways to solve the problem

Every Haskell programmer should read Conal Elliott's excellent semantic editor combinators webpage/article.

In particular, you should read it since it answers your question title "Defining Functions In Relation To Other Functions Without Considering Implementation Details" in a very general way; "Semantic Editor Combinators" is Conal's phrase for exactly that concept.

The main idea is that you can edit a function after it's written by writing a sort of path to the value you want to change in brackets, the function you want to apply at that point, then the original function. In this case, you need to apply not to the result (::Bool) of the result (::Eq a => [a]->Bool) of the original function (:: Eq a => a -> [a] -> Bool).

So if you want to edit the result of the result with not, you do:

oddOf = (result.result) not evenOf
evenOf value list = even . length . filter (== value) $ list

Conal Elliott defines result = (.) because it's conceptually easier, but you could define

oddOf = ((.).(.)) not evenOf
evenOf value list = even . length . filter (== value) $ list

directly if you prefer.

If you needed to change more :: a -> b -> [a] -> [b] -> Bool, you could use

less = (result.result.result.result) not more

or

less = ((.).(.).(.).(.)) not more

Using the same idea, you can change inside a list, part of a pair, one of the arguments,...
Read the paper for a deeper and fuller explanation.