Lecture Slides

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

Extra Exercises

IO

• 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 appendFile yet.

• 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 Prelude or 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 a, b and c is copied into the file d.

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 1.
  • 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 Maybe, Either and Tree a

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 ....  = ...

...

Prolog

• 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))).
• Run 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 wellTyped(ap(foldr,foldr),X) ?

Finger Trees

module  FingerTree where
import TooSimpleParseLib
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 True

• Implement |>, a variant of <| that adds a new element to the right end of the tree.

• Implement |>' and <|' 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 |><| for Empty and Single. When attempting to concatenate two Deep trees s1 and s2 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 and s2. 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
...