TFM:Prospering With Haskell

From ProgSoc Wiki

Jump to: navigation, search

Contents

Prospering With Haskell

Iain Sinclair, Ryan Shelswell and Peter Brownlow

Introduction[1]

This chapter provides an overview of the functional programming language, Haskell. Unlike the more entrenched imperative programming paradigm (languages such as C, Java and Python can be classified as imperative) where the focus is on telling the computer how to do something by providing the computer step-by-step instructions, programs written in a functional language tell the computer what needs to be done by providing the computer a series of definitions and letting the computer decide how it will handle these definitions. Other functional languages include Lisp (with an abundance of parentheses), Caml and bondi[2].

This chapter intends to provide a gentle introduction to this powerful, yet mind-bending (and -expanding) programming paradigm. Haskell has been chosen for our functional programming discussion due to its widespread usage in academia and other educational settings.

ProgSoc machines -- in particular niflheim -- have a Haskell interpreter, hugs, installed, so you will be able to follow the examples included in this chapter (and experiment on your own) by logging into the machine and typing hugs at the shell prompt.

Type Notation

In Haskell, every constant, variable and function has a type. Unlike other languages, Haskell is usually able to work out the type of an expression without a declaration. However, this type will be the most general possible. The Haskell programmer will often declare expression's type if it is ambiguous or complex. For example, to say "the function population is of type numeric":

population :: Num

The type class Num encompasses all numeric types - there is no distinction between, say, Int or Float unless specified by the programmer, either explicitly or implicity at run-time. Note that thickness is of type Fractional and population is of an indeterminate type that is a descendant of Num, but neither has an explicit type declaration:

population = 17041203
thickness = 0.2321

Truth values are of type Bool, and are either True or False. A single character is of type Char. Any ASCII character can be represented with a backslash followed by the corresponding decimal number, using C-like conventions.

The following are definitions of contstants (aka constant definitions):

eyes :: Int
eyes = 2

height :: Float
height = 175.8

absolute :: Bool
absolute = True

arafura :: Char
arafura = 'c'

bell :: Char
bell = '\007'

crg_return :: Char
crg_return = '\n'

tab :: Char
tab='\t'

backslash :: Char
backslash='\\'

quote :: Char
quote='\

These primitive types (Int, Bool, Char, Float) are used with versatile data types (lists, tuples, functions). Haskell permits the creation of new, user-defined algebraic and abstract data types, such as trees, queues or tables. You can build these types by putting together some of the existing types predefined in Haskell (such as those mentioned above) and by creating new type constructors yourself.

For example, let us create a binary tree:

data BTree a = Node a (BTree a) (BTree a) | leaf

This binary tree can consist of: (a) a leaf, the end of the tree; (b) a node with a value of the same type as all other values in the tree, and two leaves attached to it; or (c) a node as above with any number of descendant nodes attached to it, its children, its childrens' children etc etc, until eventually each branch is terminated with a leaf.

Lists

A list is a sequence of any type (including other list types). They can be thought of as unbounded arrays which may contain no elements, some elements, or an infinite number of elements. All of the elements of a list must be of the same type. For example, a list of integers would be represented as [ Int] in a type definition and in the form [1,2,3,4,5,6] as a literal. Strings are represented as lists of char, and can be written within double quotes ("") instead of individual characters within brackets ([]).

truth_values :: [Bool]
truth_values = [True,False,True,True]

num_lists :: [ [Int] ]
num_lists = [[],[22,67],[80]]

blossom :: [Char]
blossom = ['w','a','t','t','l','e']

blossom' :: String
blossom' = "wattle"

A tuple groups two or more (possibly differing) types, rather like a record in Pascal or a struct in C:

certificate :: (String,Int)
certificate = ("Glen O'Fathead",1967)

Recursion

Function types describe the type of a function's arguments, and the type that a function returns. There are no procedure or void-style functions in Haskell. A function must "take something", and it must "return something". (However, a variable or a constant could be considered a function without arguments or parameters.)

This is the area that defeats, at least temporarily, more people than any other in functional programming. You can't store or assign variables, and there are no for, while or repeat-until loops. Everything is just like a mathematical formula - you put in x and y and get a result. That's it. If you want to keep a value for future reference then you must define a function that calls itself, passing that value back to itself to be used again and again until a final result is calculated. Almost the same technique is used to implement loops - it is called recursion.

Let us define a function to calculate the factorial of a number (it's that '!' button on your calculator).

fac :: Int -> Int
	-- fac receives one integer as an argument and produces one integer
fac num | num == 0 = 1    -- factorial of 0 is 1
       | otherwise = fac (num - 1) * fac    -- e.g. 4! = 4 * 3 * 2 * 1

Note that everything to the right and on the same line as a comment marker (--) is ignored by the computer.

The predefined function map takes two arguments, a list and a function, and applies that function to every element in the list, returning the altered list. For example, consider the functions below:

allEven :: [Int] -> Bool
allEven list = and (map even list)
              -- 'and' returns True if all elements of the list are
              -- True, False otherwise

Polymorphic Types

There are also polymorphic types, which represent generic or unknown types. Polymorphic types `match' other types as long as that type is an ancestor of the type class(es) stated in the type definition (or, if there is not type definition, if the type allows the operations defined in the function and any subsequently called functions to be).

The in-built function show is a polymorphic function which converts its argument to a string. Its type,

show :: Show a => a -> String

contrains the variables passed to it as arguments to be of a type that inherits from type class Show.

List Manipulation

Lists can be constructed with extremely compact and elegant expressions. For example, a function which returns a list of even square numbers up to a specified limit:

evenSq :: Int -> [Int]
evenSq limit = [x*x | x <- [1..limit]]

List element-selection functions

insect = head "bear"
bird = tail "beagle"
complete xs = init xs ++ [last xs]

With the zip function, one can 'zip' the elements of n lists together to return a list of n-tuples, and of course do the reverse.

Main> zip [1,2,3,4,5,6] ['a','b','c','d','e','f']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e'),(6,'f')]

List operators

(!!) :: [a] -> Int -> a
Main> "string" !! 5
'g'

You will have noticed by now that the first element in a list is denoted by !! 0.

New Types

Haskell provides ample facilities for creating new types. The new type, like Haskell's primitive types, is `constructed' by specifying the states it can assume. These states are called constructors, and must begin with capital letters. For example, the Bool type is comprised of the True or False constructors.

data Bloom = Azalea | Waratah | Bottlebrush | Gladiola | Sundew | Rose
deriving (Show, Eq)

The last line is significant - it allows the values Azalea etc to be printed on the screen as "Azalea" etc and to be tested for equality (e.g. Azalea == Azalea, or variable == Azalea).

Recursion is permitted in composite types. This allows us to specify more complex data types, such as trees. In this example, a list is constructed from a terminator and a recursive constructor.

data List a = Value a | Cons a (List a)
type Garden = List Bloom

The new type is just like any other type -- it can be referred to in functions, played around with in the interpreter, etc. A simple function which tallies the number of blooms might look like:

countBlooms :: Garden -> Int
countBlooms (Node bloom) = 1
countBlooms (Cons bloom list) = 1 + countBlooms list

Implementing Abstract Data Types

Like other recently-developed languages (eg. Ada, Eiffel), Haskell has a linguistic facility for implementing abstract data types. Programmers can build a fair range of data representations. Examples of ADTs include the stack (a well- worn example), the (lookup) table and the binary tree mentioned earlier.

Generally, the specification for ADTs consists of the type name and a list of the operations that can be performed on the type, including their type definitions. In Haskell, it is possible to write ADT specifications ( behaviour constraints) and implementations (a working data representation).

module Maze (Maze,     -- data type
    readMaze, -- turns a String into a Maze
    showMaze, -- turns a Maze into a String
    findPath, -- returns (equal) shortest Route from Pos to Pos in a Maze
    Pos,      -- position in a 2-dimensional grid
    Route     -- list of positions
    ) where

type Tile = Bool
type Row = [Tile]
type Maze = [Row]
type Pos = (Int, Int)
type Route = [Pos]
readMaze :: String -> Maze
showMaze :: Maze -> String
findPath :: Maze -> Pos -> Pos -> Route

Note well that there is no way to see/display the state of an ADT unless the programmer specifically writes a function to do so. In Haskell, this function must use as one of its base components the function show so that the compiler knows which function to use when the object has to be converted to a print representation.


  1. A brief history of this chapter: originally, this chapter covered the Miranda programming language -- another functional language, little-used today -- written by Sinclair and Shelswell. Then, in 2001, it was re-tooled by Brownlow to cover Haskell. Unfortunately, it didn't make it to print in TFM 2003, however, with the addition of an introduction it makes its proud debut in this edition!
  2. http://bondi.it.uts.edu.au/ (a language being developed right here at UTS)
Personal tools