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?

Accepted Answer

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.

Defining Functions In Relation To Other Functions Without Considering Implementation Details

Solution

Problem

Related problems