Version 1.1¹

Examples:

Haskell list operations, stacks, and queues: ListOps.hs, ListTest.hs, Stack.hs, Queue.hs

Review

Recursive Definition of List

A list is a recursive structure. A list is either:

1. [], the empty list; or
2. head : tail, where head is the first element of the list, and tail is the rest of the list. Note: head may be any kind of thing; tail is a sublist, therefore a list.

The list [a, b, c, d] in head:tail notation:

a : b : c : d : []

What is the head of [1, 2, 3]? the tail? the head of the tail? the tail of the tail? the head of the head (!)?

Recursive Methods on Lists

The recursive structure of lists makes it natural to solve many problems by recursive methods. A few examples:

1. What is the length of a list (number of elements)?

   1. If the list is empty, it’s 0.
   2. Otherwise it’s 1 for the head + the length of the tail.

2. Find an element t in a list.

   1. If the list is empty, give up.
   2. Otherwise if the head is t, we’ve got it.
   3. Otherwise, find t in the tail of the list.

3. Find the sum of a list of numbers.

   1. If it’s empty, the sum is 0.
   2. Otherwise, return the value of the head + the sum of the tail elements.

4. Lists are equal if ???

Haskell Code

Haskell list operations, stacks, and queues:

• ListOps.hs
• ListTest.hs
• Stack.hs
• Queue.hs

Running Haskell

• Haskell is installed on merlin
  • ghci starts the Haskell interpreter in interactive mode
  • runghc MyFile.hs runs a Haskell script
  • ghc --make MyFile compiles the Haskell source file MyFile.hs and produces an executable file MyFile. You can then run it with the command ./MyFile
• You can install GHC (Glasgow Haskell Compiler) on your own computer:
  • GHC
  • The Haskell Platform (recommended) includes GHC and many important Haskell libraries.
• You can evaluate Haskell code on certain web pages, although there may be some limitations on what you can do (especially regarding input and output):
  • Try Haskell
  • FPComplete has a free online Haskell IDE and a School of Haskell with interactive tutorials
• For more information about Haskell, see haskell.org

Laziness

In most programming languages, when you call a function (or method), the expressions given as arguments to the function must be evaluated before the function can begin running. For example, in Java, foo(2, bar(x + 1)), the method foo needs to have the values of 2 and of bar(x + 1) before it can get started.

In Haskell, on the contrary, the evaluation of expressions is deferred until their values are really needed. This is called lazy evaluation. In the example above, if the foo function only uses its second argument when the first argument is greater than 10, then the second argument would never be needed in this case, so it would not be evaluated.

One advantage of lazy evaluation is that it’s possible to work with infinite data structures, as long as you use only finite parts of them. For example, the Haskell expression [1 ..] designates the infinite list of positive integers 1, 2, 3, …. But the list elements are generated only to the extent needed. So if your computation takes only the first 5 elements of the list, it can run.

Prelude> take 5 [1 ..]
[1,2,3,4,5]

A disadvantage of lazy evaluation is that it becomes harder to reason about when the values are produced and, consequently, how much memory the program uses.

For more information, read Lazy evaluation on the Haskell Wiki.