Thursday, April 30, 2009

Haskell - Lists

Haskell - Lists
Lists in Haskell are defined by square brackets, [].  In ghci, declaring a list is as simple as:
Prelude> [1,2,3]
[1,2,3]
Lists can be of any length, indeed you can type in the following (although I wouldn't recommend it!)
Prelude> [1,2, .. ]
[1,2,3,4,5,6,7,8,9,10,11,12....]
To create an empty list, type the following:
Prelude> []
[]
Lists must be all the same type, if we try to declare a list with the following, we will get an error
Prelude> [1,3,5,7,"nine"]

<interactive>:1:7:
No instance for (Num [Char])
arising from the literal `7' at <interactive>:1:7
Possible fix: add an instance declaration for (Num [Char])
In the expression: 7
In the expression: [1, 3, 5, 7, ....]
In the definition of `it': it = [1, 3, 5, ....]
What the interactive session is telling us here is there is a type incompatibility between Num and [Char] and suggests some possible fixes.
Operating on Lists
To concatonate two lists you use ++
Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
To add an element to a list use the cons operator :
Prelude> "Nate" : ["Bill","Ted","Stephen"]
["Nate","Bill","Ted","Stephen"]
List Comprehensions
List comprehensions are really a thing of beauty, although, the Haskell Wiki labels them as syntatic sugar.  I think they add an element of beauty and simplicity.  Comprehensions follow the basic syntax1:
[ e | q1 .., qn], n >=1
where the q1 qualifiers are:
  1. generators:  p <- e, where p is a pattern of type t and e is an expression of type t
  2. guards: an expression that evaluates to a bool
  3. local bindings: provide new definitions for use or subsquent generators or guards
Here's an example of how to generate a list of all even numbers between 1 and 50 using comprehensions:
Prelude> [ x | x <- [1 .. 50],even x]
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50]
Granted, you can accomplish the same thing using arithimetic sequences:
[2,4 .. 50]

But take a look at how to solve Project Euler question #1 with list comprehensions:
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
Breaking down this line into parts,
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x <- [1 .. 999] is a generator, it's using an arithimetic sequence to get all the numbers between 1 and 999.
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x `mod` 3 == 0 || x `mod` 5 == 0 is a guard or predicate.  Only when this expressions is true is it "passed" to the new list.
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x is the new list of all the numbers between 1 and 999 that satisfy the predicate.  Then, x becomes part of the last expression, the foldr function.
foldr, or reduce, applys the the operator + in this case to the seed value 0 and each element in the list.

Sunday, April 19, 2009

Learning Haskell

Why am I learning Haskell?
There are several different answers, but there are a few that stick out more than others.  While I was learning F# and making my way through ProjectEuler problems, I was getting frustrated with running into type issues.  Here I was looking at some beautiful, clean and consice code, and then watching it get all cluttered up with F#'s casting syntax.1
Another reason is when I finally solved a Euler problem and quite proudly submitted my solution, I would browse the other F# solutions and became dissapointed with what some others where submitting.  I was looking at F# syntax, but it was all procedural style.
F# is a great language and I really enjoy writing with it, and will continue.  However, I wanted to learn functional programming on a language that doesn't allow me to break the rules.
Getting Started with Haskell
I am using the GHC implementation, which can be downloaded here.  With the download you get three components:
  • ghci - an interactive interpreter
  • ghc - compiler
  • runghc - runs Haskell programs as scripts
My examples will be in ghci, but I'll note when I switch.  My development environment is a Mac, so the command window is the bash shell.
After installing Haskell, launch Terminal and type in ghci:
$ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude>

Once the ghci is loaded, we see several libraries being loaded, ghc-prim, integer and base. Details on these packages can be found here.
The Prelude> prompt means the prelude library is loaded, sort of shorthand for the prelude 98 standard.  Like other Unix shells, what you see for the prompt is configurable, but I"ll leave the default.
One of the more import things to remember when you are starting is, :? This will list commands available from the prompt.  To execute an operating system or shell command, type in :! So to see what directory you are, type in
Prelude> :!pwd
/Users/nathanhoellein/HaskellProjects

To change directories, you need the :cd command.
Prelude> :cd ./ch03//
Prelude> :!pwd
/Users/nathanhoellein/HaskellProjects/ch03

Another command that's interesting is
:browse
It lists all names loaded by module.
Interactive Haskell

The ghc interpreter functions just like the F# interactive console, you can type in code snippets and perform arithmetic, except you don't have to end each line with ;;.
You can perform calculations using infix or prefix syntax:
infix:
Prelude> 2 + 3
5

prefix
Prelude> (+) 2 3
5

Integers can be large, see what happens when you want to know what 2 ^ 100 is:
Prelude> 2 ^ 100
1267650600228229401496703205376

Whereas in F#, you have to use doubles and you get a little different output:
> 2.0 ** 100.0;;
val it : float = 1.2676506e+30

What I find pleasing is you can see F#'s roots, the keyword "it".
The "it" variable sort of holds on to the last expression that was evaluated.
Prelude> 2 ^ 100
1267650600228229401496703205376
Prelude> it
1267650600228229401496703205376

We see the same in F#:
> 2.0 ** 100.0;;
val it : float = 1.2676506e+30
> it;;
val it : float = 1.2676506e+30

Other arithmetic stuff within Haskell:
Prelude> 2 - (-8)
10
Prelude> 2 + (-8)
-6

And booleans:
Prelude> True || False
True
Prelude> True && False
False

Like basic algebra, order of operations matter:
Prelude> (1 + 3) ^ 4
256
Prelude> 1 + (3 ^ 4)
82

That's a nice start for now, next post I'll cover lists.

1 - Yeah, I know it's really the .Net runtime