This document contains information regarding the required software for this course, a short introduction to Haskell with code examples and requirements for the submission of worksheets.
The Glasgow Haskell Compiler (GHC) is required to execute Haskell code. The minimal installer is sufficient. If you do not want to install Haskell via a package manager, you can download the binaries directly at https://www.haskell.org/ghc (Download -> Current Stable Release).
If you decide to use the binaries, don't forget to add the path to the directory containing the programs ghc and ghci to the PATH environment variable.
In addition to GHC the program Shrimp (spc) is required to solve certain tasks. Shrimp allows you to write programs as flow-charts and then translates them into Haskell. To learn how to use Shrimp please follow the tutorial in the documentation.
When a Shrimp program (also called sp-program) is executed, an execution trace can be generated and writen as csv-file. It is recommended to use a spreadsheet program such as LibreOffic Calc to view these csv-files.
The file AB/Examples.hs contains examples which you can test and modify. To do so, open the file with the interpreter ghci. You can input expressions such as 2*(3+4) or couple "abc" "123" into the interpreter and press enter to let the interpreter evaluate them. With the command :r you can reload the currently loaded hs-files. This is useful when you have modified an hs-file and don't want to restart the interpreter. With the command :q you can quit the interpreter. With the command :t you can ask for the type of a function. For example, try :t couple. Using an exclamation mark after the colon allows you to execute shell commands, e.g. :!clear (resp. :!cls for Windows) clears the terminal.
Functions are defined using expressions. The control flow, which is described using control structures (if, for, while, etc.) in imperative languages, has to be expressed via recursion in Haskell.
Expressions are written in prefix notation. A call f(x, g(y, z), myVar) would be written as (f x (g y z) myVar) in Haskell. Binary operators are functions with two input parameters whose name does not consist of alphanumeric characters, e.g. +, -, *, &&, ||, ==. These are used in infix notation: (((3 * (2 + x)) > y) && (fun z)). The leading and trailing parenthesis can be omitted, e.g. f x (g y z) myVar would work as well.
Function and variable names have to start with a lower case letter. They may contain an apostrophe ' provided it is not the first character. The following code defines a function f2 which has three input parameters x, y, y' and returns y if x is odd and y' otherwise.
f2 x y y' = (if' ((mod x 2) == 1) y y')
if' has three input parameters and returns the second if the first is true, else the third.
A constant can be seen as a function without input parameters. Examples for different types of literals (a literal is a constant whose name defines its value):
pi = 3.14 baseNo = 2 str = "a string" -- type String chr = 'x' -- type Char flag_q2 = False -- type Bool list = [2,3,5,7] -- list of numbers {- the following constant contains a 3x3 matrix with entries from 1 to 9 -} matrix = [ [1,2,3], [4,5,6], [7,8,9] ]
matrix.
Every line of the expression after the first must be indented with more whitespaces than the first character of the function name (in this case m). Tabs should not be used. The first example could be written as follows:
f2 x y y' = (if' ((mod x 2) == 1) y y' )
The type of a unary function whose input parameter has the type Int and whose return value has the type Bool
is Int -> Bool.
Assume that in the case of f2 the variable x has type Int and the variables y, y' have type String. Then the signature of this function would look as follows:
f2 :: Int -> String -> String -> String
-> and the last type is that of the return value. The operator -> is right-associative and the above type expression is therefore interpreted as Int -> (String -> (String -> String)). This means f2 can be seen as unary function whose single input parameter has type Int and whose return value has the type (String -> (String -> String)); this means the return value is a function itself. The interpretation of a non-unary function as a sequence of unary functions is called Currying.
The expression (f2 1) returns a function which is the same as the function f2 except that the first input parameter is now assumed to be 1. This is called partial application. If you do not provide a signature for a function the compiler/interpreter tries to infer the most general signature for the function.
The where-clause allows one to define subexpressions separately. This can be used to structure big expressions and write them more compactly if certain subexpressions occur multiple times.
f3 x = z where y = x + x z = y * y
y and z are only valid within the definition of f3.
If y is already defined on a global level then the definition from the where-clause is preferred (shadowing). It is possible to nest where-clauses.
The keyword type can be used to introduce type aliases, e.g. type Age = Int.
An alias is treated identically to the type expression on the right side which defines it. Thus, each occurrence of Age can be replaced with Int or vice versa without affecting the semantics of the program.
A data type in Haskell consists of a name and at least one constructor. A constructor describes how a data type is represented. A constructor consists of a name and a sequence of type expressions. For example, a color can be represented using RGB or HSV.
In both cases three values are required which can be expressed as Float
data Color = RGB Float Float Float | HSV Hue Saturation Value type Hue = Float -- [0°,359°] = [0.0,1.0] type Saturation = Float -- [0%,100%] = [0.0,1.0] type Value = Float -- [0%,100%] = [0.0,1.0] black = RGB 0.0 0.0 0.0 black' = HSV 0.5 0.6 0.0 red = RGB 1.0 0.0 0.0 red' = HSV 0.0 1.0 1.0
Identifiers of data types and constructors (their names) always start with a capital letter. This makes it possible to distinguish variables and functions from data types and constructors. A constructor may have the same name as its data type (this is common if the data type only has a single constructor). Type aliases can be used to document what kind of value one expects at a specific position of a constructor, as seen in the case of HSV above. A constructor can be called like a function to define a value.
Pattern matching can be used to access the values of a constructor.
A pattern is an expression on the right-hand side of = and which may only consist of constructors and variables.
A pattern describes a set of values which have a certain structure (e.g. lists with at least two elements) and also binds parts of this structure to variables (e.g "let y be the second element of the list").
redVal (RGB x _ _) = x --redVal red == 1.0 swapRedBlue (RGB r g b) = (RGB b g r)
redVal returns the red value of a value of type Color which has been defined with the constructor RGB. The underscores mean that the values at these positions are not required. The expression redVal red' would cause an error Non-exhaustive patterns because the function is not defined for the constructorHSV. One could add another line redVal (HSV h s v) = ... which computes the red value from the HSV representation to solve this.
A constructor can also have no type expressions. For example, the data type Bool is defined as data Bool = True | False. A data type which only consists of constructors without type expressions can be seen as an enumeration. In such a case pattern matching can be used to distinguish whether a variable of type Bool is true or false.
if' True x y = x if' False x y = y
Lists have two special constructors [] and :. On the right-hand side of = the expression (2:[3,4,5]) means the same as prepend 2 [3,4,5], which means [2,3,4,5]. On the left-hand side they are interpreted as patterns and have the following meaning:
(x:xRest) — if the list consists of at least one element, let x be the first element and let xRest be the list without the first element[] — if the list is empty(x:[]) — if the list consists of exactly one element, let x be that element[x] — equivalent to (x:[])listTest [x,y] = "list with exactly two elements" listTest (x:(y:z)) = "list with at least two elements" listTest z = "all other cases"
listTest is called, the patterns are checked one by one and the first definition whose pattern matches the structure of the value of the input parameters is chosen. In this example this means the following. First, it is checked whether the list has exactly two elements. If this is not the case, then it is checked whether it has at least two elements. In all other cases the third definition is chosen. If one would swap the first and third line then the function would always return "all other cases"
A type class describes a set of types for which particular functions are available. For example, two values of type Int oder Float can always be compared with the function <. This is possible because both types are members of the type class Ord (ordered). Members of this type class must define the functions <, <=, >, >=. Type classes are similar to what is called interfaces in other programming languages.
Members of the type class Eq (equal) have to define the functions == and /=. Except for function types (types of the form* -> *), all types in this course are members of Eq and thus can be checked for equality.
Members of the type class Show can be converted into a string with the function show.
Members of the type class Read can be converted back from a string into a value of that type with the function read. The type of the return value must be declared explicitly, e.g. ( (read "[1,2,3]") :: [Int] ).
For self-defined data types it is possible to let the compiler/interpreter automatically derive the functions required for a certain type class using the keyword deriving. This turns the self-defined data type into a member of that type class.
data Color = RGB Float Float Float | HSV Hue Saturation Value deriving (Eq,Show,Read)
Color into a string using show and with read it can be converted back. Since Color is also a member of Eq its values can also be checked for equality. Two values are considered equal iff they were created using the same constructor and each component is equal. For example, red == red' would be False. The automatic derivation only works if all type expressions in every constructor are also members of the type class for which the functions should be derived.
Signatures of polymorphic functions can be expressed using type constraints. The signature of a function which sorts list which contains elements of arbitrary type would look as follows:
mySort :: (Ord a) => [a] -> [a]
[a] stands for a list with elements of type a where a can be an arbitrary type. Since a list can only be sorted if there exists an order relation on its elements, it must hold that a is a member of the type class Ord. This is expressed with the type constraint (Ord a) =>.
Further information regarding type classes can be found on Haskell/Classes and Types on Wikibooks.
The function trace can be used to print a string for debugging purposes. The first input parameter is a string which is printed, the second input parameter is the return value. A value of an arbitrary type can be converted into a string with the function show, provided it is a member of the type class Show.
The file Test.hs contains examples (starting after the comment --Tracing examples) on how to use this function for tracing. The order in which the trace calls are printed depends on the order of evaluation. Due to the lazy evaluation strategy of Haskell this order might not be quite obvious. For example, when evaluating reverse2 "abc" the strings starting with new res: are printed at the very end.
To test your code for the worksheets you may use the file AB/Testing.hs and add import statements to import modules as required, so you don't have to change the headers in the code templates for the solutions.
A module corresponds to an hs-file. The module name can consist of multiple parts separated by ., e.g. MyProject.ModuleSet1.ModuleName. By default GHC would assume the corresponding file to be MyProject/ModuleSet1/ModuleName.hs; this path is relative to the main hs-file which is being compiled/interpreted.
A module exports functions, types, constructors and type classes. If nothing is specified, all defined entities are exported. Alternatively, one can provide an explicit export list which states which entities should be exported. All entities not included in this list are not exported and thus cannot be accessed from outside the module (private). The module-line should always be placed at the beginning. The second line in the example below would only export the type MyType with the constructors ConsA and ConsB and the functions fun1 and fun2.
module MyModules.XyZ where module MyModules.XyZ (MyType(ConsA,ConsB), fun1, fun2) where
To import modules the keyword import is used.
If no import list is specified then all entities which are exported by the module are imported. The second line in the example below would only import the data type MyType without constructors and the function fun2.
import MyModules.XyZ import MyModules.XyZ (MyType,fun2)
MyModules.XyZ.fun2. This can be abbreviated by giving an alias to a module, e.g. import MyModules.XyZ as Xy. Then the function can be referenced as Xy.fun2. Further options for importing modules are listed in the Haskell-Wiki.
When submitting your solution for a worksheet ABi send all corresponding ABi_j.hs files and folders ABi_j as zip-archive via e-mail with the subject "Submission ABi" to sysprog@thi.uni-hannover.de. The zip-file should only contain hs- and sp-files! If there is no folder ABi_j for a file ABi_j.hs this means the use of sp-programs is prohibited.
Before the files ABi_j.hs are tested they are compiled with spc (if they don't contain sp-programs then nothing changes). Then the submission is run against a set of test cases. If the submission has passed all tests then you are notified and an oral examination with all group members via video chat follows. Each group member has to be able to answer questions regarding any part of the code.
If an error in the submission is spotted during the oral examination then the submission is counted as a failed attempt. If the execution of your submission for the test cases does not finish within a generous time limit then this is also regarded as a failed attempt.