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

I'm afraid that not oddOf isn't a reasonable partially-applied function. It's an application of not to oddOf.

not has type Bool -> Bool; it takes a single Bool argument and returns a Bool. oddOf isn't a Bool, so not can't be applied to it. But what you want is not to apply not to oddOf itself, but to apply not to the result of applying oddOf to two arguments.

The most direct way to do what you want is to write something like this:

evenOf value list = not $ oddOf value list

This is theoretically a little less direct and abstract than it could be, because rather than just defining evenOf by its relationship to oddOf directly you're "manually" wiring up the inputs to evenOf to the inputs of oddOf and then post-processing its result. A point-free version, such as Ziyao Wei's suggested:

evenOf = ((not .) .) oddOf

more directly states that relationship, freeing the reader from having to verify that the 2 arguments to evenOf are simply passed to oddOf in the same order and not used for any other purpose. But generally it takes quite a deep familiarity with Haskell to find that version clearer (otherwise you have to instead verify what exactly the nested composition sections do to see the "directly stated" relationship). So if you're more comfortable with explicitly naming and "wiring" the arguments, that's probably the elegant way you're looking for.

Answer 2

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.

Answer 3

Your example code is actually calling the not function with oddOf as parameter. The (.) function is used to compose 2 functions but only when you have binary functions i.e functions that take a single parameter and return a value, which ofcourse is not the case with oddOf because it is a -> [a] -> Bool.

We can make oddOf a binary function if we can make it (a, [a]) -> Bool. This can be done using uncurry. The other function called curry does the opposite i.e it will make (a,[a]) -> Bool back to a -> [a] -> Bool.

We can use these curry uncurry functions to achieve what we want:

evenOf :: (Eq a) => a -> [a] -> Bool
evenOf = curry $ not . (uncurry oddOf)

Answer 4

In addition to the other options, and to help you understand what's going on, recognize that if you use a tuple for your oddOf arguments, it will work.

let oddOf (value, list) = ...
let evenOf = not . oddOf

This is because oddOf is now a function that returns a Bool. With untupled arguments, then it's a function that returns a function that returns a Bool, which is different.

So now not oddOf still doesn't work because we're not partially applying here--not is Bool -> Bool; there is no partial application possible there. Instead we're going back to the old mathematical function composition—f(g(x)) -> (f.g)(x). Here g is oddOf and f is not. Then the Haskell representation is as above.

The basic premise of your problem all comes down to my second paragraph—you've got a function that returns a function. All the answers here present some way of converting that into a function that returns a Bool, and then doing function composition with not. Try reading the answers all in that light and it should give you a better understanding. In particular look at AndrewC's simple solution #3 with this in mind.