Haskell is a functional programming language, eschewing side effects for pure mathematical simplicity. Programming in functional languages can be a bit of a challenge to people used to standard, imperative methods. Don't fret, Builder AU's got you covered with this short quick start to Haskell.
Functional languages use a different style of programming than the traditional imperative method (which is used by languages such as Java, C or their derivatives). Rather than writing out a "recipe" for the program listing each of the steps we want taken in the order we want them, a functional program is a single expression, which may have many parts.
Languages based on a functional paradigm are a hot topic in the programming world at the moment, their fans say that functional code is much shorter, easier to understand and less prone to errors. Detractors of functional languages say that they are terse, slow and make it harder to understand what's happening under the covers.
Why use Haskell?
- It's free — Haskell is open source technology, and there are a number of free to download and free to use compilers and interpreters.
- It's under active development — Haskell is a favourite of the academic world, and right at this moment is the topic of a number of PhD and Master's theses aiming at making it faster, clearer and more powerful. Over the past five years research into optimising functional languages has transformed Haskell from a academic toy into a serious choice for high performance applications.
- It's fast (enough) — While not quite a match for optimised C code, Haskell doesn't fare too badly on the speed front. The Computer Language Shootout puts Haskell at about twice as slow as C (for comparison, Java is one and a half times slower than C, and Ruby is 50 times slower).
- Lazy Evaluation — Objects are only computed when you need them, when you're writing in Haskell you can feel free to generate and use infinitely long lists, and the compiler will only do the work to compute the ones you use. The trade off is that working out exactly how much memory your lazy data types are using can be difficult.
- Higher order functions — Functions are always first class objects in functional languages. In fact, in Haskell, manipulating functions rather than variables is often the easiest and clearest way to write code.
- It's less error prone — The Haskell compiler is strict with regards to types, and since functions are generally prohibited side effects, once your code is compiled it's likely not to have memory related bugs. The Haskell Web site advertises this as meaning no core dumps, but in fact it eliminates a range of common, and difficult to diagnose, memory bugs.
- Compiled or Interpreted — Haskell code can be compiled into native machine code, for faster execution time, or interpreted in an interactive environment —- it's up to you. Haskell is one of the few languages where compiling and interpreting code is equally well supported.
Where can you get Haskell?
There are a number of good Haskell interpreters and compilers around, the most popular and stable being GHC — the Glasgow Haskell Compiler (and its interpreted sibling, GHCi) and Hugs. For this tutorial we recommend that you use GHC and GHCi as it's better supported, and supports a larger range of Haskell extensions.
The GHC download page has links for binary packages for all the major operating systems, and there are packages included in the package repositories of the most popular Linux distributions. There are instructions on the GHC site, so we'll let you sort out the install with them — once you've got everything up and running come back and we'll continue.
Once GHC is installed, open up a terminal and type ghci:
$ ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Prelude>
You'll be presented with the interpreter prompt. The word before the > character is the name of the module we're currently working in, Prelude is the base module — similar to the built-in library in other languages.
Like most interactive prompts you can use the interpreter like a calculator. Just type in the expression and hit enter:
Prelude> 3 + 4 7 Prelude> 10 * 34 340 Prelude> 7 ^ 329 108957006957880384854781400332988655104195780924346448594905101807142948743533497375319263496297652070491969771073582487659356699431175449777087388597611757900070061059734878450350888020156369740407014773814755940670361796273579035410270670889643488187096146596661961779984097607
Note that in Haskell the ^ operator stands for "to the power of", you can see that Haskell supports arbitrarily big numbers easily.
Let's start with writing a basic function. In another window open a file called Builder.hs in the same directory that you started GHCi and then type the following:
module Builder where fact 0 = 1 fact x = x * fact (x-1)
The first line says that the file contains a new module, called Builder. This module contains one function, the factorial function (which is a standard example, when writing recursive functions), which has two definitions. The first says that the factorial of 0 is 1, and the second says that the factorial of any other number x is that number times the result of fact called with (x - 1).
To load this module into GHCi, first save it, then in your interpreter type the following:
Prelude> :l Builder.hs [1 of 1] Compiling Builder ( Builder.hs, interpreted ) Ok, modules loaded: Builder. *Builder>
Now let's try the new function:
*Builder> fact 1 1 *Builder> fact 2 2 *Builder> fact 10 3628800 *Builder> fact 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 *Builder> fact (-2) *** Exception: stack overflow
This function works, but it seems it has a problem — it can't handle negative numbers. We can write a better version that will count down if the number is positive and count up if it is negative:
betterFact 0 = 1 betterFact x = x * betterFact (x `op` 1) where op = if x > 0 then (-) else (+)
This is a bit more complicated and includes some new concepts. Firstly in the last line we use a where statement to define a new variable op. Where statements can be used to make your functions clearer by replacing complicated or repeated code with words describing what that code does.
In this case, the variable op is a function — we use an if statement to make the variable either the minus (-) function, or the plus (+) function. Since functions are objects themselves, we can make variables equal to them as easy as that.
Finally, we use the variable as in infix function — meaning its arguments are on either side like arithmetic operators — by including it between backticks (`) on the second line. If x is positive then we use x - 1 as the next argument to betterFact, otherwise we use x + 1.
Map, filter and fold
In Haskell, there are no loops statements such as while or for, so if you want to do something multiple times, you must use recursion.
Looping is such a common need of many algorithms, so to make programming a bit easier the Haskell prelude comes with a few predefined functions for looping over lists. You may recognise the map, filter and fold functions from other functional languages. It's easier to just demonstrate what they do than it is to describe them.map
*Builder> map fact [1, 2, 3, 4] [1,2,6,24] *Builder> map (+ 3) [1, 2, 3, 4] [4,5,6,7]
The map function takes two arguments, a function and a list, and returns a new list containing the output of the function with each item in the list as a parameter. In the second example, Haskell's currying system allows us to take a function that normally accepts two arguments, and partially apply it to a single value (the number 3) to produce a new function that only accepts one argument, in this case a function that adds three to a number.
*Builder> filter (>2) [1,2,3,4] [3,4] *Builder> filter even [1,2,3,4] [2,4]
Filter runs a predicate (a function returning either true or false) over a list, and returns the list of items that satisfy (i.e. make it return true) that predicate.
There are two folding functions in Haskell: foldr and foldl. Both functions do the same task, but in different orders. Sometimes they'll return the same value:
*Builder> foldr (+) 0 [1,2,3,4] 10 *Builder> foldl (+) 0 [1,2,3,4] 10
In this case it's simple to see what's going on. Both functions sum the list by performing the function given on a counter (starting at the second argument, in this case 0) and each item in the list.
When we change the function however, the two functions return different results:
*Builder> foldr (-) 0 [1,2,3,4] -2 *Builder> foldl (-) 0 [1,2,3,4] -10
The reason is that foldr and foldl apply the functions in a different order. Foldr folds the list right over the function, while foldl folds left. You'll understand more when we implement the functions in the next section.
Implementing map, filter and fold
We can explain what the functions do in a sentence or two, so if the boasts of Haskell fans are accurate we should be able to implement them without too much effort. For these examples, it turns out that we can:
map2 f  =  map2 f l = (f (head l)) : map2 f (tail l)
Our map filter does just what it says on the tin: takes a function f, and a list and then applies the function to each item in the list in order. The built-in functions head and tail are used to manipulate the list — the head function returns the first item in the list, and the tail function returns the rest. The colon operator adds an item to the head of the list.
Putting it all together: The map built-in applies the given function to the head of the list then adds the result to the list created by calling map on the tail of the list.
We can make this function more succinct by taking advantage of Haskell's pattern matching system for arguments:
map3 f  =  map3 f (x:xs) = (f x) : map2 f xs
In this version, rather than the list l, we match the expression (x:xs) - it's still a list, but it has two named parts. The head of the list labelled x, and the tail is called xs. In this case, x is equal to (head l) in the last function, and xs is equal to (tail l).
filter2 f  =  filter2 f (x:xs) = item ++ filter2 f xs where item = if f x then [x] else 
Looking at the filter implementation we can see that it works in a similar way to map — the function is called on the head of the list, if it returns true, then the item is added to the list, otherwise it is not.
foldr2 f o  = o foldr2 f o (x:xs) = f x (foldr2 f o xs) foldl2 f o  = o foldl2 f o (x:xs) = f (foldl2 f o xs) x
Here you can see implementations of the two folding functions — the difference in the order of arguments. This demonstrates how the two functions produce different output when given some functions. With functions such as (+) the order of arguments is not important (5+4 is the same as 4+5), but there are many functions where it is significant — which is why there are two functions defined.
Flipping two arguments is a common need, so there's a function in the Prelude for it. Using flip we could have written foldl as so:
foldl3 f = foldr2 (flip f)
In this implementation, we don't even need to specify the last two arguments. Instead of defining a function that takes three arguments and produces a list, we define a function that takes one argument and produces a new function that takes two arguments and produces a list. Due to Haskell's currying system, you can use the two of them interchangeably.