Evan Lenz

I’m writing this post as a way of moving myself forward at least one notch through Graham Hutton’s Programming in Haskell, which I’ve been very slowly, occasionally working through. I’m in the middle of chapter 7 right now.

The thing that slows me down (apart from having 3 kids at home including a baby) is that I’m distracted by the learning process itself. I don’t want to too easily forget the false or imperfect theories that I form along the way. A teacher’s job is to help bridge the gap between imperfect models in the student’s mind and models that are more useful and effective. But the only way they can do that is to be familiar with such inaccurate models, as well as to value them as important stages of the student’s learning (rather than reject them out of hand as is the modus operandi of schools today, but I digress). I may want to teach this stuff some day, and this is my only chance to observe the learning process first-hand, at least as a beginner. I need to keep a log of my learning, or at least parts of it, in order to keep me moving forward with the assurance that my intermediate stages of learning will not be forgotten forever.

Quick disclaimer: This post is not the first of a series of Haskell posts, at least not any planned series. I hereby give myself permission to not post on Haskell ever again, or for that matter, to drop it in favor of learning something else (although given how much I keep getting drawn back to it, I’m pretty sure that won’t happen).

Recursion patterns

In chapter 6 (on recursion), I noticed there are basically two things you could base recursion off of, or two things to “recurse” on:

• a list, or
• an integer

Recursion on an integer

The basic pattern for recursion on an integer is evident in the definition of the factorial function:

factorial 0     = 1
factorial (n+1) = (n+1) * factorial n

The factorial of 0 is just 1 (the identity for multiplication). The factorial of a positive integer (represented by (n+1)) is that integer ((n+1)) multiplied by the factorial of one less than that integer (n). The function is invoked recursively until the numbers run out and the termination case is reached (an argument of 0).

Recursion on a list

The basic pattern for recursion over a list is evident in the definition for the product function:

product []     = 1
product (n:ns) = n * product ns

The product of an empty list is just 1 (again, the identity for multiplication). The product of a non-empty list (represented by (n:ns)) is the result of multiplying the head of the list (n) times the product of the tail of the list (ns). The function is invoked recursively until the list runs out and the termination case is reached (an empty-list argument).

Capturing the list-recursion pattern

I’m only partly through chapter 7 (on higher-order functions), but I’ve now been introduced to the foldr library function, which captures the pattern evident in the product function, which uses recursion over a list. Here it is:

f []     = v
f (x:xs) = x ⊕ f xs

The v stands for some base value (which was 1 in the product function). The circled-plus symbol (⊕) stands for some operator (which was * in the product function). The foldr function takes those two variables (a base value and an operator) and automatically constructs a function for you that does the above. So you can now define product more succinctly (and without using explicit recursion):

product ns = foldr (*) 1 ns

Or even more succinctly, and thanks to Haskell’s function currying:

product = foldr (*) 1

What about capturing the number recursion pattern?

The open question in my mind is: is there an analogous higher-order function for recursion on numbers?

What wasn’t explicitly mentioned in the book is the idea that an integer can be thought of as representing a list of numbers, starting at that number and counting down to 1. If that’s the case, then I could just use foldr for recursion on a number, provided that I first turn that number into a list of numbers counting down to 1.

Using that idea, here’s another way to define factorial:

factorial n = foldr (*) 1 [n,(n-1)..1]

Of course, in the case of multiplication, the order of the list of arguments doesn’t matter, so the list doesn’t have to count down. It could start at 1 and count up to the integer instead:

factorial n = foldr (*) 1 [1..n]

Anyway, that’s where I’m at with these half-baked observations. I’m sure I’ll find better or more appropriate abstractions as well as more interesting insights. I’ll be able to look back at this post and say “Oh, what you want is the ____ function!”