Archive for June, 2007

Generalizing recursion on integers

I thought I’d post a brief answer to the question I raised in my last post, which was “is there an analogous higher-order function [like foldr] for recursion on numbers?”

As I pointed out, you can define product using foldr, like this:

product = foldr (*) 1

What I wanted is another function, say foldrNum, that would allow me to define factorial using the same idea:

factorial = foldrNum (*) 1

As it turns out, all I need to do is make some slight modifications to the foldr definition, which looks like this:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr op v []     = v
foldr op v (x:xs) = op x (foldr op v xs)

I’ll keep foldrNum general enough so that, like foldr, it can return a value of any type (b), but unlike foldr, which can process a list of any type (a), I think it’s essential to the idea of foldrNum that it only operate on a non-negative integer, which is what the recursion is based on. First, I’ll show the definition of foldrNum I came up with. Then I’ll compare it line-by-line with foldr so that we can see exactly what’s the same and what’s different.

Here’s foldrNum:

foldrNum           :: (Int -> b -> b) -> b -> Int -> b
foldrNum op v 0     = v
foldrNum op v (n+1) = op (n+1) (foldrNum op v n)

The similarities are obvious, but I like to make things as obvious as possible. First, the types of each function:

foldr               :: (a   -> b -> b) -> b -> [a] -> b
foldrNum            :: (Int -> b -> b) -> b -> Int -> b

Now, the base case:

foldr    op v []     = v
foldrNum op v 0      = v

Finally, the recursive case:

foldr    op v (x:xs) = op x     (foldr    op v xs)
foldrNum op v (n+1)  = op (n+1) (foldrNum op v n)

The natural question arising from this is “How do I generalize foldr and foldrNum, since they’re so much alike?” Joshua Ball anticipated that question in his comment on my last post, although I confess I haven’t fully wrapped my head around his solution yet.

I think this is enough for today. So many possible directions to go in. I must content myself with one small piece at a time. :-)

Comments (3)

Learning Haskell

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!”

Comments (2)

How bizarre

A Vim/Dvorak tutorial. First, QWERTY is designed to slow typists down (so early typewriters wouldn’t jam). Then, Vi was designed to make keystroke editing commands easy on QWERTY keyboards. Meanwhile, the Dvorak keyboard was designed to enable faster typing and prevent carpal tunnel.

How bizarre then to see a tutorial for Vi keystrokes on a Dvorak keyboard:

Vim/Dvorak Tutorial (PDF)

Just look at where those up/down/left/right arrow keys are.

I have to wonder if this person really uses Vi. Maybe the joke’s on me. :-)

The original one it’s based on is quite cool though.

Comments off