The Evolution of a Haskell Programmer

Freshman Haskell programmer

fac n = if n == 0            then 1           else n * fac (n-1)

Sophomore Haskell programmer, at MIT

fac = (\(n) ->        (if ((==) n 0)            then 1            else ((*) n (fac ((-) n 1)))))

Junior Haskell programmer

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

Another junior Haskell programmer

fac 0 = 1fac n = n * fac (n-1)

Senior Haskell programmer

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

Another senior Haskell programmer

fac n = foldl (*) 1 [1..n]

Yet another senior Haskell programmer

-- using foldr to simulate foldlfac n = foldr (\x g n -> g (x*n)) id [1..n] 1

Memoizing Haskell programmer

facs = scanl (*) 1 [1..]fac n = facs !! n

Pointless (ahem) “Points-free” Haskell programmer

fac = foldr (*) 1 . enumFromTo 1

Iterative Haskell programmer

fac n = result (for init next done)        where init = (0,1)              next   (i,m) = (i+1, m * (i+1))              done   (i,_) = i==n              result (_,m) = mfor i n d = until d n i

Iterative one-liner Haskell programmer

fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))

Accumulating Haskell programmer

facAcc a 0 = afacAcc a n = facAcc (n*a) (n-1)fac = facAcc 1

Continuation-passing Haskell programmer

facCps k 0 = k 1facCps k n = facCps (k . (n *)) (n-1)fac = facCps id

Boy Scout Haskell programmer

y f = f (y f)fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

Combinatory Haskell programmer

s f g x = f x (g x)k x y   = xb f g x = f (g x)c f g x = f x gy f     = f (y f)cond p f g x = if p x then f x else g xfac  = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))

List-encoding Haskell programmer

arb = ()    -- "undefined" is also a good RHS, as is "arb" :)listenc n = replicate n arblistprj f = length . f . listenclistprod xs ys = [ i (x,y) | x<-xs, y<-ys ]                 where i _ = arbfacl []         = listenc  1facl n@(_:pred) = listprod n (facl pred)fac = listprj facl

Interpretive Haskell programmer

-- a dynamically-typed term languagedata Term = Occ Var          | Use Prim          | Lit Integer          | App Term Term          | Abs Var  Term          | Rec Var  Termtype Var  = Stringtype Prim = String-- a domain of values, including functionsdata Value = Num  Integer           | Bool Bool           | Fun (Value -> Value)instance Show Value where  show (Num  n) = show n  show (Bool b) = show b  show (Fun  _) = ""prjFun (Fun f) = fprjFun  _      = error "bad function value"prjNum (Num n) = nprjNum  _      = error "bad numeric value"prjBool (Bool b) = bprjBool  _       = error "bad boolean value"binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))-- environments mapping variables to valuestype Env = [(Var, Value)]getval x env =  case lookup x env of                  Just v  -> v                  Nothing -> error ("no value for " ++ x)-- an environment-based evaluation functioneval env (Occ x) = getval x enveval env (Use c) = getval c primseval env (Lit k) = Num keval env (App m n) = prjFun (eval env m) (eval env n)eval env (Abs x m) = Fun  (\v -> eval ((x,v) : env) m)eval env (Rec x m) = f where f = eval ((x,f) : env) m-- a (fixed) "environment" of language primitivestimes = binOp Num  (*)minus = binOp Num  (-)equal = binOp Bool (==)cond  = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]-- a term representing factorial and a "wrapper" for evaluationfacTerm = Rec "f" (Abs "n"               (App (App (App (Use "if")                   (App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))                   (App (App (Use "*")  (Occ "n"))                        (App (Occ "f")                               (App (App (Use "-") (Occ "n")) (Lit 1))))))fac n = prjNum (eval [] (App facTerm (Lit n)))

Static Haskell programmer

-- static Peano constructors and numeralsdata Zerodata Succ ntype One   = Succ Zerotype Two   = Succ Onetype Three = Succ Twotype Four  = Succ Three-- dynamic representatives for static Peanoszero  = undefined :: Zeroone   = undefined :: Onetwo   = undefined :: Twothree = undefined :: Threefour  = undefined :: Four-- addition, a la Prologclass Add a b c | a b -> c where  add :: a -> b -> c  instance              Add  Zero    b  binstance Add a b c => Add (Succ a) b (Succ c)-- multiplication, a la Prologclass Mul a b c | a b -> c where  mul :: a -> b -> cinstance                           Mul  Zero    b Zeroinstance (Mul a b c, Add b c d) => Mul (Succ a) b d-- factorial, a la Prologclass Fac a b | a -> b where  fac :: a -> binstance                                Fac  Zero    Oneinstance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m-- try, for "instance" (sorry):-- --     :t fac four

Beginning graduate Haskell programmer

-- the natural numbers, a la Peanodata Nat = Zero | Succ Nat-- iteration and some applicationsiter z s  Zero    = ziter z s (Succ n) = s (iter z s n)plus n = iter n     Succmult n = iter Zero (plus n)-- primitive recursionprimrec z s  Zero    = zprimrec z s (Succ n) = s n (primrec z s n)-- two versions of factorialfac  = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))fac' = primrec one (mult . Succ)-- for convenience and testing (try e.g. "fac five")int = iter 0 (1+)instance Show Nat where  show = show . int(zero : one : two : three : four : five : _) = iterate Succ Zero

Origamist Haskell programmer

-- (curried, list) fold and an applicationfold c n []     = nfold c n (x:xs) = c x (fold c n xs)prod = fold (*) 1-- (curried, boolean-based, list) unfold and an applicationunfold p f g x =   if p x      then []      else f x : unfold p f g (g x)downfrom = unfold (==0) id pred-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)refold  c n p f g   = fold c n . unfold p f grefold' c n p f g x =   if p x      then n      else c (f x) (refold' c n p f g (g x))                         -- several versions of factorial, all (extensionally) equivalentfac   = prod . downfromfac'  = refold  (*) 1 (==0) id predfac'' = refold' (*) 1 (==0) id pred

Cartesianally-inclined Haskell programmer

-- (product-based, list) catamorphisms and an applicationcata (n,c) []     = ncata (n,c) (x:xs) = c (x, cata (n,c) xs)mult = uncurry (*)prod = cata (1, mult)-- (co-product-based, list) anamorphisms and an applicationana f = either (const []) (cons . pair (id, ana f)) . fcons = uncurry (:)downfrom = ana uncountuncount 0 = Left  ()uncount n = Right (n, n-1)-- two variations on list hylomorphismshylo  f  g    = cata g . ana fhylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . fpair (f,g) (x,y) = (f x, g y)-- several versions of factorial, all (extensionally) equivalentfac   = prod . downfromfac'  = hylo  uncount (1, mult)fac'' = hylo' uncount (1, mult)

Ph.D. Haskell programmer

-- explicit type recursion based on functorsnewtype Mu f = Mu (f (Mu f))  deriving Showin      x  = Mu xout (Mu x) = x-- cata- and ana-morphisms, now for *arbitrary* (regular) base functorscata phi = phi . fmap (cata phi) . outana  psi = in  . fmap (ana  psi) . psi-- base functor and data type for natural numbers,-- using a curried elimination operatordata N b = Zero | Succ b  deriving Showinstance Functor N where  fmap f = nelim Zero (Succ . f)nelim z s  Zero    = znelim z s (Succ n) = s ntype Nat = Mu N-- conversion to internal numbers, conveniences and applicationsint = cata (nelim 0 (1+))instance Show Nat where  show = show . intzero = in   Zerosuck = in . Succ       -- pardon my "French" (Prelude conflict)plus n = cata (nelim n     suck   )mult n = cata (nelim zero (plus n))-- base functor and data type for listsdata L a b = Nil | Cons a b  deriving Showinstance Functor (L a) where  fmap f = lelim Nil (\a b -> Cons a (f b))lelim n c  Nil       = nlelim n c (Cons a b) = c a btype List a = Mu (L a)-- conversion to internal lists, conveniences and applicationslist = cata (lelim [] (:))instance Show a => Show (List a) where  show = show . listprod = cata (lelim (suck zero) mult)upto = ana (nelim Nil (diag (Cons . suck)) . out)diag f x = f x xfac = prod . upto

Post-doc Haskell programmer

-- explicit type recursion with functors and catamorphismsnewtype Mu f = In (f (Mu f))unIn (In x) = xcata phi = phi . fmap (cata phi) . unIn-- base functor and data type for natural numbers,-- using locally-defined "eliminators"data N c = Z | S cinstance Functor N where  fmap g  Z    = Z  fmap g (S x) = S (g x)type Nat = Mu Nzero   = In  Zsuck n = In (S n)add m = cata phi where  phi  Z    = m  phi (S f) = suck fmult m = cata phi where  phi  Z    = zero  phi (S f) = add m f-- explicit products and their functorial actiondata Prod e c = Pair c eoutl (Pair x y) = xoutr (Pair x y) = yfork f g x = Pair (f x) (g x)instance Functor (Prod e) where  fmap g = fork (g . outl) outr-- comonads, the categorical "opposite" of monadsclass Functor n => Comonad n where  extr :: n a -> a  dupl :: n a -> n (n a)instance Comonad (Prod e) where  extr = outl  dupl = fork id outr-- generalized catamorphisms, zygomorphisms and paramorphismsgcata :: (Functor f, Comonad n) =>           (forall a. f (n a) -> n (f a))             -> (f (n c) -> c) -> Mu f -> cgcata dist phi = extr . cata (fmap phi . dist . fmap dupl)zygo chi = gcata (fork (fmap outl) (chi . fmap outr))para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> cpara = zygo In-- factorial, the *hard* way!fac = para phi where  phi  Z             = suck zero  phi (S (Pair f n)) = mult f (suck n)  -- for convenience and testingint = cata phi where  phi  Z    = 0  phi (S f) = 1 + finstance Show (Mu N) where  show = show . int

Tenured professor

fac n = product [1..n]

Background

Some time later, I came across Iavor’s "jokes" page, including a funny bit called“The Evolution of a Programmer” in which the traditional imperative "Hello, world" program isdeveloped through several variations,from simple beginnings to a ridiculously complex extreme.A moment’s thought turned up the factorial function as the bestfunctional counterpart of "Hello, world". Suddenly the Muse struck and I knew I must write out these examples,culminating (well, almost) in the heavily generalized categoricalversion of factorial provided by Uustalu, Vene and Pardo.

I suppose this is what you’d have to call “small-audience” humour.

PS:I’ve put all the code into a better-formatted text filefor those who might like to experiment with the different variations (you could also just cut and paste a section from your browser).

PPS:As noted above, Iavor is not the original author of“The Evolution of a Programmer.”A quick web search suggests that there are thousands of copiesfloating around and it appears (unattributed) in humor newsgroups asfar back as 1995. But I suspect some version of it goes back muchfurther than that. Of course, if anyone does know who wrote the original, please let me know so that I may credit them here.

But seriously, folks, ...

The first version(straight recursion with conditionals)is probably familiar to programmers of all stripes;fans of LISP and Scheme will find the sophomore version especially readable,except for the funny spelling of “lambda” and the absence of “define”(or “defun”).The use of patterns may seem only a slight shift in perspective, but in addition to mirroring mathematical notation,patterns encourage the view of data types as initial algebras (or as inductively defined).

The use of more “structural” recursion combinators (such as foldr and foldl) is square in the spirit of functional programming: these higher-order functionsabstract away from the common details of different instances ofrecursive definitions, recovering the specifics through function arguments. The “points-free” style (defining functions without explicit reference to their formal parameters)can be compelling, but it can also be over-done;here the intent is to foreshadow similar usage in some of thelater, more stridently algebraic variations.

The accumulating-parameter version illustratesa traditional technique for speeding up functional code. It is thesecond fastest implementation here, at least as measured in terms ofnumber of reductions reported by Hugs,with the iterative versions coming in third. Although the latter run somewhat against the spirit of functional programming, they do give the flavor of the functional simulationof state as used in denotational semantics or, for that matter,in monads. (Monads are woefully un-represented here; I wouldbe grateful if someone could contribute a few (progressive)examples in the spirit of the development above.) The continuation-passing version recalls a denotational account of control (the references are to Steele’s RABBIT compiler for Scheme and the SML/NJ compiler).

The fixed-point versiondemonstrates that we can isolate recursion in a general Y combinator.The combinatory version provides anextreme take on the points-free style inspired by Combinatory Logic,isolating dependence on variable names to the definitions of a few combinators.Of course we could go further, defining the Naturals and Booleansin combinatory terms, but note that the predecessor function will bea bit hard to accomodate (this is one good justification for algebraictypes). Also note that we cannot define the Y combinator in terms of the others without running into typing problems (due essentially to issues ofself-application). Interestingly, this is the fastest of all of theimplementations, perhaps reflecting the underlying graph reduction mechanisms used in the implementation.

The list-encoded version exploits the simpleobservation that we can count in unary by using lists of arbitraryelements, so that the length of a list encodes a natural number.In some sense this idea foreshadows later versions based on recursivetype definitions for Peano’s naturals, since lists of units areisomorphic to naturals. The only interesting thing here is thatmultiplication (numeric product) is seen to arise naturally out of combination (Cartesian product) by way of cardinality.Typing issues make it hard to express this correspondence as directly as we’d like:the following definition of listprod would break the definitionof the facl function due to an occurs-check/infinite type:

listprod xs ys = [ (x,y) | x<-xs, y<-ys ]

listprod xs ys = [ arb | x<-xs, y<-ys ]

The interpretive version implements a small object language rich enough to express factorial, and then implementsan interpreter for it based on a simple environment model. Exercisesalong these lines run all through the latter half of the Friedman,Wand and Haynes text ([6]), albeit expressedthere in Scheme. We used to getflack from students at Oberlin when we made them implement twelve interpreters in a single week-long lab, successively exposing more of the implementation bymoving the real work from the meta-language to the interpreter. Thisimplementation leaves a whole lot on the shoulders of the meta-language,corresponding to about Tuesday or Wednesday in their week. Industrious readers are invited to implement a compiler for a Squiggol-like languageof polytypic folds and unfolds, targeting (and simulating) a suitablecategorical abstract machine (see [9]), and then to implement factorial in that setting (but don't blame me if it makes you late for lunch ...).

The statically-computed version uses type classes and functional dependencies to facilitate computation at compile time (the latter are recent extensions to the Haskell 98 standard by Mark Jones,and are available in Hugs and GHC). The same kinds of techniques can also be used to encode behaviors more oftenassociated with dependent types and polytypic programming, and are thus a topic of much recent interest in the Haskell community. The code shown here is based on an account byThomas Hallgren (see [7]), extended to includefactorial. Prolog fans will find the definitions particularly easy to read, if a bit backwards.

The first of the “graduate”versions gets more serious aboutrecursion, defining natural numbers as a recursivealgebraic datatype and highlighting the difference betweeniteration and primitive recursion. The “origamist”and “cartesian”variations take a small step backwards in this regard,as they return to the use of internal integer and list types.They serve, however, to introduce anamorphic and hylomorphic notions in a more familiar context.

The “Ph.D” example employs the categorical styleof BMF/Squiggol in a serious way (we could actuallygo a bit further, by using co-products more directly, and thuseliminate some of the overt dependence on the “internal sums” of the data type definition mechanism).

By the time we arrive at the “pièce de résistance”,the comonadic version of Uustalu, Vene and Pardo, we have covered most of the underlying ideas and can (hopefully)concentrate better on their specific contributions. The final version, using the Prelude-defined product function and ellipsis notation, is how I think the function is most clearly expressed,presuming some knowledge of the language and Prelude definitions. (This definition also dates back at least to David Turner’s KRC* language [5].)

It is comforting to know that the Prelude ultimately usesa recursion combinator (foldl', the strict version of foldl)to define product.I guess we can all hope to see the day when the Preludewill define gcatamorphic, zygomorphic and paramorphic combinatorsfor us, so that factorial can be defined both conveniently andwith greater dignity :) .

Revision history

• 20 August 01: added the interpretive version,based on an environment model of a small object language (no, not in that sense of object ...).I’m thinking about re-arranging the order of theexamples, so that longer ones that are not part ofthe main line of development don't intrude so much.I also advertised the page on the Haskell Cafémailing list and requested that a link be added to the Haskell humor page.Finally, I have an interesting new example in the works thatmay actually have some original research value; more on this soon.

• 14 August 01 (afternoon): added the combinatory version,now the fastest of the bunch, as measured in number ofreductions reported by Hugs.

• 14 August 01 (morning): adjusted the sophomore/Scheme version to use an explicit "lambda" (though we spell it differentlyin Haskell land) and added the fixed-pointversion.

• 10 August 01: added the list-encoding and static computation versions(the latter uses type classes and functional dependencies tocompute factorial during type-checking; it is anextended version of code from Thomas Hallgren’s “Fun withFunctional Dependencies” [7]).

• 1 August 01: added accumulating-parameter and continuation-passing versions(the latter is a revisedtransliteration from Friedman, Wand and Haynes’ “Essentialsof Programming Languages” [5]).

• 11 July 01: date of the original posting.

References

1. Highlights from nhc - a Space-efficient Haskell Compiler, Niklas Röjemo.In the FPCA ‘95 proceedings. ACM Press, 1995 (see alsoCiteSeeror Chalmers ftp archive)

2. n+k patterns, Lennart Augustsson. Message to the haskell mailing list,Mon, 17 May 93 (seethe mailing list archive)

3. Sorting Morphisms,Lex Augusteijn. In Advanced Functional Programming, (LNCS 1608). Springer-Verlag, 1999 (see also CiteSeer).

4. Recursion Schemes from Comonads, T. Uustalu, V. Vene and A. Pardo. Nordic Journal of Computing, to appear (see alsoTarmo Uustalu’s papers page).

5. Recursion Equations as a Programming Language, D. A. Turner. In Functional Programming and its Applications. Cambridge University Press, 1982.

6. Essentials of Programming Languages, D. Friedman, M. Wand and C. Haynes. MIT PRess and McGraw-Hill, 1994.

7. Fun with Functional Dependencies, Thomas Hallgren. Joint Winter Meeting of the Departments of Science and Computer Engineering,Chalmers University of Technology and Göteborg University, Varberg, Sweden, 2001 (available atthe author’s web archive).

8. The Church of the Least Fixed-Point, authour unknown. (A little bit of lambda calculus humor which circulated in themid-1980’s (at least that’s when I saw it), probably from the comp.lang.functional newsgroup or somesuch. Please write me if you know the author or any other citation information).

9. Categorical Combinators, Sequential Algorithms and Functional Programming,Pierre-Louis Curien. Springer Verlag (2nd edition), 1993.