Peano's Axioms IV: Advanced Functions and Integers

So here's the last installment, we'll make use of all the infrastructure we've build up to define primality, and associated functions like, a divisor function, totient, and sigma and whatever else I can come up with.

as always this is a literate source, save to Peano3.lhs and make sure you have the previous posts, execute with:

$> ghci Peano3.lhs

and have fun.

No big preambles this time, Lets go.

> module Peano3 where
> import Peano2
> import Data.List

First, all this stuff will boil down to prime numbers. So lets come up with a way to test if a number is prime or not.

An easy method is to create a seive of all prime numbers, then our isPrime function is just a search on the list, is it the fastest method in the world? Not really, does it work? You bet it does.

> natPrimes :: [Nat]
> natPrimes = sieve [S(S(Z))..]

> sieve :: [Nat] -> [Nat]
> sieve [] = []
> sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]

Awesome, we all know about Haskell's powerful List Comprehensions. Now lets implement that simple linear search on the list.

> isPrime :: Nat -> Bool
> isPrime x = isPrime' x natPrimes
> where 
>    isPrime' x (p:ps) 
>       | (p < x)   = (p == x) || seq' (isPrime' x ps)
>       | otherwise = (p == x)

EDIT: augustss mentioned that my use of seq was pointless, theoretically, it would be more efficient to use strict evaluation here, but it won't till I learn how to do that. It's unfortunate ghc/hugs won't recognize tail-recursion and make it strict automatically :/

Cool, all we're doing here is building up a chain of "does element p_k equal the given number?

Now what? Well, since we've defined prime numbers over the naturals, we can do some handy things like create a factorization function. We'll just use trial division to determine the factors

> factorize :: Nat -> [Nat]
> factorize x 
>    -- if the number is prime, we're done.
>    | isPrime x = [x]
>    -- if not, then we know we just need to find the first
>    -- factor, and then recurse on the number `div` the factor
>    | otherwise = firstFactor 
>                : (factorize (x `div` firstFactor))
>    where
>       divides x y = (y `mod` x) == 0
>       firstFactor = head 
>                   $ dropWhile (\p -> not (p `divides` x)) natPrimes

Fast? Hell no, it takes quite some time to factorize 210, and I didn't even bother to wait till it finished 2310, but it does work.

We know we can create a generic "closure" function, which takes a list and a operation on the elements of that list and recursively applies that function till the list is "closed" that is, applying closure again returns the same list. Lets write that quickly.

> closure :: Ord a => (a -> a -> a) -> [a] -> [a]
> closure f ls = closure' f ls []

> -- closure' is just a helper function which keeps track of the 
> -- last list for comparasion against the closed list
> closure' :: Ord a => (a -> a -> a) -> [a] -> [a] -> [a]
> closure' f ls old 
>      -- if the old list is the same as the new list, return the
>      -- list
>      | ls == old = sort ls
>      | otherwise = closure' f (performClosure f ls) ls

> performClosure :: Eq a => (a -> a -> a) -> [a] -> [a]
> performClosure _ [] = []
> performClosure f (x:xs) = [x] 
>                         `union` (map (f x) xs) 
>                         `union` (performClosure f xs)

Well, okay- it wasn't that simple. However, using this, we can write the "divisors" function, which returns a set of all numbers which divide a given number. We're going to use a nifty trick here too, I'll take a moment to explain it.

Normally, we see closed sets defined with a "mod" function, as in the group of integers mod 10, etc. We can define the closure operation (in Haskell's lambda notation) as being:

\ x y -> (x + y) `mod` k

for some constant k. However, this really doesn't work well when trying to come up with a closure operator for divisors. What we need is a function which will dynamicly limit the power to which each factor is raised. Fortunately, a nice mathematician named Euclid came up with a handy algorithm for creating a function just like this, it is called the greatest common divisor, the GCD.

Upon examination, you'll note that the function:

\ x y -> (x * y) `gcd` k

will force the product to only contain appropriately sized factors, because if the multiplication creates a number with an factor with an exponent greater than that of the same factor in k, then it will simply return the factor to the lower of the two powers.

So now, lets create a divisors function based on that concept and previously defined functions, we need to add 1 to the list because our factorization function won't return that.

> divisors :: Nat -> [Nat]
> divisors k = S(Z) : closure closer (factorize k)
>      where closer x y = (x*y) `gcd` k

Pretty simple, just one more reason to love Haskell. Lets define sigma, which is the sum of divisors to a power function. That is

> sigma :: Nat -> Nat -> Nat
> sigma k p = sum (map (^p) (divisors k))

Hmm, lets do one more big one, how about Totient, that is, the total number of all numbers x less than k that satisfy the property gcd(x,k) == 1

 

> totient :: Nat -> [Nat]
> totient k = length [x | x <- [S(Z)..(k-1)], gcd x k == 1]

List comprehensions are awesome, aren't they?


Okay, last thing on our list, Integers. So far, we've been dealing with Naturals so far, and as such, have not had negative numbers to deal with. What I intend create a "Smart" Datatype which can cleverly increment and decrement without much difficulty. The problem with Integers is that the naive method for creating them, using the standard data types, is that when we try to decrement a positive number (or vice versa) we have to ensure that we just remove one of the increment/decrement symbols. Rather than just add a new one.

Heres the Datatype, you'll note its similarity to Nat.

 data ZZ = Pre ZZ -- decrement an integer 
         | Z      -- Zero is an integer
         | Suc ZZ -- increment an integer

Note that all we really did was relax the "0 is the successor of no number" axiom. Much of mathematics is discovered by this method of removing the restrictions imposed by some axiom, or assuming an axioms converse/inverse, etc. The most popular example is that of Geometry, for many years, Euclidean Geometry was all there was. However, in the 19th century, Janos Bolyai and Nikolai Ivanovich Lobachesevky (the same mathematician of Tom Lehrer's "Lobachevsky") independently published papers about Hyperbolic Geometry, which changed the infamous "parallel" postulate of Euclidean Geometry to say that, instead of only one line, that there are two lines which pass through a point P not on a line L that do not intersect L. Riemannian, or Ellipic Geometry, states that instead of two lines, that there are no lines. In fact, you can imagine an infinite number of geometries based on the number of lines that can be parallel to a given line. For more about Euclidean and Non-Euclidean Geometries, wikipedia has some very nice articles, links are at the bottom of the post.

So the real test is to create some smarter constructors than what is provided, then we already have. The first thing, really, is to note that we can, in fact, pattern match on functions, eg

> precInt :: Int -> Int -> Int
> precInt (x + 1) = x

works just fine. So lets use that to create two functions, s and p, which are successor and predecessor over the Integers. We'll start a new module for this, this should be placed in a separate .lhs file called "ZZ.lhs"

> module ZZ(ZZ(Z), s, p) where

> data ZZ = P ZZ
>         | Z
>         | S ZZ
>         deriving (Show, Eq, Ord) -- that'll allow us to skip ahead a bit

Notice how we don't have to deal with s(Z) or p(Z) that happens automagically for us.

> s :: ZZ -> ZZ
> -- if we're incrementing a negative number, we can just eliminate a P
> s (P x) = x
> -- these take care of the normal cases, just like in the Nats
> s x = (S x)

> p :: ZZ -> ZZ
> -- Now we just do p, in a similar way.
> p (S x) = x
> p x = (P x)

so now we can define addition, which is all we'll define over the Integers, most of it will be the same or similar to the Naturals, and if you'd like to see it, I encourage you to try it, I'd love to see it working.

Here it is, Addition:

> addZZ :: ZZ -> ZZ -> ZZ
> addZZ Z y = y
> addZZ x y 
>     | y < x  = addZZ y x
>     | x == Z = y
>     | y == Z = x
>     | x < Z  = addZZ (s(x)) (p(y))
>     | x > Z  = addZZ (p(x)) (s(y))

Notably, this also defines subtraction, given the capability of negation, anyway. Hopefully you've enjoyed seeing the buildup from a simple concept of Z and S(x::Nat) to a powerful arithmetic. I think the next stop on my list is dealing with DFA/NFA and PDA evaluator and eventually a Regex Recognizer DFA automata, ala Thompson's NFA, then maybe I'll build a Turing Machine Interpreter. All plans are subject to change randomly for no reason at all, Stay Tuned!


~~Joe

Wikipedia articles about various geometry stuff.
Geometry
Euclidean Geometry
Non-Euclidean Geometry
Elliptic Geometry
Hyperbolic Geometry

EDIT: fixed some indentation errors

Peano's Axioms Part III: Making use of Haskell's Powerful Polymorphism

This time, we'll be looking at making use of the polymorphic capabilties of Haskell's type system.

In Haskell, Polymorphism is provided via type variables. That is, you may have a function

foo :: (a -> b) -> [a] -> [b]

which requires a function of any type to any other type, and a list of elements of the first type, and it returns a list of elements of the second type. Most people call this function map, though it can represent others.

So in addition to getting the functions defined in the typeclass, we get all the prelude functions with variable type signatures.

But wait- theres more. When we define certain types of functions, we often want to limit the scope of the function to only operate on certain variables. Like defining an instance of an interface in Java, we can specify a "scope" (though thats an abuse of the term) for a type variable. As in the following:

foo2 :: Ord a => a -> a -> a

Here, we state that a must be an instance of the typeclass Ord (and by inheritance, an instance of Eq too.) So now we know that foo2 takes two comparable elements and returns a comparable element.

Polymorphism is nothing new to any language. However, I think that Haskell really has an advantage not in the area of semantics, which are pretty much uniform -- at least in the case of polymorphism. I think that Haskell's advantage is in the syntax of polymorphism. Type signatures are easily wonderfully simple ways to express polymorphism. Both this basic kind of polymorphism (called rank-1 polymorphism), as well as higher order polymorphism (rank-2, rank-3, rank-n).

The point of this post is to show the rich library of polymorphic functions which become available with just a few (I think we're up to 7, one derived, 6 implemented) type classes. This, as always, is a literate file, just cut and paste to a .lhs and run


$> ghci .lhs


> module Peano2 (Nat(..)) where
> import Peano
> import Data.Ratio

==============================================================
Continuing on which defining math in terms of Peano's axioms
==============================================================

Last time I noted that we'd be working on exp, div, mod, and some other
higher-level functions. I also mentioned that we "sortof" got exp for free, in
that

S(S(S(Z)))^k,

where k is an integer, works fine, but what if we k be a natural. we'll notice
readily that this will fail, with the error that theres no instance of
Integral Nat.

Why is that a problem? because (^) isn't in Num, its defined elsewhere, its
signature is

(^) :: (Num a, Integral b) => a -> b -> a

Okay, so now what we should do is define Nat to be an Integral Type. So, lets go
for it.


=======================================

so, for Integral, we need quot, rem, and toInteger. We have the last of these, from the last time. Its quot and rem that we need. So, how do we define these?

well, we know that quot and rem are (effectively) just mod and div, in fact, not having negative numbers means that they are exactly the same. Lets then realize that mod is just repeated subtraction until we hit modulus > remnant. further, we relize that div is just the same, but the count of times we subtracted till we met that condition.

> quotNat :: Nat -> Nat -> Nat
> quotNat k m 
>    | k == m       = 1
>    | k < m        = 0
>    | otherwise    = 1 + (quotNat (k-m) m)

> remNat :: Nat -> Nat -> Nat
> remNat k m 
>    | k == m       = 0
>    | k < m        = k
>    | otherwise    = remNat (k-m) m

> quotRemNat     :: Nat -> Nat -> (Nat, Nat)
> quotRemNat k m = ((quotNat k m), (remNat k m))

now, we just instantiate integral

> instance Integral Nat where
>    toInteger = ntoi
>    quotRem = quotRemNat
>    -- this fixes a problem that arises from Nats not having
>    -- negative numbers defined.
>    divMod = quotRemNat

=======================================

but now we need to instantiate Enum and Real, oh my. Lets go for Enum first.

Enum requires just toEnum and fromEnum, thats pretty easy, to and from enum are just to and from Integer, which we have.

> instance Enum Nat where
>    toEnum = integerToNat
>    fromEnum = natToInteger 

Real is actually relatively easy, we're just projecting into a superset of the
Naturals, notably, the Rationals, so we do this simply by pushing the value
into a ratio of itself to 1, that is

toRational S(S(S(S(Z)))) ==> S(S(S(S(Z)))) % 1

> instance Real Nat where
>    toRational k = (ntoi k) % 1

=======================================

Next time, we'll go for primes.

oh- and by the way, pushing Nat into Integral gave us lots of neat things, notably even/odd, gcd/lcm, the ability to do ranges like [(Z)..], and all the appropriate functions that go with that.

So far, I've spent about 1 hour making all this work, you can imagine how this speed could be useful if you have defined your problem as having certain properties. Type classes are an extremely powerful tool, which can help make your code both clean, as well as powerful. In one hour, I've managed to build up a simple bit of code, based on some fairly primitive axioms, and create a huge amount of powerful math around it.

Imagine if you could define these same relations around data? What if you were able to define strings as having properties of numbers, heres an Idea:

Imagine you have some strings, you can define the gcd of two strings as the least common substring of two strings. If you can sensically define the product of two strings, then you can get a concept of lcm as well. Granted, the may not be the best example. But you can just imagine the power you can push into your data by defining an arithmetic, (not even an algebra!) on them. Imagine creating an arithmetic of music (been done, sortof, check out Haskore) or pictures? I use
arithmetic,because what I'm implementing here is only a little peice of the power you can instill. _This_ is why Haskell is powerful. Not because its purely functional, not even because its lazy. It's the _math_ that makes Haskell capable of doing this. The type theory upon which Haskell rests makes Haskell powerful.

Remember, next time, Primes and Totients and Number Theory, and a datatype
representing the Integers,
Oh my!

Intermezzo: Mental Vomit.

Phew, it's been a long few days, I have the last few posts in the Peano series coming up, and I've been planning out a new series of posts about a project I've been toying with- a Haskore-esque Music system. By the looks of it, Haskore is no longer being mantained, so maybe someday I'll this project will actually turn into something useful, but really- I'm just looking to do something nifty with Haskell.

Today, though, I'm just going to brain-vomit and talk about some random thoughts I had.

Programming the Universe, by Seth Lloyd.

Excellent book, I'm about halfway through it. It's really brilliantly written, very engaging, though its occasionally a little too conversational for my tastes. It's also relatively thin, which is good, because it makes me feel proud to say I'm halfway through in less than 3 days, even though halfway through is 100 pages. It's also kind of unfortunate, as I'll be done with it soon, though I suppose if you have to have some problem, not wanting the book to end because your enjoying it to much is probably a good one to have. The book, principly, is about how the universe can be described as a giant quantum computer, it goes into information theory and its relation to thermodynamics and entropy. It talks about Quantum Logical Operations, though (at least up till now) not in any real detail, althoug h I saw some Bra-ket notation in later chapters. I'm not very knowledgable about Quantum Computing in general, so I hope to pick up some basic understanding from this, or at least enough language so I know where to look for more info. I figure, in 10 years, this technology will be relatively grown up, and I'll need to know it to stay current. Might as well start now.

I am a Strange Loop, by Douglas Hofstadter

I'm a Hofstadter fanboy, I'll admit it. GEB is the best book ever. Metamagical Themas is the second best book, and hopefully, this will be the third best. I didn't even read the back cover when I bought this, I saw "Hofstadter" and I actually squealed a little. Yes, I squealed, but honestly, DH is quite possibly my favorite non-fiction writer ever. I'm allowed to be a fanboy. It was a manly squeal. Shut up. :P

I haven't started reading it yet, but my first impression (from my random flipopen to one of the pages) is that it'll be a entertaining read, to say the least. I opened to a section headed with "Is W one letter or two?" I think it'll be good, and the cover art is really quite nice.

Reinventing the Wheel, and why It's a good thing.

Now a little more on topic. I've been hearing more and more, or maybe I'm just noticing that people say this more and more, that we -- as programmers, mathematicians, etc -- should not try to reinvent the wheel. For the most part, I agree. Some problems are solved, but should we discourage people from reinventing the wheel entirely? I think there is something to be said for reinventing the wheel every now and again, especially for new programmers. For instance, the recent posts about Peano's Axioms. This has probably been done to death by other Haskeller's out there, but why do I do it now? Partially because it shows the wonders of type classes, but also because the exercise of solving this already solved problem is an excellent way to learn about how the solution works, and furthermore how to apply those concepts to other problems. I mean, maybe I'm just ranting, but don't we reinvent the wheel over and over? Insertion sort is a perfectly good sorting algorithm, it does the job, heck, it even does it far quicker than we could. However, if it weren't for the fact that someone sat down and said, "Maybe this wheel isn't as great as it could be" and reinvented it, and came up with quicksort, or radix sort, or count sort, then where would our applications be? Even looking at the actual wheel, how many times has it been reinvented? It started out as some big stone, then it was probably wood, then wood with metal plating, then mostly metal, now its a complex part with alloys and rubber and all sorts of different materials. I m guess what I'm trying to say is maybe instead of "never reinventing the wheel" we should, "Never reinvent the wheel, except in cases where reinventing the wheel would give us a better solution." I suppose its the logical resolution to the problem presented from trying to combine this adage with the adage:

"Never say never, ever again."

Anyway, It's time to get back to procrastinating, or not, I guess I'll do it later.

PhD. Procrastinate.

Peano's Axioms Part II: Orderability and Code

So, lets get started with this Peano arithmetic stuff. For those who do not know what Peano's axioms are, heres a brief explaination.

Peano's Axioms define a formal system for deriving arithmetic operations and procedures over the set of "Natural" numbers. Peanos Axiom's are most often stated as follows, though variants do exist.

1) 0 is a natural number. (Base Case)
2) If x is a natural number, S x is a natural number (Successor)
3) There is no number S x = 0 (0 is the successor of no number)
4a) 0 is only equal to 0.
4b) Two natural numbers Sx and Sy are equal iff x and y are equal.
4c) If x,y are natural numbers, then either (x == y /\ y == x) or (x /= y /\ y /= x)
5) If you have a subset K, and 0 is in K. Then if some Proposition P holds for 0, and Sx for all x in K, then K contains the naturals. (Induction, from Wikipedia)

(see Peano's Axioms Wikipedia Entry)

The goal of this post is to define Equality, Orderability, and basic arithmetic over the Naturals. We'll also see how the standard Peano numbers. Lets talk about Orderability, for a second.

Equality is provided for by the axioms, but what is orderability? When we think about something being ordered, we can think about a "total" ordering, or a "partial" ordering. A Total Ordering is one that satisfies the following conditions.

For some Binary relation R(x,y), (notated xRy),
1) R is antisymmetric:
(xRy /\ yRx) iff (x==y), where == is equality.
2) R is transitive:
if (aRb /\ bRc) then (aRc)
3) and R is total:
(xRy \/ yRx)

a partial order only lacks in the third axiom. What does all this mean though? Well, axiom 1 gives us an important link to equality. We can actually use this fact to either define Equality from Orderability, or vice versa. Also, Axiom 1 gives us the ability to make the MRD for the Ord class very succint, only requiring (<=) at the very least. In Haskell, the Ord class is a subclass of Eq, so we need to define equality first in Haskell. This is not a problem, as we can always use Axiom 1 to define an equality function retroactively. That is, define (<=) as a function external to the type class, over the naturals. Then define (==) as ((x<=y)&&(y<=x)). We can then instance the both classes together. Axiom 2 is pretty self explainatory, it allows us to infer an ordering of two elements from two separate orderings. One neat thing this does, that not many people point out, is this is the axiom that allows for the concept of sorting. Since effectively, when we sort, we want to chain orderings together so we can have a list with elements of the type with the property of: k_1 <= k_2 &&amp;amp; k_2 <= k_3 && ... && k_(n-1) <= k_n => k_1 <= k_n that is, element 1 is less than element 2, and so on, such that the first element of the list is ordered with the last. It's relatively trivial to realize, so much so that most people don't even bother to mention it, but it certainly is interesting to see. Axiom 3 is the defining feature of total orderings, it's similar to the law of the excluded middle. We can see how certain relations are non-total, take for instance the relation (<). That is, the relation x < sx ="=" sy ="=">
> {-# OPTIONS -fglasgow-exts #-}
> module Peano (Nat(..), one, p,
>    iton, ntoi, natToInteger,
>    integerToNat) where

=============================================
Defining Arithmetic based on Peano's Axioms
=============================================

===============================================================================
First, we'll define Nat, the set of natural numbers w/ 0,

This covers Axiom 1,2, and 3.

> data Nat = Z | S Nat
>   deriving Show

This encodes the concept of Natural Numbers, we aren't going to use Haskell's
deriving capabilities for Eq, but Show thats fine, it'd just be
tedious.


Handy bits.

> one :: Nat
> one = (S Z)



===============================================================================
Now lets build up Eq, the Equality of two numbers, this covers Axioms
2,3,4,5,7, and 8


> instance Eq Nat where

every number is equal to itself, we only need to define it for Zero, the rest
will come w/ recursion for free.

>   Z == Z = True

No number's successor equals zero, and the inverse is also true, zero is the
successor of no number

>   S x == Z = False -- no successor to zero
>   Z == S x = False -- zero is no number's successor

Two numbers are equal iff there successors are equal, here, we state it
backwards,

>   S x == S y = (x == y)

And that, my friends, it Eq for Nat

===============================================================================

Now, lets define orderability, these two things will give us some extra power
when pushing Nat into Num.

> instance Ord Nat where
>   compare Z Z = EQ
>   compare (S x) Z = GT
>   compare Z (S x) = LT
>   compare (S x) (S y) = compare x y

Easy as pie, follows from Axioms 1,2 and 8.
===============================================================================

Now, we can push this bad boy into Num, which will give us all your basic
arithmetic functions

First, lets write (p), the magic predecessor function

> p :: Nat -> Nat
> p Z = Z -- A kludge, we're at the limit of the system here.
>    -- We'll come back to this when we start playing with ZZ
>    -- (the integers)
> p (S x) = x

=======================================

Heres (+) in terms of repeated incrementing.

> addNat :: Nat -> Nat -> Nat

First, we know that Z + Z = Z, but that will follow from the following
definitions

> addNat x Z = x
> addNat Z y = y
> addNat (S x) (S y)
>   | (S x) <= (S y) = addNat x (S (S y)) > | otherwise = addNat y (S (S x))

=======================================

Heres (*)

> mulNat :: Nat -> Nat -> Nat

Simple, here are our rules
y' = y
Z * Sx = Sx * Z = Z
SZ * Sx = Sx * SZ = x
Sx * y = (x) * (y+y')


> mulNat _ Z = Z
> mulNat Z _ = Z
> mulNat a b
>   | a <= b = mulNat' a b b > | otherwise = mulNat' b a a
>   where
>    mulNat' x@(S a) y orig
>     | x == one = y
>     | otherwise = mulNat' a (addNat orig y) orig


=======================================

We're gonna stop and do integerToNat and natToInteger just quick.

> natToInteger :: Integral a => Nat -> a
> natToInteger Z = 0
> natToInteger (S x) = 1 + (natToInteger x)

easy enough, heres integerToNat

> integerToNat :: Integral a => a -> Nat
> integerToNat 0 = Z
> integerToNat k = S (integerToNat (k-1))


pretty nice, huh? Lets add a couple of aliases.

> iton = integerToNat
> ntoi = natToInteger

=======================================

Now we just need (-), we'll talk about abs and signum in a second

> subNat :: Nat -> Nat -> Nat
> subNat x Z = x
> subNat Z x = Z
> subNat x y
>   | x <= y = Z > | otherwise = subNat (p x) (p y)

=======================================

Few, after all that, we just need to define signum. abs is pointless in Nat,
because all numbers are either positive or Z,

so signum is equally easy. since nothing is less than Z, then we know the
following

> sigNat :: Nat -> Nat
> sigNat Z = Z
> sigNat (S x) = one

and abs is then just id on Nats

> absNat :: Nat -> Nat
> absNat = id

===============================================================================

After all that, we can now create an instance of Num

> instance Num Nat where
>   (+) = addNat
>   (*) = mulNat
>   (-) = subNat
>   signum = sigNat
>   abs = absNat
>   negate x = Z -- we don't _technically_ need this, but its pretty obvious
>   fromInteger = integerToNat

Phew, that was fun. Next time- we'll play with Exp, Div and Mod, and maybe some
more fun stuff.

Quick note, pushing Peano into Num gives us (^) for free (sortof.), but we'll
define it next time anyway

Peano's Axioms Part I: Haskell and Type Theory, and Object Oriented Programming

Well, the title's a little misleading, this has very little to do with type signatures, I decided to start a little series on what I think is the most powerful aspect of Haskell. Of course, I think that the most part is Math. Specifically in the realm of Type Classes. I'll give you a little background here.

I'm primarily familiar with Java's class system. Notably, upon reading about and toying with other class inheritance systems, Java stood out to me as being my favorite. It feels the most algebraic. One thing that should be noted is that typically, the only "real" difference between these systems (I'm generalizing wildly.) is in the world of multiple inheritance. Java, in particular, uses interfaces, which I intend to show as being a kind of type class, in fact, it is about one step away from being a real live type class.

Now, Lets start talking about inheritance.

Assume we have an Object Joe. Joe is a "Reified" (to borrow some language from type theory) object, that is. He's a finite, usable, object, with real methods, that do real things. Effectively, he's material, you can "poke" him, as it were.

Lets now say Joe has some Children, Jack and Emily. These are also Reified objects. However, they have a special property, they have a "Parent" object, namely Joe. This "special property" allows them to inherit properties from Joe, (say... devilishly good looks, and powerful intellect?). By now, the female readers are probably moaning, "Those have to come from the mother." And thats a good point, how do we get the Mom in on this? We need Multiple Inheritence. Before we get there though, lets talk about a different kind of object, an Abstract object.

An Abstract Object describes some underlying property of an object, but it does so through this Parent/Child relationship. An Abstract Object in our setting might be something like "Ancestor" or even "Parent". Notable things about Abstract objects is that they don't contain any "Reified" methods, that is, methods containing code. The contain stubs which describe the signature of a method, but not the method itself. So we might have a Abstract class "Parent" which contains a method "getChildren" which has a signature void -> List, its purpose is to return a list of the extending classe's (like Joe) Children. The important thing is, it doesn't force that to be the result, it only enforces a type of the content, not the content itself.

But what about Multiple Inheritence. Assume we have another object called "Sarah" which also extends the parent class, and also assume that Jack and Emily are Sarah's children too. Lets assume further that Sarah implements getChildren differently than Joe does. How then do Jack and Emily access there respective parents getChildren Methods? If they are fundamentally different implementations, then how can they choose which to use? Further, what if we want to have Parents for Joe, but we also want Joe to extend the Ancestor class? Now we have a mess...

How do we fix it? Well, the answer is to create a super version of Abstract classes, lets call them interfaces.

What does an Interface do? Well-- in Java, no class is allowed to inherit from more than one parent class. Abstract or Reified. Interfaces exist outside of the usual inheritance tree, and can therefore give information about the tree as a whole. For instance, we can now create our inheritance tree by saying that each ancestor class implements the "hasChildren" interface, which forces the ancestor to have the void -> List method, we can then say that the Children found in that list are instances of the Child class, rather than the class itself, this gives us a solution to the problem by forcing us to access Jack through the Sarah object.

Could we have done this with normal Abstract/Reified classes, sure. Would it work as well? Probably not.

So why are interfaces cool? Well- you can think of an Interface as a way to describe a set of classes. Classes which meet certain properties. Indeed, they use interfaces like this all the time. For instance, Java has a interface called "Comparable" which- as the name suggests, means that any class that implements Comparable can compare instances of itself in a meaninful way. Comparable doesn't say how to do the actual comparison, it just says that there must be a method compare which has type: (using Haskell-esque syntax)


compare :: Comparable a => a -> a -> {-1,0,+1}


The Javadocs recommends that it should have 0 mean that x == y, but that its not required. The interface only defines the kind of interaction you can have.

Why is this cool? Well, consider the obvious example, what if I wanted to write quicksort over a generic list of elements? How do I ensure that I have a sortable list? Lets say we have an Object Foo, which has no ordering, and another Object Bar, which can. I have a magic method qsort which will actually do the sorting, but how do I write the method such that I know that the list is sortable? That is if I write tests:


assertFail(qsort(List = {foo1, foo2, ...}));
assertPass(qsort(List = {bar1, bar2, ...}));


How can I ensure those both succeed (with the assumption, of course, that those testing constructs exist)? Well, the easy answer is to define qsort as having the method signature:


List qsort(List);

(I think thats the right syntax, it's been a while since I wrote Java.)

This will prevent (at compile time, no less) the use of qsort on List, because Foo doesn't implement Comparable. Running it on List is Fine, because its comparable, like we said before.

So now how is this different from Type Classes. Well, principly, there is one difference. Type Classes can not only specify methods the Type must have defined on it, but it can also define other methods derived from those methods. A seemingly trivial extension to Interfaces. However, that one simple change gives you enormous power in creating data abstractions. For instance, given the Haskell equivalent of Comparable, which is the pair of classes Eq and Ord (for Equality and Orderability, resp.), which require only 2 definitions total (== or /=, and compare or <=, /= is not equal). We get for free, about 20-30 functions including: all your comparison and equality operators, the ability to put items implementing the class in a set, the ability to use them as a key in a finite map, sorting of implementing items, some extra list functions, and more. All that, from 2 definitions, in two type classes, along with the Prelude and Haskell's own polymorphism capabilities.

How does that work? Well, lets dissect some code, here's the Ord class:

ignore the '.''s, they're just for spacing.


class (Eq a) => Ord a where
........compare :: a -> a -> Ordering
........(<), (<=), (>=),(>) :: a -> a -> Bool
........max, min :: a -> a -> a
................--minimal complete definition:
................-- (<=) or compare
................-- using compare can be more efficient for complex types.
........compare x y
.............| x == y = EQ
.............| x <= y = LT
.............| otherwise = GT
........x <= y = compare x y /= GT
........x < y = compare x y == LT
........x >= y = compare x y /= LT
........x > y = compare x y == GT
........-- note that (min x y, max x y) = (x,y) or (y,x)
........max x y
.............| x <= y = y
.............| otherwise = x
........min x y
.............| x <= y = x
.............| otherwise = y



So, lets dissect.

First, we declare what the class implements, that is, what methods are required to exist if the class is implemented. However, this is not the same as saying that all those methods must be defined over the structure before we can say it implements the class. We instead only need the "MRD/MCD" or "Minimal Requisite/Complete Definition" that is, the minimal number of functions needed to define all the other functions the class provides. How do we know what the MRD is? Well- thats up to you to decide. We do that by defining each function of the class in terms of other functions in the class, even cyclicly if necessary. I like to call this set of cyclic definitions the "internal definitions" of the set. These internal definitions provide the real power of the type class. Also note how, in the class definition, we have an inheritance bit, in that of Eq a => Ord a. This allows us to assume that we have basic equality functions provided by Eq.

In the next few posts in this series, I'll be implementing Peano Arithmetic in Haskell, principly by pushing one simple data type:


Nat = Z | S Nat


Into as many type classes as I can, as of this writing, I have two more posts planned, and have pushed Nat into Eq, Ord, Num, Integral, Enum, and Real, I hope to get it into Rational and Fractional which will turn it into Nat-QQ (Natural Rationals (that is, all the Positive Rationals)), and maybe then refactor Nat into ZZ (the integers), and get the Regular Rationals out of that.

Human Error Bugs

I fixed comments not coming up, and such. Thanks for pointing them out, folks.

An Analogy for Functional versus Imperative programming.

I was thinking the other day, about many things, as we drove back from my Aunt and Uncles in NY. I had been discussing with my father about C vs Haskell and, more generally, about functional versus imperative programming. I had been trying to explain why Functional programming is useful, particularly in areas relating to parallelism and concurrent code. To put this in perspective, my father has been writing low level system verification code for a very long time. (he started way back in the 70s) so he's pretty situated in the imperative world, with a (vast) knowledge of C and languages like Verilog and stuff. Me, I've only been writing code since I was 14-15. I have far more knowledge in languages like Scheme, Haskell, and to an extent, the ML family. I also regularly use Java and friends, So it's safe to say that trying to cross our respective expertises is most often quite difficult. Anyway, I came up with a pretty clever analogy, I think, for how Functional and Imperative programs relate.

Factorys

I have no idea if this analogy has been used before, but if it has, kudos to whoever came up with it, basically, it goes like this.

an imperative language is monolithic. it effectively can be modelled as one giant state machine that gets permuted. Like a Rube Goldberg machine, you don't design an imperative program to manipulate inputs, you design it for its side effects.

Here in Massachusetts, we have the Boston science museum, in which, there is a rube goldberg machine (RGM). It is, (next to the math room), by far one of my favorite exhibits. But what does an RGM do? Put simply, its just a while(1) loop. It ferries some bowling balls or whatnot to the top, and then drops then. The interesting part is the side effects. The bangs and whizzes and clanking and ratcheting of the chain as various balls drop and gears spin and cogs do whatever they do, cogulate, I guess. The point of the RGM is to manipulate the world indirectly. Someone, at some point, "said" to the machine, "start." From thence, it has worked to make noise and spin and do all that nifty stuff.

So, RGM's, you say, are mildly useless, right? Well. We'll come back to that in a minute, but suffice to say, like everything else in the world, they have there place.

So if an Imperative language is Like a RGM, whats a functional language?

Well, lets realize that effectively, all a program does is turn some set of inputs, to some set of outputs. Kind of like how a factory may take in some raw material, (steel, plastics, etc.) and create a new, better "material" from those outputs, (eg, a car). A language does the same thing, a user "inputs" a query to a database server (technically, he, or someone else, have given the program the database, too. Kind of like currying, here. hmm). Then after your query, you get back a database entry or list thereof which match your search parameters. Now, a RGM-type machine, or more accurately, a monolithic program, which are typically written in imperative languages (though you can write monolithic functional programs) take an input, and, completely internally, turn that input to an output. Kind of like a whole factory in a box. useful, yes, reusable not necessarily. A functional approach, on the other hand, is like the components that make up a factory. When I write a program in Haskell, I have a series of functions which map input data to intermediate data, and functions which map intermediate data to intermediate data, and then finally functions which take intermediate data and map it to output data. For instance, if I want to create a function which takes a list and returns it along with its reversal, in Haskell, I'd write:


myReverse :: [a] -> [a]
retPair :: [a] -> ([a],[a])

myReverse [] = []
myReverse (x:xs) = myReverse xs : x

retPair ls = (ls , myReverse ls)


So you can see how retPair starts the chain by taking input. copies ls and sends it to an output, and then sends the other copy to another "machine" in the factory, which turns a list of anything '[a]' to a list of anything. The result is then sent to output with the original as a pair '([a],[a])'

You can see this in the diagram:


..........................myReverse..............................
................/---------[a]->[a]-------\...they get............
input...........|........................|...rejoined............
>---------------|split ls................|---([a],[a])-->output..
................|........................|.......................
................\---------[a]->[a]-------/.......................
..........................identity...............................
..........................function...............................


So what does this "individual machine method" give us? For one, its free to reuse, its very easy to pull apart this "factory" of "machines" and reuse any given "machine" in some other "factory". It would not be as easy to do if we had written it procedurally, as in C/C++. I can hear the screams of imperative programmers now, "We would have written exactly the same thing, more or less!" and I know this, and don't get me wrong, you _can_ write this "factory style" code in C/C++, but what about less trivial examples? In Haskell, I can only write pure functional code (barring monads, which are borderline non-functional). Whereas in C/C++, writing this kind of reusable code is often hard. In a functional language, writing this kind of code is almost implicit to the nature of how you think about code. The point I'm trying to make is simply this, FP-style languages force you to write (more or less) reusable code. Imperative languages in many cases force you to write once-off code you'll never see again. I'm not saying this makes FP better, in fact, in a huge number of cases, I, as an FP programmer, have to write one-off imperative-esque state mangling RGM's to get things done. The point is Haskell helps me avoid those things, which makes for more reusable code.

Another thing, FP is famous for being "good" at concurrency. This analogy works wonders at explaining why. Think about the factory example, when I split ls into two copies, I split the program into two "threads". I effectively set up an assembly line, when I send done the copy of ls to the myReverse function, you can imagine a little factory worker turning the list around pi/2 radians so that it was backwards, and sending it down the line... You can even imagine the type constrictions as another little worker who hits a siren when you send down the wrong material. Imagine, however, trying to parallelize an RGM. RGM's are often dependent on the inability to be made concurrent, even if that wasn't the programmers intention. Imperative programs fight the programmer with things like deadlocks (two balls in the RGM get stuck in the same spot) and race conditions (two balls in the RGM racing towards the conveyor belt, with no way of determining who will win, how do you handle that?) whereas FP implicitly allows multiple "workers" to manipulate there own personal materials to make there own personal products at there station. In a purely functional program, each function is implicitly a process, you could even go so far as to give it its own thread. Each machine's thread would just yield until it got something to work on, at which point it would do its work, and go back to waiting, it doesn't matter which information gets to the next machine first, because it will just wait till it has all the information it needs to execute. Bottlenecking (a common problem in all code) is easier to see in this "factory" style view, since a bottle neck will (*gasp*) look like a bottle neck, all the functions will output to a single function. Thats a sign that its time to break it up, or have two copies of it running in parallel. FP makes this stuff simple, which makes FP powerful. Because for a language to have true power, it must make it so the programmer has to only think about what he wants to do, and not how to do it.

On the other hand, Imperative programming world. You have a number of excellent things going for you. Imperative code is remarkably good at clever manipulations of the machine itself. It is, in some ways, "closer" to the machine than a Functional language could ever be. So even though you have your share of problems, (parallelism and code reuse are the two I think are the biggest.) you have benefits to. Code in C is well know to be very fast, Object Oriented Languages are, I think, best described imperatively, and OO is a wonderfully intuitive way to think about programming. Imperative Programming is also makes it infinitely easier to deal with state, which can be a good thing, if use properly. Don't get me wrong, I love monads, but even the cleverness of monads can't compare to the ease of I/O in Perl, C, Java, Bash, or any other imperative language.

Hopefully this was enlightening, again, I want to say, Imperative programming isn't Bad, just different. I like FP because it solves some big problems in Imperative Programming. Other people are of course allowed to disagree. It's not like I'm Jake or anything.