Implementing Pointer Algorithms in Haskell — Exercises

Péter Diviánszky

CEFP, Budapest & Komárno, 25-30 May 2009

Legend

E2: exercise
*E3: exercise, hard to solve
-E6: exercise, easy to solve

Programming Environment

Newer GHC and cabal-install are needed (these are on computers in the lab; Linux is recommended).

Run the following commands in a terminal:

cabal update
cabal install linear-maps -fcheck
firefox `linear-maps-exercises` &

Open an editor and save an empty file Maps.hs (do not quit).
Run the command “ghci Maps.hs” in a terminal — this is an interpreter.

First Steps

Enter 3*23 in the interpreter. The result should be 69.
Write x = 3*3 in the editor and save the file. Enter :r (reload) and enter x in the interpreter. The result should be 9.
You can navigate between previous commands with up and down arrows.
:t x shows the type of x.
Get acquainted with Haskell (look at haskell.org if necessary).

E1: Depth-First Walk

If we start from A then we get A, B, D, E, C, F, G, H.

graph

Instructions

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

Instructions (continued)

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"

Help

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 (:).

E2: Postorder Walk

If we start from A then we get D, E, B, F, H, G, C, A.

graph

Instructions

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"

Help

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.

E2’: Postorder Walk Variant

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

*E3: Mapped Walk

If we start from B, G, A then we get E, D, B; H, G; F, C, A.

graph

Instructions

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"]

E3’: Mapped Walk Variant

Define a function similar to mapWalk but

The result is reversed.
Collect the nodes which are present in the set.

revMapWalk :: I i => 
    ChildrenFun k -> Set i k -> [Id k] -> [[Id k]]

Help: Use accumulation.

*E4: Strongly Connected Components

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

graph

Instructions

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"]

-E5: `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"

-E6: `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"

*E7: Pointer Reversal Walk

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

*E7: Pointer Reversal Walk (continued)

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.

*E7: Pointer Reversal Walk (continued)

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"

*E8: Linear Time Type Inference

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

*E8 / Types

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

*E8 / Types (continued)

“[a]->a” has the graph:

type

*E8 / Type Equations

type TEq k = (Id k, Id k)

*E8 / Instruction

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

CEFP, Budapest & Komárno, 25-30 May 2009