# Algebra of Programming: Chapter 1 Section 2

[update] you'll notice I corrected the title to represent the section I went through. Not clear how I got the idea this was the whole first chapter.
My wife, bless her heart, heard me talking about Algebra of Programming after it was recommended to my by the fine people in #haskell and she went out and ordered a print on demand copy. You can do the same for yourself here (Note: the price at amazon.ca is much better than amazon.com).
Since my new job is working with Ruby, my free time can be devoted to other languages/projects and I've fallen under the spell of Haskell. As an example, Unraverl's partial application parse transform for Erlang grew out of my time spent learning about Haskell, and how useful partial application can be. And as a natural sort of progression I've gotten interested in how mathematics can play a larger roll in my programming.

To further explain how this can represent any natural number consider the following possible definitions of a function that represents the value 3

When I attempted an explanation of this to my wife her question was a frustrating "Why?". Of course, "because its cool" didn't persuade her. First, it's a definition for a set of numbers which involves no actual numbers, only the structure of our new data type. We've

It should be noted here, as it confused me initially, that by providing (n + 1) or (Successor n) in the head of the function, n represents a value of one less than that which is passed in. So in the case that foldn was called with some c, some h and 6, n has the value 5 (since (5 + 1) is 6). The fun part about this is that is provides a method by which you can define functions for addition, subtraction and exponentiation (and others) in terms of foldn. From the book:

If you're a ruby developer you'll recall the Comparable mixin. Each of the methods in Comparable is defined in terms of the method < =>, and once you've done that you get skads of additional functionality for free. Similarly here we've defined one function, significantly more generic than < =>, that can be used as the basis for many other functions.

## Starting Out

I was initially a bit worried that I would be out of my depth with this book but I was also determined to do whatever was necessary to fill in the gaps of understanding. Luckily the first bit hasn't been too difficult, as most of my questions have been around terminology which were quickly answered thanks, once again, to #haskell. As an aside, if you're on the fence about which functional language to learn spend a couple minutes in haskell's irc channel. Huge thanks to heatsink, c_wraith, and others.## Recursive Data Types

The second section of the first chapter is where things started to get exciting and dense. The first example of recursive data types they provide, that make the basis for the rest of the chapter, is natural numbers (all integers >= 0). In haskell it would look something likedata Nat = Zero | Successor Nat

To further explain how this can represent any natural number consider the following possible definitions of a function that represents the value 3

-- What we would normally do three = 3 -- Another "unrolled" recursive definition using the + function three = (1 + (1 + (1 + 0))) -- Using our data type three = (Successor (Successor (Successor Zero)))

When I attempted an explanation of this to my wife her question was a frustrating "Why?". Of course, "because its cool" didn't persuade her. First, it's a definition for a set of numbers which involves no actual numbers, only the structure of our new data type. We've

*structurally*defined natural numbers. Second, because we have a recursive representation we can define recursive functions for this data type, and more generic functions for other types that are similarly recursive. The rest of the chapter is devoted to presenting the foldn function that provides a very generic way to perform operations over recursive data types like Nat.-- In terms of numbers as you would use them normally foldn c h 0 = c foldn c h (n + 1) = h (foldn c h n) -- In terms of our Nat data type foldn c h Zero = c foldn c h ( Successor n ) = h (foldn c h n)

It should be noted here, as it confused me initially, that by providing (n + 1) or (Successor n) in the head of the function, n represents a value of one less than that which is passed in. So in the case that foldn was called with some c, some h and 6, n has the value 5 (since (5 + 1) is 6). The fun part about this is that is provides a method by which you can define functions for addition, subtraction and exponentiation (and others) in terms of foldn. From the book:

-- Addition plus m n = foldn m Successor n -- Subtraction mult m n = foldn 0 (plus m) n -- Exponentiation expn m n = foldn 1 (mult m) n -- The more point free ("point-less"?) version, would be without the n's.

If you're a ruby developer you'll recall the Comparable mixin. Each of the methods in Comparable is defined in terms of the method < =>, and once you've done that you get skads of additional functionality for free. Similarly here we've defined one function, significantly more generic than < =>, that can be used as the basis for many other functions.