# Order Matters

Previous: 6-by-6 Sudoku Solver

Next: More Hemingway

I’m learning me a Haskell, very slowly, and I just wanted to share a little anecdote about function order and infinite lists that I thought was funny.
It has to do with the interplay between `filter`

and `takeWhile`

.

In Chapter 6 we learn how to map and filter over lists. We see a short example of a one-liner that will sum the odd squares smaller than 10,000.

Everything seems to work fine. (I can tell, because I know the sum of the odd squares smaller than 10,000 off the top of my head.) Let’s capitalize on our small victory by defining this as a function.

Great!
`funnySum`

is now a general function that takes a list of integers and returns an integer.
Let’s feed it some other lists of integers.
How about every number that’s 3 modulo 4?

Now, let’s intentionally feed it a list without any odd numbers. We should just get the sum of the empty list (namely 0) right?

Nothing gets printed.
The program is looping forever!
What’s going on?
The answer has to do with the order in which we apply the two condition-checking mechanisms, `filter odd`

and `takeWhile (<10000)`

.

Our `funnySum`

is defined using `takeWhile (<10000) . filter odd`

.
With that definition, `funnySum [2,4..]`

looks for the first odd square it encounters, checks to see if it’s less then 10000, then adds it to the running sum.
Therein lies the problem: `funnySum`

never encounters an odd square, so it can’t advance to the step where the odd square is checked against `(<10000)`

.

Fortunately, this is easy to fix.
We’ll define a new function, `funnySum'`

that will still solve the problem but will also be more flexible with allowable inputs.
All we need to do is swap the order of `takeWhile (<10000)`

and `filter odd`

.

We still answer the original questions correctly, and we’re able to evaluate the sum of all the odd members of an infinite list of even numbers. Success!

# Afterward

I originally thought that `filter odd . takeWhile (<10000)`

and `takeWhile (<10000) . filter odd`

would always return the same results whenever both of them returned a finite list.
However, this is simply not the case, because `filter odd`

might remove a list element that would otherwise trigger `takewhile (<10000)`

.

Example:

Since they are different function, neither is better than the other. Use the one that produces what you want for your particular piece of code.

The most general setting where `filter odd . takeWhile (<10000)`

and `takeWhile (<10000) . filter odd`

agree whenever each returns a finite list is when you know that the input list will be monotonically increasing.
In that case, use `filter odd . takeWhile (<10000)`

, because the set of lists for which it terminates properly includes the set of lists for which `takeWhile (<10000) . filter odd`

terminates.

# Acknowledgement

Thanks to Miran Lipovača for not only writing a wonderful, succinct, smoothly conversational textbook for learning Haskell, but also for making it freely available on the internet.

Previous: 6-by-6 Sudoku Solver

Next: More Hemingway