Lectures and schedule
| nummer || datum || slides || dictaat || extra te lezen || werkcollege |
| 1 || 10 sept || 1-Introduction || Hfd. 1 & 2 || bekijk website vak || begin oefenpraktikum |
| 2 || 12 sept || 2-NotatieRecursieLijsten || Hfd. 3 || || 2.5, 2.7, 2.12, 2.14, 2.15, 3.1, 3.4, 3.6, 3.7, 3.8, 3.14 |
| 3 || 17 sept || 3-IO || Hfd. 4 || || 4.1, 4.3, 4.5, 4.4, more |
| 4 || 19 sept || 4-Foldl-Lambda-Lijsten || Hfd. 5 || || 5.1-5.17, 5.22 |
| 5 || 24 sept || 5-Fib-Ham-ListComp-ListAlg || Hfd. 9.1 || 9.3 || 9.1 - 9.8 |
| 6 || 26 sept || 6-ListAlg-Arrays-Calendar || Hfd. 6 || || 2.11, 6.1-6.5 |
| - || 1 okt || 20121001-Tussentoets: || Hfd. 1-5, 6, 9 || Oude Tentamens || 9.6-9.8, 9.12, 9.13 |
| 7 || 3 okt || 7-Data-Structures || Hfd. 7 || 10 || 7.8-7.15 |
| 8 || 8 okt || 8-Classes-Instances || Hfd. 8 || || 10.1-10.5, |
| 9 || 10 okt || 9-LazyEvaluation || || 11 || 8.1-8.8, more |
| 10 || 15 okt || 10-DSL || Hfd. 14 || || 11.1-11.4, 14.1-14.3, 11.5 ?? |
| 11 || 17 okt || 11-Gui || Hfd. 16 || Layout || 14.5-14.14, 14.20 |
| 12 || 22 okt || 12-RekenenMetProgrammas || Hfd. 12 || || 14.4-14.15, 14.20 |
| 13 || 24 okt || 13-Prolog.pdf || Hfd. 15 || Wiskunde D || 12.3-12.9 |
| 14 || 29 okt || 14-FingerTrees || Hfd. 13 || || PrologEx |
| 15 || 31 okt || vragenuur || || || Parsing, FingerTrees |
| - || 6 nov || Eindtoets || || || |
- Write a function of type
[String] -> String -> IO () that concatenates a list of files to a specific target file: the first parameter is a list of filenames and the second parameter the name of the target file. Next write a program that first asks for the name of the target file, and then continues asking for names of files to be appended to that file until an empty line is entered. Note that the target files may be one of the source files! Do not use the function
- If we know that none of the source files equals the target file we may do a bit better using the function
appendFile from the
System.IO. Look up its definition using hoogle, and change the function you have written above using this function. What are the advantages and disadvantages of this approach?
- With the function
getArgs from the module
System.Environment we can ask for the parameters which were entered form the command line when the program was called. Write a program
CopyFiles, such that when called as
./CopyFiles a b c d the contents of the files
c is copied into the file
About Data Structures
- All the examples we have seen of data type are so-called regular data types: the recursive positions take the same parameters as the data type: the definition of
Tree a contains
Tree a 's again, etc. This is however not required by Haskell. We may also have nested data types. Describe in your won words what kind of values inhabit the following type:
data WhatAmI a = Zero a | Succ (WhatAmI (a,a))
- An AVL tree is a binary search tree in which for every
Node the height of the left and the right subtree differs at most
- Write a function which checks whether a binary tree has this property (use tupling to make the algorithm linear in the size of the tree)
- Verify that the following nested data type enforces the AVL property through the Haskell type system by defining a couple of example trees and putting these definitions through the Haskell type checker:
data Balanced a t_np1 t_n = L t_np1 a t_n | Bal t_np1 a t_np1 | R t_n a t_np1
data AVL a t_np1 t_n = Zero t_n
| Succ (AVL a (Balanced a t_np1 t_n) t_np1)
type AVLTree a = AVL a a ()
emptyTree = Zero ()
singletonTree v = Succ (Zero v)
- In the exam we have seen how to encode Boolean values and cartesian products using just functions. Combine these techniques to encode the constructors and case statements corresponding to the data type
true = \ x y -> x
false = \ x y -> y
caseBool bool truebranch falsebranch = bool truebranch falsebranch
pair x y = \f -> f x y
casePair p alwaysbranch = p alwaysbranch
just a = \ just nothing -> ...
nothing = ...
caseMaybe .... = ...
- In the version of the Prolog interpreter NanoProlog the interpreter builds first an intermediate data structure of type:
data Result = Done Env
| ApplyRules [(Tag, Rule, Result)]
The leaves of this tree represent solutions to the query posed. This makes it easy to implement different search strategies.
- The standard prolog semantics is a depth-first strategy, and thus the order of the rules is extremely important. Define a function
enumerateBreathFirst, for which this order does not matter.
- Change the parser of the code on the lecture slides such that also the Haskell list notation can be used in writing terms, i.e we can write
1:2:3: instead of
Cons(1,Cons(2, Cons(3, Nil))).
cabal install NanoProlog in order to obtain the executable
nano-prolog in your $CABAL/bin directory.
- Use the NanoProlog interpreter to see how it infers types for the examples in chapter 6, and the types in chapter 6.1-6.4. You have to show that when you apply (the type of) a function to an argument (type) that the parameter (type) of the function can be unified with the argument (type).
- How would you model the type checking of a case expression in this style (hint: use a list to represent the case branches). Assume that the patterns and the expressions do not contain variables. Patterns are thus just constant values.
- If you want to deal with variables in expressions you have to extend the relation =wellTyped+ such that it carries a third parameter, an environment, but this approach breaks down : we have modelled polymorphism using Prolog variables. But this simplistic approach implies we cannot easily store a polymoprhic type in an environment. This would cause all uses of this variable to have the same type! The case statement in my approach thus just boils down to a kind of nested if-then-else.
- Our Prolog interpreter is very simplistic, in the sense that it does not perform the so-called occurs check, i.e. we do not test whether a variable can be unified with a term which reaches that variable again. What is the consequence when trying to solve for a goal of the form
module FingerTree where
import Control.Applicative -- includes Alternative
data FingerTree a = Empty
| Single a
| Deep [a] (FingerTree (Node a)) [a] deriving Eq
data Node a = Node2 a a
| Node3 a a a deriving Eq
instance Show a => Show (FingerTree a) where
show Empty = "Empty"
show (Single a) = "Single" ++ show a
show (Deep lf t rf) = "Deep" ++ show lf ++ show t ++ show rf
instance Show a => Show (Node a) where
show (Node2 a b ) = "Node2(" ++ show a ++ "," ++ show b ++")"
show (Node3 a b c) = "Node3(" ++ show a ++ "," ++ show b ++ "," ++ show c ++")"
(<|) :: a -> FingerTree a -> FingerTree a
a <| Empty = Single a
a <| Single b = Deep [a] Empty [b]
a <| Deep [b,c,d,e] m sf = Deep [a,b] (Node3 c d e <| m) sf
a <| Deep pr m sf = Deep ([a] ++ pr) m sf
t :: FingerTree Int
t = foldr (<|) Empty [1..18]
class Parseable a where
parse :: Parser Char a
instance Parseable Int where
parse = ...
-- define the needed instances such that the following value evaluates to True
true = t == snd (head $ runParser parse $ show t)
- Define the correct instances of
Parseable such that the variable
true evaluates to
|>, a variant of
<| that adds a new element to the right end of the tree.
<|' which add not a single but a list of elements to the tree.
- A finger tree represents a sequence of values. So it is no surprise we want to have a concatenation operator:
(|><|) :: FingerTree a -> FingerTree a -> FingerTree a
Of course we do not want to fully deconstruct the operands but leave as much of them intact as possible. First, implement
. When attempting to concatenate two Deep
you should create a finger tree t
such that t
has as its left subtree the left subtree of s1
, and t
has as its right subtree the right subtree of s2
. In the middle you need to combine the
remainding data from s1
. To this end it might be helpful to express =|><| in terms of another function app3
, which also processes this "remaining data"
as its second argument.
s1 |><| s2 = app3 s1  s2
app3 :: FingerTree a -> [a] -> FingerTree a -> FingerTree a