I'm going to take your question to mean, more specifically, "if I already program in an imperative language like C or Java, how do I adjust my thinking for functional programming?" Using your problem as an example, I'm going to spend my Saturday morning answering this question in long form. I'll trace the evolution of a functional programmer through three stages, each a successively higher plane of zen - 1) thinking iteratively; 2) thinking recursively; and 3) thinking lazily.
Part I - Thinking Iteratively
Let's say I'm programming in C and I can't or won't use recursion - perhaps the compiler does not optimize tail recursion, and a recursive solution would overflow the stack. So I start thinking about what state I need to maintain. I imagine a little machine crawling over the input. It remembers if it is searching for an increasing or a decreasing sequence. If it hasn't decided yet, it does so based on the current input, if it can. If it finds input headed in the wrong direction, it terminates with zigzag=true. If it reaches the end of the input, it terminates with zigzag=false.
int
zigzag(int *data, int n)
{
enum {unknown, increasing, decreasing} direction = unknown;
int i;
for (i = 1; i < n; ++i)
{
if (data[i] > data[i - 1]) {
if (direction == decreasing) return 1;
direction = increasing;
}
if (data[i] < data[i - 1]) {
if (direction == increasing) return 1;
direction = decreasing;
}
}
/* We've made it through the gauntlet, no zigzagging */
return 0;
}
This program is typical of C programs: it is efficient but it is difficult to prove that it will do the right thing. Even for this simple example, it's not immediately obvious that this can't get stuck in an infinite loop, or take a wrong turn in its logic somewhere. Of course, it gets worse for more complicated programs.
Part II - Thinking Recursively
I find that the key to writing readable programs in the spirit of functional languages (as opposed to just trying to morph an imperative solution into that language) is to focus on what the program should calculate rather than on how it should do it. If you can do that with enough precision - if you can write the problem out clearly - then most of the time in functional programming, you're almost at the solution!
So let's start by writing out the thing to be calculated in more detail. We want to know if a list zigzags (i.e. decreases at some point, and increases at another). Which lists meet this criterion? Well, a list zigzags if:
- it is more than two elements long AND
- it initially increases, but then decreases at some point OR
- it initially decreases, but then increases at some point OR
- its tail zigzags.
It's possible to translate the above statements, more or less directly, into a Scheme function:
(define (zigzag xs)
(and (> (length xs) 2)
(or (and (initially-increasing xs) (decreases xs))
(and (initially-decreasing xs) (increases xs))
(zigzag (cdr xs)))))
Now we need definitions of initially-increasing, initially-decreasing, decreases, and increases. The initially- functions are straightforward enough:
(define (initially-increasing xs)
(> (cadr xs) (car xs)))
(define (initially-decreasing xs)
(< (cadr xs) (car xs)))
What about decreases and increases? Well, a sequence decreases if it is of length greater than one, and the first element is greater than the second, or its tail decreases:
(define (decreases xs)
(letrec ((passes
(lambda (prev rest)
(cond ((null? rest) #f)
((< (car rest) prev)
#t)
(else (passes (car rest) (cdr rest)))))))
(passes (car xs) (cdr xs))))
We could write a similar increases function, but it's clear that only one change is needed: < must become >. Duplicating so much code should make you uneasy. Couldn't I ask the language to make me a function like decreases, but using > in that place instead? In functional languages, you can do exactly that, because functions can return other functions! So we can write a function that implements: "given a comparison operator, return a function that returns true if that comparison is true for any two successive elements of its argument."
(define (ever op)
(lambda (xs)
(letrec ((passes
(lambda (prev rest)
(cond ((null? rest) #f)
((op (car rest) prev)
#t)
(else (passes (car rest) (cdr rest)))))))
(passes (car xs) (cdr xs)))))
increases and decreases can now both be defined very simply:
(define decreases (ever <))
(define increases (ever >))
No more functions to implement - we're done. The advantage of this version over the C version is clear - it's much easier to reason that this program will do the right thing. Most of this program is quite trivial with all the complexity being pushed into the ever function, which is a quite general operation that would be useful in plenty of other contexts. I am sure by searching one could find a standard (and thus more trustworthy) implementation rather than this custom one.
Though an improvement, this program still isn't perfect. There's lots of custom recursion and it's not obvious at first that all of it is tail recursive (though it is). Also, the program retains faint echos of C in the form of multiple conditional branches and exit points. We can get an even clearer implementation with the help of lazy evaluation, and for that we're going to switch languages.
Part III - Thinking Lazily
Let's go back to the problem definition. It can actually be stated much more simply than it was in part II - "A sequence zigzags (i.e. is non-sorted) if it contains comparisons between adjacent elements that go in both directions". I can translate that sentence, more or less directly, into a line of Haskell:
zigzag xs = LT `elem` comparisons && GT `elem` comparisons
Now I need a way to derive comparisons, the list of comparisons of every member of xs with its successor. This is not hard to do and is perhaps best explained by example.
> xs
[1,1,1,2,3,4,5,3,9,9]
> zip xs (tail xs)
[(1,1),(1,1),(1,2),(2,3),(3,4),(4,5),(5,3),(3,9),(9,9)]
> map (\(x,y) -> compare x y) $ zip xs (tail xs)
[EQ,EQ,LT,LT,LT,LT,GT,LT,EQ]
That's all we need; these two lines are the complete implementation -
zigzag xs = LT `elem` comparisons && GT `elem` comparisons
where comparisons = map (\(x,y) -> compare x y) $ zip xs (tail xs)
and I'll note that this program makes just one pass through the list to test for both the increasing and decreasing cases.
By now, you have probably thought of an objection: isn't this approach wasteful? Isn't this going to search through the entire input list, when it only has to go as far as the first change of direction? Actually, no, it won't, because of lazy evaluation. In the example above, it calculated the entire comparisons list because it had to in order to print it out. But if it's going to pass the result to zigzag, it will only evaluate the comparisons list far enough to find one instance of GT and one of LT, and no further. To convince yourself of this, consider these cases:
> zigzag $ 2:[1..]
True
> zigzag 1:[9,8..]
True
The input in both cases is an infinite list ([2,1,2,3,4,5..] and [1,9,8,7,6,5...]). Try to print them out, and they will fill up the screen. But pass them to zigzag, and it will return very quickly, as soon as it finds the first change in direction.
A lot of the difficultly in reading code comes from following multiple branches of control flow. And a lot of those branches are really efforts to avoid calculating more than we need to. But much of the same thing can be achieved with lazy evaluation, allowing the program to be both shorter and truer to the original question.
