E2: exercise
*E3: exercise, hard to solve
-E6: exercise, easy to solve
Newer GHC
and cabal-install
are needed (these are on computers in the lab; Linux is recommended).
cabal update
cabal install linear-maps -fcheck
firefox `linear-maps-exercises` &
Maps.hs
(do not quit).ghci Maps.hs
” in a terminal — this is an interpreter.3*23
in the interpreter. The result should be 69
.x = 3*3
in the editor and save the file. Enter :r
(reload) and enter x
in the interpreter. The result should be 9
.:t x
shows the type of x
.
Get acquainted with Haskell (look at haskell.org if necessary).
If we start from A then we get A, B, D, E, C, F, G, H.
Define a function with the following type signature:
import Data.IdMap -- at the beginning of the file
import Data.Graph.IdMap.Tests
type ChildrenFun k = Id k -> [Id k]
depthFirstWalk ::
I i => -- type level integer
ChildrenFun k -> -- children function
Set i k -> -- set of already visited nodes
[Id k] -> -- nodes to be visited
[Id k] -- visited nodes
Use the following primitives:
member :: I i => Id k -> Set i k -> Bool
setInsert :: I i => Id k -> Set i k -> Set i k
Test your function in the interpreter:
*Main> testWalk depthFirstWalk "A"
"ABDECFGH"
Make pattern matching on the identifier list. If it is not empty, test whether the first identifier is in the set. If it is not in the set, return it and make a recursive call with a modified set and an extended task list (the children of the first identifier has to be visited).
You will probably need the functions (++)
and (:)
.
If we start from A then we get D, E, B, F, H, G, C, A.
Define a postorder walk:
postOrderWalk :: I i => ChildrenFun k -> Set i k -> [Id k] -> [Id k]
Use the following data structure inside in a “task list”:
data Task a = Return a | Visit a
Use the same primitives as in depthFirstWalk
. Test your function in the interpreter:
*Main> testWalk postOrderWalk "A"
"DEBFHGCA"
Define a local function which receives a set of already visited nodes and a list of tasks and returns the reachable nodes. Call the local function with the set and with Visit
tasks.
The local function is a recursive function.
Make pattern matching on the identifier list. If it is not empty, and the first identifier is a Return
task then return it and make a recursive call.
If the first identifier is a Visit
task then test whether it is in the set.
If it is not in the set, make a recursive call with a modified set and an extended task list.
The extended task list should contain the children of the first identifier (as Visit
tasks) and the first identifier as Return
task, and the old tasks.
Define the function:
revPostOrderWalk ::
I i =>
Children k ->
Set i k ->
[Id k] ->
( Set i k -- set of visited nodes
, [Id k]) -- visited nodes in reversed postorder
Help: Use accumulation (define a local function with an additional list parameter which accumulates the values).
If we start from B, G, A then we get E, D, B; H, G; F, C, A.
Define the function:
mapWalk :: I i => ChildrenFun k -> Set i k -> [Id k] -> [[Id k]]
mapWalk
takes a list of nodes. It returns a list of lists with the same length. The first list contains the nodes reachable from the first node. The second contains the nodes reachable from the second node not touching nodes in the first list. …
*Main> testMapWalk mapWalk "BGA"
["EDB","HG","FCA"]
Define a function similar to mapWalk
but
revMapWalk :: I i =>
ChildrenFun k -> Set i k -> [Id k] -> [[Id k]]
Help: Use accumulation.
If we start from A then we get D; E; B; I, H, G; C, F, A.
(If these are modules then this is the compilation order.)
Define the function:
scc :: I i =>
ChildrenFun k -> -- children
ChildrenFun k -> -- parents
Set i k -> -- an empty set
[Id k] -> -- initial nodes
( Set i k -- an empty set
, [[Id k]]) -- the scc of the reachable nodes
Test case:
*Main> testSCC scc "A"
["D","E","B","HG","CFA"]
replaceLast
Define a function which replaces the last element of a list.
replaceLast :: [a] -> a -> [a]
Test cases:
replaceLast [1,4,6] 7 == [1,4,7]
replaceLast "take" 'x' == "takx"
replaceAndShiftOne
Define a function which replaces a list’s nth element and shift the old element one position to the right.
replaceAndShiftOne :: Int -> [a] -> a -> [a]
Test cases:
replaceAndShiftOne 0 "abcd" 'e' == "eacd"
replaceAndShiftOne 1 "abcd" 'e' == "aebd"
replaceAndShiftOne 2 "abcd" 'e' == "abec"
Define the pointer reversal algorithm.
prWalk ::
(I i, I i') =>
Map i k [Id k] -> -- a graph
Map i' k Int -> -- an empty map
Id k -> -- start node
[Id k] -- reachable nodes in depth first order
next slide
Use the helper functions:
follow, back ::
(I i, I i') =>
Map i k [Id k] -> -- modified graph
Map i' k Int -> -- index map
Id k -> -- previous node
Id k -> -- this node
[Id k] -- reachable nodes in depth first order
follow
follows an edge, back
goes back on an edge.
The index map contains already visited nodes. The index show how many children of the node was completely visited.
The graph is transformed in each step a little but at the end it will have its original shape.
Use the following library functions:
lookUp :: I i => Id k -> Map i k a -> Maybe a
insert :: I i => Id k -> a -> Map i k a -> Map i k a
(!) :: I i => Map i k a -> Id k -> a
Test Cases:
*Main> testPrWalk prWalk "A"
"ABDECFGH"
Begin a new file with the rows:
import Data.LinkMap
type Link i k = LinkMap i k ()
Link
is a disjoint set data structure.
We will use the following primitives:
link :: I i => Id k -> Id k -> Link i k -> Link i k
-- make a link from the first id to the second id
follow :: I i => Link i k -> Id k -> Id k
-- follow the links until no link is found
same :: I i => Link i k -> Id k -> Id k -> Bool
-- True if follow id1 == follow id2
data TypeNode k
= Var -- type variable
| Con String -- type constructor
| App (Id k) (Id k) -- application
type Types k = Id k -> TypeNode k
-- many types in one graph
For example, “[a]->a
” is first transformed to “((->) ([] a)) a
”.
“[a]->a
” has the graph:
type TEq k = (Id k, Id k)
Define a function
solveEqs ::
I i =>
Link i k -> -- fully separated map
Types k -> -- typing environment
[TEq k] -> -- type equations
( [TEq k] -- failed equations
, Link i k) -- unifications
The definition is just 13 rows..