| Design and Implementation of a validating XML parser in Haskell: Master's thesis; University of Applied Sciences Wedel | ||
|---|---|---|
| Prev | Chapter 1. Basics | Next |
This introduction to Haskell can only cover a few aspects of Haskell. Its aim is to make the next chapters more easily understandable for persons who are not familiar with Haskell, but with programming languages. If you are new to Haskell, its homepage Haskell.org [WWW11] is a good place to start for gaining information and lots of free compilers and libraries. The tutorial "A Gentle Introduction to Haskell" [WWW14] gives a detailed overview about the language. A great learning book, full of examples is "The Craft of Functional Programming" by Simon Thompson [Thompson99]. For advanced people Paul Hudak's "The Haskell School of Expression" [Hudak00] gives a more complete overview about monads and higher-order functions by samples from multimedia. The language itself is defined in the Haskell 98 Report [WWW15] and the Haskell 98 Library Report [WWW16].
Haskell is named after Haskell Brooks Curry [WWW12] who was one of the pioneers of the lambda calculus. Haskell bases on the lambda calculus, a mathematical theory of functions, and not on the Turing machine like imperative programming languages do. In functional programming the programmer defines what has to be calculated and not how it is calculated. A functional program is a single expression, which is executed by evaluating the expression.
Shortly described, Haskell is a strong typed, lazy, pure functional programming language.
Haskell has a static type system so that all type errors are detected at compile time. This makes Haskell programs very type safe. Its type class system is complex but powerful.
Haskell's evaluation model is called lazy or non-strict, because arguments of functions are only evaluated if they are needed for computations. This leads to a demand-driven evaluation. Expressions are evaluated just enough to get the result. Parts of them may not be evaluated at all. In contrast to imperative languages, program order is not needed.
The language is called pure, because it has no imperative extensions and it eschews all side effects. This leads to the fact that Haskell lacks any loop constructs, because mutable variables do not exist. All iterations have to be expressed by recursions. The lack of side effects allows easy reasoning about the programs.
The above-described qualities make Haskell a modern functional programming language with many strengths over actual object oriented languages like Java or C++.
Functions are essential for structuring a program. The following example shows a function declaration for adding two numbers.
The first line is the type signature, it declares the name and type of the function. The function add takes two integers as input and returns an integer as a result. The type system of Haskell is so powerful that the type signature can be avoided. However there exist a few exceptions and defining the type signatures makes a program much more maintainable.
The second line gives the definition of the function as an equation. The part before the equal sign names the arguments, the part after the equal sign defines the computation. Using pattern matching (see Section 1.2.4) a function can be defined by a series of these equations.
By surrounding the function name of a two-argument function in back-quotes, it can be written between its arguments, called infix.
Operators, such as ++ for concatenating two lists, are just infix functions. Instead of writing the function in front of its arguments, it is written between them. Haskell allows the programmer to define his own operators. For defining infix functions, the function name has to be enclosed in parenthesis in the type signature.
It is also possible to define the associativity and binding power of the self-defined operators. The following example defines ++ as a right-associative operator with a precedence level of 5.
In general terms, a type is a collection of similar objects, such as numbers or characters. Haskell has a very powerful and complex type system. The following sections can just give a small overview. Type classes, abstract data types or infinite lists are not discussed.
Like many other programming languages Haskell has the basic build-in types: Char, Int, Bool, Float and String, which is only a synonym for a list of Char.
Lists and tuples are often used data structures for compound data in Haskell and are therefore also build-in values.
Lists combine values of the same type into a single object. The list [1,2,3] is a shorthand for 1:(2:(3:[])). The infix operator : adds its first argument to the front of its second argument, a list. The empty list is expressed by []. The data type list is a polymorphic type, see Section 1.2.3.2 .
A tuple combines a predefined number of values of predefined, may be different, types into a single object. Tuples are called records or structures in other programming languages. A person might be represented by a personal id and a name. These two different types can be expressed by a tuple:
Lists and tuples are the most common examples of generic polymorph data types. A list can contain any type, the only constraint is that all types in one list are the same.
The Prelude, Haskell's standard library, contains lots of polymorphic functions and operators for processing lists and tuples. The head function for example is a list function that returns the head element of any list.
The function takes a list with elements of type a and returns one element of type a, the head. Haskell supports type variables, like the a above. They are uncapitalized in contrast to specific types like Char or Int and stand for any type.
Type synonyms are names for commonly used types. They are created using a type declaration. A synonym does not define a new type, it just gives a new name for an existing type. Because synonyms are simply a shorthand, which can always be expanded out, type synonyms cannot be recursive.
As mentioned in the section about basic types, a String is a type synonym for a list of characters.
Instead of writing ['H','e','l','l','o'] for a string, Haskell defines a shorthand syntax for strings: "Hello".
Algebraic types are used to define more complex types than lists or tuples, e.g. enumerated types or trees. These types can be recursive. Their definition starts with the keyword data, followed by the name of the type and the constructors.
The following example demonstrates a recursive data structure for a polymorphic binary tree, which can store any data type in its leafs. The two kinds Leaf and Branch of the data type BinTree are called constructors. They can be used in the pattern matching of function definitions, described in the next section.
Functions can get different types of input. A powerful way for describing different input types in Haskell is using pattern matching. A function can be multiple defined, each definition having a particular pattern for its input arguments. The first pattern that matches the argument is used for that function call. An underscore is a wildcard and is used where something should match, but where the matched value is not used.
Example 1-10. Calculate the length of a list
length :: [a] -> Int length [] = 0 length (_:xs) = 1 + length xs |
The function length uses recursion for calculating the length of lists. It calls itself on the right-hand of the second equation. There exist two definitions of the function: one for empty lists and one for lists with content. The pattern [] matches the empty list. The pattern x:xs matches any list with at least one element. The head element is described by the x, the tail of the list by xs. The x can be replaced by the wildcard, because the head element has not to be accessed directly.
The generic type [a] in the function declaration of length expresses that length is a polymorph function, which can be applied to a list containing elements of any type.
Constructors of algebraic types can also be used for pattern matching. The following function returns a list of all values stored in a binary tree. The infix function ++ concatenates two lists.
Example 1-11. Get all values from Bintree
fringe :: Bintree a -> [a] fringe (Leaf x) = [x] fringe (Branch t1 t2) = fringe t1 ++ fringe t2 |
To name a pattern for the use on the right-hand side of an equation, there exists the operator @. These patterns are called as-patterns. The pattern in front of the @ always results in a successful match, but the sub-pattern can fail. The following example shows a rewritten fringe function that returns not only the values of the leafs but the leafs itself.
Guards (|) allow boolean tests of arguments passed to a function. The function definition which conditional expression matches first is applied. The keyword otherwise matches always. The function max uses guards for calculating the maximum of two numbers.
In Haskell functions are first-class citizens. This means that they are themselves simply values. They can be stored in data types or passed as arguments to other functions.
Higher-order functions are functions that take functions as input, return functions as a result or do both. This technique provides a very high abstraction, by embodying a pattern of computation into a function. The following map function embodies transformations over lists.
Example 1-14. Apply a function to a list
map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs |
map is a polymorphic function that takes a function and a list as arguments. The passed function takes any type a and returns any type b. By applying map to a list of a's, it returns a new list of b's. The generic types a and b might be different, but do not have to be like the following example demonstrates.
The infix function + in the example for increasing all numbers in a list is partially applied. Partial application can be done to any function taking two or more arguments. The operator + expects two arguments, one argument is predefined as "1". In this case the function increases every second argument by one.
Modules are the basis for structuring programs or building general libraries. A module has a name and contains a collection of Haskell definitions. A module may import definitions from other modules and export definitions for the use by other modules.
The module Foo exports the functions inc and dec. It imports the module Bar so that Foo can use Bar's exported definitions. Haskell's standard library, the Prelude, is implicitly imported.