Please comment. I'd especially appreciate ideas for where to go next, suggestions for a quick overview of currying, and general remarks on style.

## A Perlesque Introduction to Haskell, Part One (draft)

### -1. Introduction and Disclaimer

Sure, this is *Perl* Monks, but as a whole we seem to be pretty
receptive to other languages (as long as they aren't Java or VB), and
I've seen Haskell mentioned a few times. As
it happens, I'm taking a grad-level functional programming course at the
moment, and we're using Haskell. After a bit of Chatterbox chatter, I
decided that enough people would be interested in a Perl-oriented intro
to Haskell that I'd write one up. (I'm not being entirely altruistic
here; I've noticed that I learn things a lot more thoroughly if I have
to explain them to other people.)

A few words of warning: I don't have a *lot* of experience with
Haskell, and very little indeed with some of its more advanced features
(functors and monads, for instance). I might miss important details; I
might even mis*represent* important details; I'll try not to. If
you notice anything that I should have said, but didn't, or any mistakes
I've made, please let me know.

### 0. What is Haskell?

According to haskell.org,

Haskell is a computer programming language. In particular, it is a polymorphicly typed, lazy, purely functional language, quite different from most other programming languages. The language is named for Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages.

Haskell lets you do a lot of the things that you probably really like about Perl, especially relating to lists and lambdas (anonymous functions). It's that list-manipulation similarity that I'm going to try to exploit to bulldoze the learning curve a bit.

haskell.org is Haskell's big web presence;
it's an excellent collection of links and resources. It has a rather
complete list of
implementations, of which `hugs` and `ghc` are probably
the most popular. It also hosts A
Gentle Introduction to Haskell (which isn't especially gentle), and
links to The
Evolution of a Haskell Programmer, both of which you should skim
through while you read these nodes.

### 1. Okay, What's a Polymorphically Typed, Lazy, Purely Functional Language?

#### 1.1. Functional Languages

I haven't been able to get anyone to agree on a definition of what makes a language functional. Functional languages (Lispen, Haskell, ML, Miranda, etc) share a few useful characteristics, though:

##### Good list-processing facilities

Perl has a few generalized list-munging tools (`map`
and `grep` come to mind, as well as
`for (@list)` auto-binding `$_`). Haskell has more --
nothing you can't implement with what we have, of course (just look
at Language::Functional), but well-integrated into the
language. Lists aren't quite as ubiquitous in Haskell as they are
in Lisp, but they're pretty close.

##### Ad-hoc, anonymous functions (lambdas)

You know that anonymous code block you can pass to
`map` or `grep`? Yep. In Perl, you can build
anonymous subs and assign them to coderefs; in functional languages,
building anonymous and/or locally-scoped functions is just another
idiom.

##### First-class functions

Once you have lambdas that are fun and easy to sling around, you can do a lot more with functions than just call them. You can pass them to other functions, store them in lists, build a bunch of related functions on the fly, and so on. (You can do all of this in Perl, too: for instance, storing a bunch of handler functions in a hash as a dispatch table.)

Since functions are first-class objects, there's nothing
preventing you from writing functions that operate on
functions (in fact, this is quite common). These are known
as *higher-order functions*, and are rather closely
tied to the idea of *currying* (see below).

##### No side effects

Well, mostly. If you ignore inconvenient ideas like I/O, Haskell
is pretty much entirely free of side effects (for example, the Perl
expression `$foo = 5` evaluates to 5, and changes the
value of `$foo` as a side effect -- or is it the other
way around?). Proponents of this sort of programming will tell you
that side-effect-free programming causes far fewer bugs; I'm going
to reserve judgement on this point. Put simply, don't expect to do
much in the way of assignment or iteration in Haskell. (Note that
if you consider Lisp and friends to be functional languages, you
probably don't consider this to be a defining point -- unless your
variety of Lisp doesn't have `setq`, of course.)

#### 1.2. Polymorphic Typing

Haskell is a *polymorphically typed* language. If that makes
you think of object-oriented "strongly typed" languages like Java or
C++, you're not too far off the mark. (In fact, you'll probably spend
your first few months with Haskell cursing its anal-retentive type
system, especially given the fact that neither `hugs` nor
`ghc` produces particularly clear type-error reports.) It's not
as bad as you think, though: Haskell is pretty clever at inferring types
for your expressions and functions -- however, any type mismatches will
be caught at compile-time, not at runtime. (This is generally supposed
to be a good thing.)

Haskell's types aren't really isomorphic to your standard OO class
hierarchy, though. Okay, Haskell has a hierarchy of *type
classes*, which give you polymorphism in much the same way as a
base-class pointer in C++. However, Haskell type classes don't enforce
the usual data-encapsulation you'd find in OO languages; nor do they
adhere to the `object->method` "functions attached to data"
model that most of us associate with OOP.

For example, Haskell's `negate` function takes
a number and negates it. (Big surprise, eh?) It has the
type:

which basically says, "ifPm_tut> :t negate negate :: Num a => a -> a

*a*is a numeric type, then

`negate`takes something of type

*a*and returns something of type

*a*". The binary function

`(-)`(operators are functions like any other) has this type:

which gets more interesting in section 1.4.Pm_tut> :t (-) (-) :: Num a => a -> a -> a

#### 1.3. Lazy Evaluation

In Haskell, programming with infinite data structures is fun and easy. For instance, you can say:

and Haskell will give you a list of the natural numbers. (Does that list-range syntax look familiar, by the way?) If you want the first ten natural numbers, then, you can say:nats = [0..]

(Of course, if you want to print all ofPm_tut> take 10 nats [0,1,2,3,4,5,6,7,8,9]

`nats`, you should be prepared to wait a while.)

This works because Haskell is a *lazy* language. When we
defined `nats`, the interpreter (or compiler) didn't dash
right out to calculate its value; when we *used* `nats`,
the interpreter only generated as many elements as we asked for.

A more Perlish example of laziness is the "or die" idiom:

open FH, '<', $file or die "Can't open $file for reading: $!\n";

`perl`won't bother to evaluate the

`die`call if the

`open`succeeds -- it already knows the value of the

`or`. This happens in Haskell, too:

doesn't need to evaluate its second parameter (useful if the second parameter is an infinite list, for instance) to figure out its value. (This happens more often in multi-part function patterns, which I'll get to in a minute.)const x y = x

Lazy evaluation is common enough in Haskell that we tend to talk
about values that *can't* be evaluated (either because they cause a
fatal exception of some sort, or because they're infinite) -- there's a
generic "black-hole" value called "bottom" (usually drawn as an inverted
T; $\perp$ in LaTeX; or the awfully ugly _|_ in ascii). If you ever
evaluate _|_, bad things happen -- your program terminates, or loops
forever; your computer blows up; demons fly out of your nose (depending
on the C compiler that built your Haskell implementation): you get the
idea. (_|_ is like `undef` on steroids and PCP.) Thanks
to Haskell's laziness, we can work happily around _|_s; as long as we
don't evaluate them, everything's fine.

#### 1.4. Currying

Haskell brings another useful functional technique to the party: currying.

Remember the type of `(-)`:

from before? That doesn't look quite right: a function from(-) :: Num a => a -> a -> a

*a*s to

*a*s to

*a*s? Shouldn't it be more like:

instead? (That's actually a valid type: it says that(-) :: Num a => (a, a) -> a

`(-)`is a function from pairs of numbers to numbers, which isn't quite what we want.) Things get more interesting when you know that

`->`is

*right associative*, so our function type becomes:

So subtraction (the(-) :: Num a => a -> (a -> a)

`(-)`function) takes a number and

*returns a function from numbers to numbers*. In other words:

is a function that subtracts its argument from five. (This is called an(5-)

*operator section*, and the parentheses are mandatory. See Section 3.2.1 of AGItH for more details on sections.) We'll see more about currying later on.

### 2. "Hello, world!"

The basic Haskell "Hello, world!" program isn't particularly edifying:

Pm_tut> putStr "Hello, world!\n" Hello, world! Pm_tut>

(Besides, it raises the question "How do you do I/O in a language that's supposedly without side effects?", the answer to which is "Magic and monads", and I really don't want to get into monads right now.) Instead of printing a string, then, I'm going to use a different simple problem as an example: factorial.

#### 2.1. Factorial, Recursively

With a quick glance through the available operations, your first factorial function in Haskell might look like:

Not too bad. Thefactorial n = if n == 0 then 1 else n * factorial (n-1)

`if ... then ... else ...`construct is pretty clear. We're obviously defining a function (in fact, to a mathematician, this definition of factorial is probably more obvious than what you'd write in C, or Perl, or even Lisp).

Wait: we said earlier that Haskell makes a big deal about types; why
didn't we have to specify a type for this function? Our Haskell
interpreter inferred the type of `factorial` automagically;
let's see what it found:

What this tells us is thatPm_tut> :t factorial factorial :: Num a => a -> a

`factorial`is a function from things of type

*a*to more things of type

*a*, as long as type

*a*is numeric (that is, inherits from type

*Num*). (If you have a bit of background in symbolic logic, think of the type as saying "numeric

*a*implies

*a -> a*".)

#### 2.2. Factorial With Pattern-Matching

We can define `factorial` a bit more idiomatically:

Note that the two cases of the function (base and recursive) are more apparent here; there's less cruft around the actual mathematical part of function. What happens here is that, when Haskell sees a call tofactorial 0 = 1 factorial n = n * factorial (n-1)

`factorial`, it tries to match patterns from top to bottom. (If you've done any Prolog hacking, this'll look familiar, although Prolog's pattern-matching is much more powerful than Haskell's.) That means that switching the order of the patterns is a bad thing:

Any calls to this factorial function will not terminate: the recursive pattern always matches, so you'll never get to the base case.factorial n = n * factorial (n-1) factorial 0 = 1

Another way to do it (sound familiar?) is to do the arithmetic on the left-hand side, and coincidentally in the pattern:

This isn't exactly a great way to do it, but it shows that patterns in Haskell are more flexible than you might first think: they're not just simple argument lists.factorial 0 = 1 factorial (n+1) = (n+1) * factorial n

#### 2.3. Recursively, Factorial

"Wait a minute," you might ask, "all this recursion has gotta be pretty slow. Isn't there a better way?" Yes, in fact: we can use tail recursion. What tail recursion amounts to is doing all the calculations before the recursive call; that way, we don't need to keep anything on the stack, and we can optimize a set of recursive calls into a while loop (see your favourite intro-CS textbook for details). In Haskell, that looks like this:

In the tail-recursive functionfactorial n = tr n 1 where tr 0 f = f tr n f = tr (n-1) (n*f)

`tr`, we're accumulating a partial result into the second parameter. Eventually, we hit the base case (n=0), and return the result.

What's more interesting is the fact that we've defined
`tr` as a a purely local function inside a *where*
clause. This is handy for not cluttering up the local namespace. There
aren't any delimiters on the where clause: the interpreter figures out
what's going on based on the *layout rule*: basically, "indent your
code the way you usually would and everything'll be fine". (Yes, this
is similar to Python. No, you won't go to hell for it.) Anyways,
patterns obviously work just fine in where clauses.

#### 2.4. Use The Builtins, Luke!

All this messing around with recursion is kinda fun, but if you've
ever played Perl Golf you're probably wondering if there isn't a more
concise way to do it. There is: Haskell's *Standard Prelude*
(think of it as stdlib in Haskell) defines a bunch of useful functions,
among them one called `product`:

Nowfactorial n = product [1..n]

*that's*a lot better: short and to the point. Of course, it raises a couple of questions:

- Why just
`product`? Why not a more general version for doing arbitrary binary operations on lists? - What happens when
*n*is zero?

`product`.

#### 2.5. Foldl? What's That?

The Haskell Standard Prelude defines `product` like this:

That's not exactly enlightening. (There's a lot going on here.) What's thisproduct = foldl (*) 1

`foldl`business?

Generic list-combining, that's what. `foldl` takes a
binary function, a start value, and a list, and "folds" the list into a
scalar from the left. For instance, `foldl (*) 1 [a b c d]`
is about the same as `((((1 * a) * b) * c) * d)`. (There's
another function `foldr` that does about the same, except
from the right.)

So what happens when we call `product` with an empty list
(which is what Haskell generates from `[1..0]`)? For that,
we need to look at the definition of `foldl`:

With an empty list,foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs

`foldl`just returns the starting value (in this case, 1).

## A short digression on extensionality

Wait a minute:

foldltakes three parameters (operator, start, list), but in our definition ofproductwe only passed two! Shouldn't that be:instead? As it turns out, it doesn't really matter, and we can blame that on something calledproduct xs = foldl (*) 1 xsextensionality, which basically means that we can (usually) cancel out bound variables on both sides of an equation. Extensionality eventually leads us to something called themonomorphism restrictionand a lot of probably unnecessary pain. (See the Haskell Report, section 4.5.5, for all the gory details -- or just forget about it for the moment.)

There's something else we can learn from this code: we can convert an
infix operator (in this case, `*`) to a general function by
wrapping it in parens. So if we wanted to take the sum of a list of
numbers, we'd do it thus:

(End-of-line comments in Haskell are introduced by two dashes followed by something that isn't punctuation. I'm sure that must've made sense to someone at some time.) Similarly, we're not restricted to folding numbers. We can find out whether a list of booleans contains any true elements:sum xs = foldl (+) 0 xs -- this is in the Standard Prelude, too

or contains all true elements:or xs = foldl (||) False xs -- this is also in the Prelude

If we have a functionand xs = foldl (&&) True xs -- so is this

`prime`that tests a number for primality, we can check a list of numbers:

anyprime xs = or (map prime xs) -- map does what you'd expect allprime xs = and (map prime xs)

But back to hello world -- er, I mean, back to factorial.## foldl and type signatures

foldl's type signature is:What this says is thatfoldl :: (a -> b -> a) -> a -> [b] -> afoldltakes a binary function onas andbs, a scalara, and a list ofbs and returns ana. It's interesting to note that the list elements don't have to be the same type as what they're folded into. For instance, we can re-writeallprimelike so:If we're only going to useandprime p n = p && prime n allprime xs = foldl andprime True xsandprimeonce, we don't really want to have it clogging up the symbol table, so we can write it inline as alambda function:See Section 3.1 of AGItH for more on lambdas.allprime xs = foldl (\p n -> p && prime n) True xs

#### 2.6. Lazy Factorials

So far, all the factorial functions we've defined have been a bit limited. They calculate one factorial, return it, and that's it. If you want to find another factorial, you're going to repeat a lot of work. Wouldn't it be nice if we could get Haskell to generate a list of factorials for us?

factorials = scanl (*) 1 [1..]

`scanl`is similar to

`foldl`, but it generates a list of successively reduced values. In this case,

`scanl`gives us

`[1, 1*1, (1*1)*2, ((1*1)*2)*3, ...]`-- we're basically doing a

`foldl`on successively longer prefixes of the list

`[1..]`, which generates the positive integers.

Generating a list of all factorials sounds like an impossible task,
but as long as we never try to use the *whole* list, it isn't a
problem. For instance:

Pm_tut> take 10 factorials [1,1,2,6,24,120,720,5040,40320,362880] Pm_tut> factorials !! 24 620448401733239439360000

`take n xs`returns the first

*n*elements of the list

*xs*, and

`factorials !! 24`is Haskell for list indexing (in Perl, we'd write

`$factorials[24]`). (Did I mention that Haskell uses bignum ints by default?) What's going on here is that Haskell's generating only as many elements as it needs to in order to satisfy our requests. If we ask for the factorial of a ridiculously large number, we'll have problems:

Pm_tut> factorials !! 65536 ERROR - Garbage collection fails to reclaim sufficient space Pm_tut>

**Edit 2004 June 24:**

`s/LISP/Lisp/g`-- thanks hding- Corrected extensionality discussion, and did
`s/any/or/ ; s/all/and/`-- thanks tmoertel - Added some examples to
**1.2** - Added a quick overview of currying.
- Added a digression on
`foldl`'s type, with a little bit on lambda.

`--
F
o
x
t
r
o
t
U
n
i
f
o
r
m
Found a typo in this node? /msg me
% man 3 strfry
`