TFM:Prospering With Haskell
From ProgSoc Wiki
Prospering With Haskell
Iain Sinclair, Ryan Shelswell and Peter Brownlow
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.
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.
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.
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],] 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)
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
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.
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')]
(!!) :: [a] -> Int -> a Main> "string" !! 5 'g'
You will have noticed by now that the first element in a list is denoted by !! 0.
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.
- ↑ 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!
- ↑ http://bondi.it.uts.edu.au/ (a language being developed right here at UTS)