XXX

Hi, Redditers -- this was somehow linked directly out of my darcs
repository and is not at all complete.  Additionally, I decided there
are a ton of other Haskell tutorials out there so I sorta abandoned
working on this back in June 2006.

With that said, it looks like the initial feedback was sorta positive
(despite some embarrassing errors) so I guess you might as well read and
enjoy, and maybe I'll finish it someday.

  -- Evan Martin, 13 July 2007

XXX



= Haskell for Programmers
Many people have written Haskell tutorials, but when I learned Haskell
they didn't present it in a way that made sense to me.  The author's
perspective always leaks through in the exposition.

So here's my perspective, and what I expect of you: you hate it when
people waste your time by using more words than necessary; you should be
comfortable programming (particularly with a high-level language, such
as Perl, Python, or Ruby) but maybe not so much with "funky languages";
you are interested in learning new things for their own sake; you are
interested in practicality; you learn through examples ('strings look
like "foo"') better than abstract statements ('strings are sequences of
characters surrounded by double-quotes').

Some brief style tips on getting the most out of this:
- The exercises included are intended to be worked through, at least
  mentally if not at a keyboard.  Sometimes they introduce new
  concepts.
- Jargon and new terms are typically //emphasized//.

=== Why Haskell is Worth Learning

You're already here, so there's not a lot of convincing to be done.
Instead, here are the reasons I think you //ought// to be here.
- Haskell is different than what you're comfortable with.  Another way
  of saying that that is that it's "Seriously Weird", but in a good way.
  It has changed the way I think about programming.
- Haskell code is beautiful, and that makes it enjoyable to both consume
  and produce.
- Some people write Real Programs with it.  Notably: Perl6 (pugs) and
  darcs.  I'm not promising much here, but I also think this is less
  important; if you can get your job done using Perl, then go get your
  job done.
- Some people argue it is the future of programming.  See,
  [[sweeny.pdf]] for a discussion of this by one of the creators of the
  game Unreal.  Even if the language of the future is not Haskell, it's
  likely some of Haskell's ideas will percolate down to more popular
  languages much in the way garbage collection did in the last decade.

=== The two things you have to get over to learn Haskell

1. Haskell is not a just a new syntax for a language you already know.
Many languages are just new paint jobs on the same car.  Haskell
switches out some more fundamental ideas, which has the following 
important effects:
- Haskell uses some terms (such as "class") that are found other
  languages, but with a meaning that is very different.  Once you
  understand things fully you can sorta squint and understand the name
  choice, but until then it's better to just pretend that the used the
  same name for an entirely different thing.
- Haskell does not have a lot of features you may be comfortable with
  and expect to have a new language to have.  You will become frustrated
  if you try to "translate" an existing program or construct into
  Haskell.  So instead of "how do I do [x] in Haskell?" (where [x] is
  e.g. "read a line of input from the user"), try to think of
  problems in terms of "how do I achieve [x]?" ("how do I make my
  program work with user input?").

Another way of saying this is: this will be the best for you if you
relax, and try to go with the flow.

2. Haskell has a bunch of features you may have never seen before, and
they require some head scratching.  In particular, understanding Haskell
requires thinking at a //higher level of abstraction// than other
programming languages, and requires practice.  But hopefully that is
part of why you're here: you want to learn something.

=== Getting Set Up

There are multiple implementations of Haskell, but you should use GHC;
everyone else does.  Debian/Ubuntu users: apt-get install ghc6.  Others:
{XXX download link}.

GHC comes with "ghci", which is a read-eval-print loop that lets you
type in expressions interactively and see their results (like Lisps,
"irb", or "ipy").  However, for various reasons you can't really write
full programs with it.  I recommend instead writing code in a text file
like you would another language, and then loading it up into ghci to
play with it:
  ghci test.hs
You can then hit ctl+d to exit.

Below, I show input to ghci by showing the prompt as a ">".

== First Steps
=== First, an Apology
Some things (such as printing text) that are simple in other languages
are more complicated in Haskell, so please forgive me for skipping "Hello,
world".  (It's a trivial single line of code, but explaining it is more
involved.)

Similarly, error messages can be difficult to understand until you get
what's going on, so don't worry about them too much yet.

=== Diving in
Fire up a text editor and write some code.  (Or copy'n'paste this.)
  myint = 2

  y = myint + z
  z = 1

  -- single-line comments start with a double-hyphen.
  -- infinity is one greater than... well, infinity.
  infinity = infinity + 1

  mylist = [1,2,3]
Try loading this into ghci.

All Haskell code is a collection of //definitions//: that first line means
"define ##myint## to stand in for 2".  This is different than in other
languages: in Haskell, a given name (like ##myint##) can have only one
meaning, so it's an error to later try to give it a different
definition.  (In C++-speak this means everything is defined "const", and
there's no way to turn it off.)

How can a collection of definitions actually do anything useful,
especially when the whole point of a program is to transform some input
into some output?  That's part of the magic of Haskell!  And it will be
explained.

At the ghci prompt, you can type in //expressions// (the right side of an
equals sign of a definition) and ghci will print out what the expression
evaluates to.  Try a few:
  > 1 + 1
  2
  > myint
  2
A few caveats to note upfront so you don't get confused:
- Note that you can't make new definitions here.  Only expressions are
  allowed.  (This is why, earlier, I suggested you get into the habit of
  putting code into a file to test it.)
- If you get an error about "##No instance for (Show ...##", what that
  means is that you typed a valid expression, but there is not a defined
  way for Haskell to show it.

So what about ##y##?  Though it's defined in terms of something that
comes later, since these are all just definitions it doesn't really
matter which one comes first.  (Using "later" in the previous sentence
was a bit misleading.)  In fact, you can even define something in terms
of itself, and later we'll use this a lot.  Ask ghci for the value of
##infinity## -- infinite loop!  (You can hit ctl-C to interrupt it.)

This demonstrates a few of the great magics of Haskell: there is no
mutation (once a name is bound to a definition, there's no changing it),
there is no specific order of evaluation (the order in which things are
computed doesn't really matter), and things can be defined in terms of
themselves.

=== Functions
Functions are very fundamental to Haskell, and so calling a function
gets a very simple syntax -- just a space between the function and its
arguments:
  > sin 1             -- a builtin mathematical function
  0.8414709848078965
  > length mylist     -- list length
  3
  > div 6 3           -- integer division:  divide 6 by 3
  2
To nest function calls, you must use parenthesis.  ##sin div 6 3## means
"call ##sin## with three arguments: ##div##, 6, and 3", while ##sin (div
6 3)## means "call ##sin## on the result of dividing 6 by 3".  This
syntax is weird at first, but it'll eventually feel natural.

To define a function, it's written as below.  (Again, since this is a
definition, it must go into your test program and then reloaded into
ghci.)
  -- a one-argument function:
  oneLessThan x = x - 1
  -- a two-argument function:
  add x y = x + y
  -- a function that takes another function as an argument:
  applyTwice f x = f (f x)
Functions themselves are values.  You can give them names, pass them as
arguments to other functions, and put them in lists.  Here's an example
using ##applyTwice##:
  > applyTwice oneLessThan 5    -- one less than (one less than 5)
  3
You can create a function as an expression with the following
syntax:
  > applyTwice (\x -> x + 1) 5
  7
The backslash introduces a function (it's simulating a lambda: λ), the
bit following it gives the arguments names, and the bit after the arrow
is the body of the function.  We could have defined "add" equivalently
like this:
  add = \x y -> x + y

Note that there is no "return" keyword in Haskell. One way to look at it
is that these functions aren't "returning" anything.  Instead, when you
write "oneLessThan 2", you're just substituting 2 for x in the
definition of oneLessThan.  Along those lines, instead of using 
terminology like "call add with two arguments", people often say
"//apply// add to two arguments".

Any two-argument function can also be used with a special syntax, which
puts the function name between the two arguments:
  > 6 `div` 3
  2
  > 20 `add` 30
  10
This sometimes makes code clearer, and has no special meaning beyond
that.

In fact, even operators like + are functions, except that they default
to working in the "between" mode and they obey the normal mathematical
notions of precedence.  You can use them as regular functions by
surrounding them with parenthesis:
  > (+) 1 2
  3

In Lisp, (nearly) everything was a list.  In Smalltalk, (nearly)
everything was an object.  In Haskell, (nearly) everything is a
function.  Much like in Lisp and Smalltalk, using a single concept
pervasively allows for powerful composition throughout the language.

Exercises:
  1) Precedence.
     a) Write an expression to find the the length of the hypotenuse of a
        right triangle whose sides are 5 and 9.  (The exponent operator is
        ##**##, and the square root function is ##sqrt##.)
     b) What does "sqrt 25 + 81" mean?
  2) Parenthesis.
     a) Write an expression for the sum of the first three integers, using
        addition only like a regular function that takes two arguments to
        its right.  Pay attention to getting the parenthesis right!
     b) Now write it as you would in normal code.

Answers:
  1) a) sqrt ((5**2) + (9**2))
        Actually, the parens around the exponents aren't required, due to
        operator precedence.  But you may as well write them if you're not
        sure.
     b) sqrt 25 + 81 =
           5    + 81 =
              86
        The one precedence rule that will bite you for a while is that
        function calls have higher precedence than all the operators.
        This is sometimes useful and sometimes annoying.
  2) a) (+) 1 ((+) 2 3)
        It looks a bit like lisp, doesn't it?  These languages all have their
        roots in some similar areas of mathematics...
     b) 1 + 2 + 3
        Since addition is associative, we don't care whether that's
        (1+2)+3 or 1+(2+3).

=== Types
Haskell is statically typed.  Static typing has negative associations
for many programmers, but I like to think it's just because they haven't
been exposed to a good treatment of it yet.

Every well-formed expression in Haskell has a type.  You haven't seen
any yet because Haskell figures out types out for you, but they're
still there.  (This is one of the reasons static typing in Haskell is
pleasant:  you almost never have to write types out, but they are always
in the background helpfully verifying your code is correct.)

You can ask ghci for to display the type of an expression by using the
":t" command.  (This is a ghci-specific command and not part of Haskell.)
  > :t myint
  myint :: Integer
  > :t mylist
  mylist :: [Integer]
The double-colon can be read "is a" or "has type".  The square brackets
around a list type can be read "a list of".  Putting them together, that
last line reads: "##mylist## is a list of integers".  (A list can only
contain one type.  Another way of saying that is that all elements in a
list must be the same type.)

If you want, you can annotate your code with types, using that same
syntax.  It sometimes helps explain your thinking, and also can help
catch errors.  Trying to load this code:
  one_third :: Integer
  one_third = 1 / 3
will result in an error that looks like this:
  No instance for (Fractional Integer)
  arising from use of `/' at [...]
because / results in a fractional number, but you've declared that
##one_third## is an Integer.  (You can use ##div##, discussed above, for
integer division.)

=== Fancier Types
Haskell types often involve //type classes//, which we'll discuss later,
but for now you need to at least recognize them when you see them.
(First, keep in mind the disclaimer from the beginning: these are very
distinct from the classes in object-oriented programming.)
  > :t 3
  3 :: (Num t) => t
"Num" here is a type class.  Everything before the => sign is a
constraint on the type, and every after the => sign is the actual type.
This type is saying that 3 can serve as any type "t" as long as "t" is
an //instance// of Num (which is short for numeric).

For example:
  > :t (3 :: Integer)
  (3 :: Integer) :: Integer
  > :t (3 :: Rational)
  (3 :: Rational) :: Rational
  > :t (3 :: String)
      ...
      No instance for (Num String)
Both integers and rationals are numeric, but strings aren't.

=== Function types
Function types are written with an arrow, with the argument on the left
and the result on the right:
  > :t oneLessThan
  oneLessThan :: (Num a) => a -> a
##oneLessThan## takes a number and gives you back another number of the
same type.  If you want, you can read the arrow as "maps", like in the
mathematical sense, and to sound like you have a math degree you can say
"oneLessThan maps numbers to numbers".

Multi-argument function types are written with a sequence of arrows.
Let's look at ##add##, our addition function:
  > add 3 4
  7
  > :t add
  add :: (Num a) => a -> a -> a
What does that type mean?  It'll help if we add some parenthesis to make
an equivalent definition that shows how the arrows are grouped:
  add :: (Num a) => a -> (a -> a)
That type says that ##add## takes a number ("a") and produces another
function -- the one in the parenthesis at the end.  Then, that new
function has the same type as ##oneLessThan##: it takes another number and
produces the final answer.  You can even make these two parts explicit
with parenthesis:
  > (add 3) 4     -- equivalent to the above
  7
First we pass 3 to add and get a function back, then we pass 4 to that
function and get 7.  Logically, this intermediate function must add 3 to its
argument.

You can //partially apply// add to grab that intermediate function.
In your test file, you can now define a function just like
##oneLessThan## but with a simpler definition:
  oneMoreThan :: Int -> Int
  oneMoreThan = add 1

If you take a step back at this point to review you'll realize that
every function in Haskell takes only a single argument, and that
multiple-argument functions are built by chaining these simpler
functions together.  This is sometimes known //curried functions//.

Exercises:
  1) Write a function that takes three Ints and sums them.
     What is its type?
  2) Write a function that takes a function and an integer and applies the
     first to the second.  The following code should work:
       > apply oneLessThan 3
       2

Answers:
  1) addThree :: Int -> Int -> Int -> Int
     addThree x y z = x + y + z
  2) apply :: (Int -> Int) -> Int -> Int
     apply f x = f x

=== Lists, Strings, and Polymorphism
Define a few lists in your test program and load it back into ghci:
  -- strings are double-quoted and allow the normal backslash escapes.
  strings = ["hello", "world"]
  -- characters are quoted with single quotes, like in C.
  chars = ['a', 'b', 'c']

  -- ranges are just shorthand for writing all the elements out.
  ints = [1..3]
  chars2 = ['a'..'c']  -- same as "chars"

You can use ghci to print these lists out if you'd like.  chars is a bit
of a surprise:
  > chars
  "abc"

In Haskell, a string is just a list of characters, and double quotes are
just a shorthand way of writing the list out.  You can confirm this by
looking at the types of some of these:
  > :t "test"
  "test" :: [Char]
  > :t strings
  strings :: [[Char]]
strings is a list of lists of characters.

This also means that all normal list operations will also work on
strings.  For example, ##length## gives the ##length## of a list and
##(++)## is the list concatenation function:
  > length ints
  3
  > length ['a'..'z']   -- how many letters in the alphabet?
  26
  > ints ++ ints
  [1,2,3,1,2,3]
  > "hello" ++ "there"
  "hellothere"

What is the type of ##length##?
  > :t length
  length :: [a] -> Int
The "a" here in the type is like the "t" we saw in type classes, but
without a constraint.  This means that for any type a (sometimes read as
"alpha"), ##length## takes a list of a and produces an integer.  The
length of a list is independent of what the list actually contains.
This is called //(parametric) polymorphism//: ##length## works for lists
of any type.

Exercises:
  1) What is the type of [], the empty list?
  2) For each of the following, is it a valid list?  If so, what is its type?
     a) [myint, sqrt 2]
     b) [[myint], []]
     c) []:[]
     d) [(+), (-)]
  3) For each of the following functions, what is its type?
     You can check your answers using ":t".
     a) head  (given a list, gives you the first element in the list)
     b) tail  (given a list, gives you everything but the first element in
        the list)
     c) concat  (given a list of lists, gives you the result of
        concatenating the lists together)

Answers:
  1) The empty list can be a list of anything, so it has type [a].
  2) a) No.  ##myint## is an Integer, while the result of ##sqrt## is
        fractional.
     b) [[Integer]]
     c) [[a]]
     d) This is a list of functions, and they all have the same
        type.  So the list has type (Num a) => [a -> a -> a].
  3) a) [a] -> a
     b) [a] -> [a]
     c) [[a]] -> [a]

= XXX BELOW HERE THINGS GET UGLY AND NEED EDITING

=== More on lists
XXX fit me in elsewhere
A Haskell list is similar to a Lisp list or a linked list in other
languages.  A list is recursively defined as either empty, [], or as
a value followed a list.  The "followed by" operator is a colon, and its
right side must be a list of whatever is on the left side.
  > 1:[]
  [1]
  > 1:2:3:[4,5,6]
  [1,2,3,4,5,6]
Again, using 'a':'b':[], ['a','b'], and "ab" are equivalent, though the
last one is easiest to read.


  ones = 1:ones    -- this will be explained below

Going back to the test program, you'll see that the definition of ones
is a 1 followed by... itself.  The list goes on forever!  If you tell
ghci to print it it'll go on forever until you hit ctl+c.


2) What is the type of (:), the list construction operator?
2) It takes something on the left and a list of somethings on the right,
   so it has type a -> [a].
  4) mystery x = x : (mystery x)
     a) What does this function do?
     b) What is its type?
  4) This function is actually a builtin, called "repeat".
     a) It creates an infinite repeating list of out of any value.
     b) a -> [a]

=== More Functions and Pattern Matching
Let's define an "isEven" test that returns a Bool (whose two values are
True and False -- capitalization here seems weird but there's a good
reason for it that will become apparent later).
  isEven :: Int -> Bool
  isEven x = if x == 0 then True else not (isEven (x-1))
Here's a better definition:
  isEven 0 = True
  isEven 1 = False   -- not necessary, but it serves as an example
  isEven x = not (isEven (x-1))
Note here how we define isEven in multiple lines, by breaking the cases
out.  This sometimes make code clearer than having a chain of if-then
tests, and is quite common in Haskell code.

Of course, there's also a "mod" function that could be used to compute
this directly:
  isEven x = (x `mod` 2) == 0

Now let's define our own length function, called "len".  In Haskell, as
in many functional languages, you use recursion for everything.  (This
requirement is even stronger in Haskell -- since you can't alter
definitions, there would be nothing to do inside the body of a
hypothetical "for" loop.  There really is no looping construct in the
language.)

Thinking recursively quickly requires practice at first and then seems
really natural once you've got it.  For len, you define its type:
  len :: [a] -> Int
a base case:
  len []     = 0
and the induction step:
  len (x:xs) = len xs + 1
(If you put those three lines together your test file, you'll see that
the equals signs line up.  This is just a style thing.)  The new thing
here is the way we wrote the function arguments, where we gave names
to pieces of the input.  This is called //pattern matching//: the last
line here works for inputs that are lists of at least one element, and
they call that element "x" and whatever's left of the rest "xs".  Since
all lists follow one of the two patterns we've defined, len is now
defined for all lists.

In fact, if your patterns don't cover all inputs and you run ghc with
the -Wall flag, you'll get a warning:
    Warning: Pattern match(es) are non-exhaustive
             In the definition of `foo': Patterns not matched: _ : _


Here's a function that counts the number of times a certain element is
in a list.  Since we test whether our "a"s are equal, we must constain
them with the "Eq" type class, which covers all types where equality
is meaningful.
  countFind :: (Eq a) => a -> [a] -> Int
  countFind target []     = 0
  countFind target (x:xs) = if x == target
                              then 1 + (countFind target xs)
                              else countFind target xs

(A brief word here on syntax: Haskell is defined in terms of semicolons
and curly braces, but if you indent your code properly they are
optional.  You don't even need to learn the rules for //layout//, as it's
called, as long as you follow good style.  In general, if you're
continuing a line, just indent a bit more and you're fine.)

Note that an "if" must always have an "else" branch, as the whole thing
(if ... then ... else) must always evaluate to a single value and type.

It's a pain to keep passing that "target" name around, since it's 
always the same value.  Here's another way of writing that function:
  countFind target list = countUp list where
    countUp []     = 0
    countUp (x:xs) = if x == target
                       then 1 + (countUp xs)
                       else countUp xs
Note the new keyword "where" at the end of the first line.  The where
keyword lets you introduce new definitions within an expression.  Since
target is in scope inside the body of countFind, countUp doesn't take it
as a parameter.

Also note that we didn't write out a type for countUp.  We could, but
its type is obvious from its context and the compiler can figure it out
anyway.

Let's redefine the hypotenuse function using where excessively:
  hyp a b = sqrt (a2 + b2) where
    a2 = square a
    b2 = square b
    square x = x**2
Here, we've defined both plain values (a2, b2) and a function.

Exercises:
  1) Write a function that counts how many times the substring "ab" occurs
     within a string.  (Hint: this section was about the pattern matching.)

Answers:
  1) abCount :: String -> Int
     abCount []           = 0
     abCount ('a':'b':xs) = 1 + abCount xs
     abCount (x:xs)       = abCount xs

# vim: set ts=2 sw=2 tw=72 et :