linear-maps 0.5 → 0.6

raw patch · 27 files changed

+2495/−27 lines, 27 filesnew-component:exe:linear-maps-exercisesnew-component:exe:linear-maps-introductionnew-uploaderbinary-addedPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Graph/IdMap.hs +131/−0
• Data/Graph/IdMap/Tests.hs +84/−0
• Data/IdMap/Core/Fast.hs +5/−1
• Data/IdMap/Core/Pure.hs +2/−2
• Data/IdSequence.hs +83/−0
• Data/LinkMap.hs +107/−0
• Data/LinkMap/Tests.hs +73/−0
• Data/List/IdMap.hs +28/−0
• Data/Sequence/IdMap/Profile.hs +21/−0
• Data/Sequence/Profile.hs +25/−0
• Exercises.html +1294/−0
• Exercises.pandoc +361/−0
• Intro.html +17/−11
• Intro.pandoc +7/−2
• LinearMapsExercises.hs +6/−0
• LinearMapsIntroduction.hs +6/−0
• Makefile +11/−0
• Solutions.hs +92/−0
• Test/IdMap.hs +18/−0
• TypeInf.hs +44/−0
• graph.dot +18/−0
• graph.png binary
• graphmod.dot +18/−0
• linear-maps.cabal +27/−11
• runtests +3/−0
• type.dot +14/−0
• type.png binary

@@ -0,0 +1,131 @@+module Data.Graph.IdMap where++import Data.IdMap++import qualified Data.List as List++------------------------------------++type Children a = a -> [a]++x .: ~(st, l) = (st, x: l)++depthFirstWalk' :: I m => Children (Id a) -> Set m a -> [Id a] -> (Set m a, [Id a])+depthFirstWalk' children s [] = (s, [])+depthFirstWalk' children s (h: t)+    | h `member` s = depthFirstWalk' children s t+    | otherwise = h .: depthFirstWalk' children (setInsert h s) (children h ++ t)+++depthFirstWalk :: I m => Children (Id a) -> Set m a -> [Id a] -> [Id a]+depthFirstWalk children _s [] = []+depthFirstWalk children s (h: t)+    | h `member` s = depthFirstWalk children s t+    | otherwise = h : depthFirstWalk children (setInsert h s) (children h ++ t)++{-+postOrderWalk :: I m => Children (Id a) -> Set m a -> [Id a] -> [Id a]+postOrderWalk children _s [] = []+postOrderWalk children s (h: t)+        | h `member` s = postOrderWalk children s t+        | otherwise = postOrderWalk children (setInsert h s) (children h) ++ [h] : t+-}++data Task a = Return a | Visit a++postOrderWalk :: I m => Children (Id a) -> Set m a -> [Id a] -> [Id a]+postOrderWalk children s l = collect s $ map Visit l where++    collect _s [] = []+    collect s (Return h: t) = h: collect s t+    collect s (Visit h: t)+        | h `member` s = collect s t+        | otherwise = collect (setInsert h s) $ map Visit (children h) ++ Return h: t+++scc :: I m => Set m a -> Set m a -> Children (Id a) -> Children (Id a) -> [Id a] -> [[Id a]]+scc k k' children revChildren l +    = reverse $ filter (not . null) $ mapWalk k revChildren l' where++        l' = reverse (postOrderWalk children k' l)++mapWalk :: I m => Set m a -> Children (Id a) -> [Id a] -> [[Id a]]+mapWalk k children l = f k l+ where+    f _s [] = []+    f s (h:t) = c : f s' t+        where (s', c) = collect s [] [h]++    -- collect :: Set a -> [a] -> [a] -> (Set a, [a])+    collect s acc [] = (s, acc)+    collect s acc (h:t)+        | h `member` s = collect s acc t+        | otherwise = collect (setInsert h s) (h: acc) (children h ++ t)++-----------------------------------------------------------+{-+-- megkeressük azokat a csúcsokat, amelyekre többen is hivatkoznak+findShared +    ::  k+    => Bool     -- számoljuk-e még egyszer a gyökereket+    -> Bool     -- nézzük-e a gyerektelen csúcsokat+    -> Children (Id a)+    -> [Id a]       -- roots+    -> [Id a]++findShared countRoots countLeafs ch roots = filter double nodes where++    nodes = walk k1 ch roots++    inv = inverse ch nodes++    double x +        | countLeafs    = numOfParents x > 1+        | otherwise = length (ch x) > 0 && numOfParents x > 1++    numOfParents x+        | countRoots && isRoot x = 1 + length (inv x)+        | otherwise = length (inv x)++    isRoot = flipElem roots+-}++{-++data Task' a = Down a | Up a++downUp i = [Down i, Up i]++-- keresünk olyan csúcsokat, amelyeknek a kivétele megszünteti a ciklusokat+breakCycles :: Empty k -> Children (Id a) -> [Id a] -> [Id a]+breakCycles k children roots = collect (emptySet k) (emptySet k) $ concatMap downUp roots where++    -- collect :: Set a -> [a] -> [a]+    collect parents visited [] = []+    collect parents visited (Up h:t)+        = collect (delete h parents) visited t+    collect parents visited (Down h:t)+        | member h parents = h : collect parents visited t+        | member h visited = collect parents visited t+        | otherwise = collect (setInsert h parents) (setInsert h visited) $ concatMap downUp (children h) ++ t+++cyclic, acyclic :: Empty k -> Children (Id a) -> [Id a] -> Bool++acyclic k ch r = List.null $ breakCycles k ch r++cyclic k ch r = not $ acyclic k ch r++---------++mapg :: Empty k1 -> Empty k2 -> Children (Id a) -> ((Id a->b) -> Id a -> b) -> [Id a] -> [b]+mapg k1 k2 ch h nodes = map f nodes where+    f = memo k1 (h f) (walk k2 ch nodes)+{-+mapg' :: Empty k -> Children (Id a) -> ((a->b) -> a -> PreIds p -> b) -> [a] -> PreIds p -> [b]+mapg' ch h nodes ids = map f nodes where+    f = memo' (h f) (walk ch nodes) ids+-}+-}++

@@ -0,0 +1,84 @@+module Data.Graph.IdMap.Tests where++import Data.List.IdMap+import Data.IdMap+import Data.Graph.IdMap+import Test.HUnit++import Data.IORef+import System.IO.Unsafe++toFunction :: I i => Map i k [a] -> Id k -> [a]+toFunction m x = flattenJust $ lookUp x m++flattenJust Nothing = []+flattenJust (Just l) = l++relationToFunction :: Eq a => [(a, b)] -> a -> [b]+relationToFunction l x = [ns | (n, ns) <- l, n == x]++testWalk :: (forall k i. I i => Children (Id k) -> Set i k -> [Id k] -> [Id k]) -> [Char] -> [Char]+testWalk walk ns = withGraph (\toChar fromChar ch _ s _ _ -> map toChar $ walk (toFunction ch) s $ map fromChar ns)++testPrWalk :: (forall k i i'. (I i, I i') => Map i k [Id k] -> Map i' k Int -> Id k -> [Id k]) -> Char -> [Char]+testPrWalk walk n = withGraph (\toChar fromChar ch _ s _ m -> map toChar $ walk ch m $ fromChar n)++testMapWalk :: (forall k i. I i => Children (Id k) -> Set i k -> [Id k] -> [[Id k]]) -> [Char] -> [[Char]]+testMapWalk walk ns = withGraph (\toChar fromChar ch _ s _ _ -> map (map toChar) $ walk (toFunction ch) s $ map fromChar ns)++testSCC :: (forall k i. I i => Children (Id k) -> Children (Id k) -> Set i k -> [Id k] -> [[Id k]]) -> [Char] -> [[Char]]+testSCC scc ns = withGraph (\toChar fromChar ch revCh s _ _ -> map (map toChar) $ scc (toFunction ch) (toFunction revCh) s $ map fromChar ns)++withGraph :: forall a . (forall k i i' i'' i''' i4. (I i, I i', I i'', I i''', I i4) => (Id k -> Char) -> (Char -> Id k) -> Map i'' k [Id k] -> Map i''' k [Id k] -> Set i k -> Set i' k -> (forall x . Map i4 k x) -> a) -> a+withGraph fun = runICCS iccs  where++    iccs :: ICCS I3 k a+    iccs (m1 `PlusMap` m2 `PlusMap` m3 `PlusMap` _) (s1 `PlusSet` s2 `PlusSet` _) ids = fun toChar fromChar chm revchm s1 s2 m3      where++        ids' = take 11 ids++        (a:b:c:d:e:f:g:h:i:j:k:_) = ids++        chm = fromList' m1 $ reverse l+        revchm = fromList' m2 $ map swap $ reverse l++        fromChar = head . relationToFunction (zip ['A'..] ids')+        toChar = head . relationToFunction (zip ids' ['A'..])++        l = [ (a, b)+            , (a, c)+            , (b, d)+            , (b, e)+            , (c, f)+            , (c, g)+            , (f, a)+            , (g, h)+            , (h, g)+            , (i, h)+            , (j, k)+            ]++        swap (a, b) = (b, a)++++tests :: IO Counts+tests = runTestTT $ TestList ++    [ "depthFirstWalk" ~: testWalk depthFirstWalk "A" ~=? "ABDECFGH"+    , "postOrderWalk" ~: testWalk postOrderWalk "A" ~=? "DEBFHGCA"+    ]+{-+ let l = [1 :: Int ..10] +      in "dlist insert pop" ~: l ~=? (toList $ fromList l)++    , let (a,b) = ([1 :: Int ..11], [40..50])       -- ide nem szabad 10-et írni...+      in "dlist join" ~: (a++b) ~=? (toList $ fromList a >< fromList b)++    , let l = [[x..x+5] | x<-map (10*) [1 :: Int ..10]]+      in "dlist joins" ~: concat l ~=? (toList $ foldl' (><) empty (map fromList l))+    ]+-}+++

@@ -78,7 +78,11 @@ -- For example, @('left' x == 'right' x)@ should be @False@ in theory, but during runtime @('left' x)@ and @('right' x)@ are exactly the same identifiers.  equalBy :: Maplike i k a -> Id k -> Id k -> Bool-equalBy !_ (Id a) (Id b) = a == b+equalBy !_ a b = a == b++instance Eq (Id a) where++    Id a == Id b = a == b  -- | Family of finite maps from keys @('Id' k)@ to values @a@. -- For efficiency reasons, use only with concrete type integers:

@@ -49,7 +49,7 @@ -- * @(a :|: b)@, where @a@ and @b@ are identifier indexes.  newtype Id k -    = Id IdCore+    = Id IdCore     deriving (Eq)  data IdCore      = I Integer@@ -68,7 +68,7 @@ -- The first parameter has a role only in the other implementations.  equalBy :: Map i k a -> Id k -> Id k -> Bool-equalBy _ (Id x1) (Id x2) = x1 == x2+equalBy _ a b = a == b   -- | Finite maps from keys @('Id' k)@ to values @a@.

@@ -0,0 +1,83 @@+module Data.IdSequence+    ( Seq+    , previous+    , next+    , value+    , member+    , update+    , delete+    , insertBefore+    , fromList+    ) where++import Data.IdMap hiding (insert, delete, member)+import qualified Data.IdMap as M++import Prelude hiding (last)+++------------------------------------------++data Seq k a = Seq+            {-# UNPACK #-} !(Map I0 k (Id k))+            {-# UNPACK #-} !(Map I1 k (Id k))+            {-# UNPACK #-} !(Map I2 k a)++previous :: Seq k a -> Id k -> Maybe (Id k)+previous (Seq p _n _v) i = lookUp i p++next :: Seq k a -> Id k -> Maybe (Id k)+next (Seq _p n _v) i = lookUp i n++value :: Seq k a -> Id k -> Maybe a+value (Seq _p _n v) i = lookUp i v++member :: Id k -> Seq k a -> Bool+member i (Seq _p _n v) = M.member i v++delete :: Id k -> Seq k a -> Seq k a+delete i s@(Seq p n v) +    | member i s = case (previous s i, next s i) of+        (Just j, Just k) -> Seq (M.insert k j p) (M.insert j k n) (M.delete i v)+        (Just j, _)      -> Seq p                (M.delete j n)   (M.delete i v)+        (_,      Just k) -> Seq (M.delete k p)   n                (M.delete i v)+        _                -> Seq p                n                (M.delete i v)++update :: Id k -> a -> Seq k a -> Seq k a+update i a s@(Seq p n v) +    | member i s = Seq p n (M.insert i a v)++insertBefore :: forall k a e . Id k -> a -> Seq k a -> (forall k'. Seq (k :|: k') a -> e) -> e+insertBefore i a s@(Seq p n v) f +    | member i s = runICC g where++        g :: ICC I2 v e+        g (v' `PlusMap` n' `PlusMap` _) p' (k:_) = case previous s i of++            Just j -> f $ Seq (M.insert i' k' $ M.insert k' (left j) $ fmap left p `union` fmap right p') +                              (M.insert (left j) k' $ M.insert k' i' $ fmap left n `union` fmap right n')+                              (M.insert k' a $ v `union` v')+            _      -> f $ Seq (M.insert i' k' $ fmap left p `union` fmap right p') +                              (M.insert k' i' $ fmap left n `union` fmap right n')+                              (M.insert k' a $ v `union` v')++         where+            k' = right k+            i' = left i++fromList :: forall a e . [a] -> (forall k. Id k -> Id k -> Seq k a -> e) -> e+fromList [] _ = error "IdSequence.fromList: empty list"+fromList (a:as) f = runICC g where++    g :: ICC I2 k e+    g (v `PlusMap` n `PlusMap` _) p (i:is) = h as is i i (Seq p n (M.insert i a v))++    h :: [a] -> [Id k] -> Id k -> Id k -> Seq k a -> e+    h (b:bs) (i:is) k j !(Seq p n v) = h bs is k i $ Seq (M.insert i j p) (M.insert j i n) (M.insert i b v)+    h []     _      k j s = f k j s+    h _      _      _ _ _ = error "impossible: no more ids!"+++++

@@ -0,0 +1,107 @@+{-# LANGUAGE NoBangPatterns #-}++module Data.LinkMap +    ( module Data.IdMap++    , LinkMap, linkMap+    , link, follow+    , lookUp, insert, delete, union+    , member, notMember+    , same+    , (!), fromList+    ) where++import qualified Data.IdMap as M+import Data.IdMap hiding +    (lookUp, insert, inserts, delete, union, member, (!))++import Data.Maybe+import Data.List (foldl')++----------------------------------------++data Pointer k a+    = Link !k+    | Data a++instance Functor (Pointer k) where fmap _f = error "fmap@Pointer"+instance Functor2 Pointer where fmap2 _f = error "fmap2@Pointer"++newtype LinkMap i k a = L (M.Map i k (Pointer (Id k) a))++instance Functor (LinkMap i k) where fmap _f = error "fmap@LinkMap"+++linkMap :: (forall b. Map i k b) -> LinkMap i k a+linkMap m = L m++-- Azonosítunk két kulcsot.+-- Az első kulcshoz tartozó érték elvész.+link    :: I i => Id k -> Id k -> LinkMap i k a -> LinkMap i k a+link a b m@(L mm)+    | equalBy mm ua ub   = m +    | otherwise = L $ M.insert ua (Link ub) mm+ where+    ua = follow m a+    ub = follow m b++follow :: I i => LinkMap i k a -> Id k -> Id k+follow m@(L mm) a = case M.lookUp a mm of+    Just (Link b)   -> case M.lookUp b mm of+        Just (Link c)   -> let+                d = follow m c+            in d `seq` M.unsafeInsert a (Link d) mm `seq` d+        _   -> b+    _   -> a++{- slow version+follow (M m) a = case M.lookup a m of+    Nothing -> a+    Just b  -> follow (M m) b+-}++lookUp :: I i => Id k -> LinkMap i k a -> Maybe a+lookUp i m@(L mm) = case M.lookUp (follow m i) mm of+    Just (Data a)   -> Just a+    _               -> Nothing++insert :: I i => Id k -> a -> LinkMap i k a -> LinkMap i k a+insert i a m@(L mm) = L $ M.insert (follow m i) (Data a) mm++delete :: I i => Id k -> LinkMap i k a -> LinkMap i k a+delete i m@(L mm) = L $ M.delete (follow m i) mm++infixr 2 `union`++union :: LinkMap i k a -> LinkMap i l a -> LinkMap i (k :|: l) a+L a `union` L b = L (fmap (fmap2 left) a `M.union` fmap (fmap2 right) b)+++same :: I i => LinkMap i k a -> Id k -> Id k -> Bool+same m@(L mm) a b = equalBy mm (follow m a) (follow m b)++--------++-- fromList :: [(Id k, Id k)] -> FastLink k+-- fromList l = foldl (\m (a,b)->link a b m) empty l++--unions :: LinkKey k => [Link k] -> Link k+--unions = foldl union separated+++----------------------++infixl 8 !      -- 9 lenne, de ~> miatt 8++(!) :: I i => LinkMap i k a -> Id k -> a+m ! i = maybe (error "Data.LinkMap.!") id (lookUp i m)++member :: I i => Id k -> LinkMap i k a -> Bool+member i = isJust . lookUp i++notMember :: I i => Id k -> LinkMap i k a -> Bool+notMember i = not . member i++fromList :: I i => (forall b. Map i k b) -> [(Id k, a)] -> LinkMap i k a+fromList = foldl' (\m (i,x) -> insert i x m) . linkMap+

@@ -0,0 +1,73 @@+module Data.LinkMap.Tests +    ( tests+    ) where++import Data.LinkMap+import Test.HUnit++import Prelude hiding (null, catch)++-------------------- ++run :: forall b. (forall x. (forall a. LinkMap I0 x a) -> [Id x] -> b) -> b+run f = runICC g  where++    g :: ICC I0 v b+    g _ m ids = f (linkMap m) ids++testList :: [Bool] -> Test+testList = TestList . map (TestCase . assert)++tests :: IO Counts+tests = runTestTT $ TestList+    [ "LinkMap tests" ~: TestList (map testList list)+    ]++list :: [[Bool]]+list =+    [ run $ \m (i1:_) -> +        [same m i1 i1]+    , run $ \n (i1:_) -> +        let m = link i1 i1 n+        in [same m i1 i1, notMember i1 m]+    , run $ \n (i1:_) -> +        let m = link i1 i1 $ insert i1 (1 :: Int) n+        in [same m i1 i1, lookUp i1 m == Just 1]+    , run $ \n (i1:i2:_) -> +        let m = link i1 i2 $ link i2 i1 $ insert i1 (1 :: Int) n+        in [same m i1 i2, lookUp i1 m == Just 1, lookUp i2 m == Just 1]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i3 i1 $ link i2 i3 $ link i2 i1 $ insert i1 (1 :: Int) n+        in [lookUp i1 m == Nothing, lookUp i2 m == Nothing, lookUp i3 m == Nothing]+    , run $ \n (i1:i2:_) -> +        let m = link i1 i2 n +        in [same m i1 i2, same m i2 i1]+    , run $ \n (i1:i2:_) -> +        let m = n +        in [not (same m i1 i2), not (same m i2 i1)]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i3 i2 $ link i2 i1 n+        in [same m i1 i2, same m i1 i3, same m i2 i3]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i3 i1 $ link i2 i1 n +        in [same m i1 i2, same m i1 i3, same m i2 i3]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i2 i3 $ link i2 i1 n +        in [same m i1 i2, same m i1 i3, same m i2 i3]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i1 i3 $ link i2 i1 n +        in [same m i1 i2, same m i1 i3, same m i2 i3]+    , run $ \n (i1:i2:_) -> +        let m = link i1 i2 $ insert i1 (1 :: Int) n +        in [lookUp i1 m == Nothing, lookUp i2 m == Nothing]+    , run $ \n (i1:i2:_) -> +        let m = link i1 i2 $ insert i2 (1 :: Int) n +        in [lookUp i1 m == Just 1, lookUp i2 m == Just 1]+    , run $ \n (i1:i2:i3:_) -> +        let m = link i3 i2 $ link i2 i1 $ insert i1 (1 :: Int) n +        in [lookUp i1 m == Just 1, lookUp i2 m == Just 1, lookUp i3 m == Just 1]+    -- ...+    ]+++

@@ -0,0 +1,28 @@+module Data.List.IdMap+    where++import Data.IdMap++import qualified Data.List as List+import Data.Maybe++-----------------------------------------------------------------------------------++nubId :: I m => Set m a -> [Id a] -> (Set m a, [Id a])+nubId s [] = (s, [])+nubId s (h:t)+    | h `member` s   = nubId s t+    | otherwise         = h `add` nubId (setInsert h s) t+ where+    add :: a -> (b, [a]) -> (b, [a])+    x `add` ~(s, xs) = (s, x:xs)+++fromList' :: I m => Map m a [b] -> [(Id a, b)] -> Map m a [b]+fromList' = List.foldl' f where++    f m (a,b) = case lookUp a m of+        Nothing -> insert a [b] m+        Just bs -> insert a (b:bs) m++

@@ -0,0 +1,21 @@+module Data.Sequence.IdMap.Profile+    ( prof1+    , prof2+    ) where++import Data.Sequence.IdMap+import Data.List++prof1 :: Int -> Int -> Int+prof1 a b +    = sum $ toList $ foldl' (><) empty $ map fromList $ take a [take b [x..] | x<- [0::Int,10..]]++prof2 :: Int -> Int+prof2 n +    = sum $ toList $ f n 0+ where+    f :: Int -> Int -> Seq Int+    f 0 i = singleton i+    f n' i = f (n'-1) i >< f (n'-1) (i+1)++

@@ -0,0 +1,25 @@+module Data.Sequence.Profile+    ( prof1+    , prof2+    ) where++import Data.Sequence hiding (take)+import Data.List++prof1 :: Int -> Int -> Int+prof1 a b +    = sum $ toList $ foldl' (><) empty $ map fromList $ take a [take b [x..] | x<- [0::Int,10..]]++prof2 :: Int -> Int+prof2 n +    = sum $ toList $ f n 0+ where+    f :: Int -> Int -> Seq Int+    f 0 i = singleton i+    f n' i = f (n'-1) i >< f (n'-1) (i+1)++toList :: Seq a -> [a]+toList s = case viewl s of+    EmptyL  -> []+    a :< ss -> a: toList ss+

@@ -0,0 +1,1294 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml"+><head+  ><title+    >Implementing Pointer Algorithms in Haskell &mdash; Exercises</title+    ><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"+     /><meta name="generator" content="pandoc"+     /><meta name="author" content="P&#233;ter Divi&#225;nszky"+     /><meta name="date" content="CEFP, Budapest &amp; Kom&#225;rno, 25-30 May 2009"+     /><style type="text/css"+    >+table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode, table.sourceCode pre +   { margin: 0; padding: 0; border: 0; vertical-align: baseline; border: none; }+td.lineNumbers { border-right: 1px solid #AAAAAA; text-align: right; color: #AAAAAA; padding-right: 5px; padding-left: 5px; }+td.sourceCode { padding-left: 5px; }+pre.sourceCode { }+pre.sourceCode span.Normal { }+pre.sourceCode span.Keyword { color: #007020; font-weight: bold; } +pre.sourceCode span.DataType { color: #902000; }+pre.sourceCode span.DecVal { color: #40a070; }+pre.sourceCode span.BaseN { color: #40a070; }+pre.sourceCode span.Float { color: #40a070; }+pre.sourceCode span.Char { color: #4070a0; }+pre.sourceCode span.String { color: #4070a0; }+pre.sourceCode span.Comment { color: #60a0b0; font-style: italic; }+pre.sourceCode span.Others { color: #007020; }+pre.sourceCode span.Alert { color: red; font-weight: bold; }+pre.sourceCode span.Function { color: #06287e; }+pre.sourceCode span.RegionMarker { }+pre.sourceCode span.Error { color: red; font-weight: bold; }+</style+    ><!-- configuration parameters -->+<meta name="defaultView" content="slideshow" />+<meta name="controlVis" content="hidden" />+<style type="text/css" media="projection" id="slideProj">+/* Do not edit or override these styles! The system will likely break if you do. */++div#header, div#footer, div#controls, .slide {position: absolute;}+html>body div#header, html>body div#footer, +  html>body div#controls, html>body .slide {position: fixed;}+.handout {display: none;}+.layout {display: block;}+.slide, .hideme, .incremental {visibility: hidden;}+#slide0 {visibility: visible;}++/* The following styles size, place, and layer the slide components.+   Edit these if you want to change the overall slide layout.+   The commented lines can be uncommented (and modified, if necessary) +    to help you with the rearrangement process. */++/* target = 1024x768 */++/* img { float: right; padding-left: 10%; padding-bottom: 30px } */+++div#header, div#footer, .slide {width: 100%; top: 0; left: 0;}+div#header {top: 0; height: 3em; z-index: 1;}+div#footer {top: auto; bottom: 0; height: 2.5em; z-index: 5;}+.slide {top: 0; width: 92%; padding: 3.5em 4% 4%; z-index: 2;  list-style: none;}+div#controls {left: 50%; bottom: 0; width: 50%; z-index: 100;}+div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;+  margin: 0;}+#currentSlide {position: absolute; width: 10%; left: 45%; bottom: 1em; z-index: 10;}+html>body #currentSlide {position: fixed;}++/*+div#header {background: #FCC;}+div#footer {background: #CCF;}+div#controls {background: #BBD;}+div#currentSlide {background: #FFC;}+*/++/* Following are the presentation styles -- edit away! */++body {background: #FFF url(bodybg.gif) -16px 0 no-repeat; color: #000; font-size: 2em;}+:link, :visited {text-decoration: none; color: #00C;}+#controls :active {color: #88A !important;}+#controls :focus {outline: 1px dotted #227;}+h1, h2, h3, h4 {font-size: 100%; margin: 0; padding: 0; font-weight: inherit;}+ul, pre {margin: 0; line-height: 1em;}+html, body {margin: 0; padding: 0;}++blockquote, q {font-style: italic;}+blockquote {padding: 0 2em 0.5em; margin: 0 1.5em 0.5em; text-align: center; font-size: 1em;}+blockquote p {margin: 0;}+blockquote i {font-style: normal;}+blockquote b {display: block; margin-top: 0.5em; font-weight: normal; font-size: smaller; font-style: normal;}+blockquote b i {font-style: italic;}++kbd {font-weight: bold; font-size: 1em;}+sup {font-size: smaller; line-height: 1px;}++.slide code {padding: 2px 0.25em; font-weight: bold; color: #533;}+.slide code.bad, code del {color: red;}+.slide code.old {color: silver;}+.slide pre {padding: 0; margin: 0.25em 0 0.5em 0.5em; color: #533; font-size: 90%;}+.slide pre code {display: block;}+.slide ul {margin-left: 5%; margin-right: 7%; list-style: disc;}+.slide li {margin-top: 0.75em; margin-right: 0;}+.slide ul ul {line-height: 1;}+.slide ul ul li {margin: .2em; font-size: 85%; list-style: square;}+.slide img.leader {display: block; margin: 0 auto;}++div#header, div#footer {background: #EEE; color: #AAB;+  font-family: Verdana, Helvetica, sans-serif;}+div#header {background: #EEE url(bodybg.gif) -16px 0 no-repeat;+  line-height: 1px;}+div#footer {font-size: 0.5em; font-weight: bold; padding: 1em 0;}+#footer h1, #footer h2 {display: block; padding: 0 1em;}+#footer h2 {font-style: italic;}++div.long {font-size: 0.75em;}+.slide h1 {position: absolute; top: 0.7em; left: 0px; z-index: 1;+  margin: 0; padding: 0.3em 0 0 50px; white-space: nowrap;+  font: bold 150%/1em Helvetica, sans-serif;+  color: #028; background: #EEE;}+.slide h3 {font-size: 130%;}+h1 abbr {font-variant: small-caps;}++div#controls {position: absolute; left: 50%; bottom: 0;+  width: 50%;+  text-align: right; font: bold 0.9em Verdana, Helvetica, sans-serif;}+html>body div#controls {position: fixed; padding: 0 0 1em 0;+  top: auto;}+div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;+  margin: 0; padding: 0;}+#controls #navLinks a {padding: 0; margin: 0 0.5em; +  background: #EEE; border: none; color: #779; +  cursor: pointer;}+#controls #navList {height: 1em;}+#controls #navList #jumplist {position: absolute; bottom: 0; right: 0; background: #DDD; color: #227;}++#currentSlide {text-align: center; font-size: 0.5em; color: #449;}++#slide0 {padding-top: 3.5em; font-size: 90%;}+#slide0 h1 {position: static; margin: 1em 0 0; padding: 0;+   font: bold 2em Helvetica, sans-serif; white-space: normal;+   color: #000; background: transparent;}+#slide0 h2 {font: bold italic 1em Helvetica, sans-serif; margin: 0.25em;}+#slide0 h3 {margin-top: 1.5em; font-size: 1.5em;}+#slide0 h4 {margin-top: 0; font-size: 1em;}++ul.urls {list-style: none; display: inline; margin: 0;}+.urls li {display: inline; margin: 0;}+.note {display: none;}+.external {border-bottom: 1px dotted gray;}+html>body .external {border-bottom: none;}+.external:after {content: " \274F"; font-size: smaller; color: #77B;}++.incremental, .incremental *, .incremental *:after {color: #DDE; visibility: visible;}+img.incremental {visibility: hidden;}+.slide .current {color: #B02;}+++/* diagnostics++li:after {content: " [" attr(class) "]"; color: #F88;}+*/++</style>+<style type="text/css" media="projection" id="operaFix">+/* DO NOT CHANGE THESE unless you really want to break Opera Show */+.slide {+	visibility: visible !important;+	position: static !important;+	page-break-before: always;+}+#slide0 {page-break-before: avoid;}++</style>+<style type="text/css" media="screen" id="outlineStyle">+/* don't change this unless you want the layout stuff to show up in the outline view! */++.layout div, #footer *, #controlForm * {display: none;}+#footer, #controls, #controlForm, #navLinks, #toggle {+  display: block; visibility: visible; margin: 0; padding: 0;}+#toggle {float: right; padding: 0.5em;}+html>body #toggle {position: fixed; top: 0; right: 0;}++/* making the outline look pretty-ish */++#slide0 h1, #slide0 h2, #slide0 h3, #slide0 h4 {border: none; margin: 0;}+#slide0 h1 {padding-top: 1.5em;}+.slide h1 {margin: 1.5em 0 0; padding-top: 0.25em;+  border-top: 1px solid #888; border-bottom: 1px solid #AAA;}+#toggle {border: 1px solid; border-width: 0 0 1px 1px; background: #FFF;}++</style>+<style type="text/css" media="print" id="slidePrint">+/* The following rule is necessary to have all slides appear in print! DO NOT REMOVE IT! */+.slide, ul {page-break-inside: avoid; visibility: visible !important;}+h1 {page-break-after: avoid;}++body {font-size: 12pt; background: white;}+* {color: black;}++#slide0 h1 {font-size: 200%; border: none; margin: 0.5em 0 0.25em;}+#slide0 h3 {margin: 0; padding: 0;}+#slide0 h4 {margin: 0 0 0.5em; padding: 0;}+#slide0 {margin-bottom: 3em;}++h1 {border-top: 2pt solid gray; border-bottom: 1px dotted silver;}+.extra {background: transparent !important;}+div.extra, pre.extra, .example {font-size: 10pt; color: #333;}+ul.extra a {font-weight: bold;}+p.example {display: none;}++#header {display: none;}+#footer h1 {margin: 0; border-bottom: 1px solid; color: gray; font-style: italic;}+#footer h2, #controls {display: none;}++/* The following rule keeps the layout stuff out of print.  Remove at your own risk! */+.layout, .layout * {display: none !important;}++</style>+<script type="text/javascript">+// S5 v1.1 slides.js -- released into the Public Domain+//+// Please see http://www.meyerweb.com/eric/tools/s5/credits.html for information +// about all the wonderful and talented contributors to this code!+var undef;var slideCSS='';var snum=0;var smax=1;var incpos=0;var number=undef;var s5mode=true;var defaultView='slideshow';var controlVis='visible';var isIE=navigator.appName=='Microsoft Internet Explorer'&&navigator.userAgent.indexOf('Opera')<1?1:0;var isOp=navigator.userAgent.indexOf('Opera')>-1?1:0;var isGe=navigator.userAgent.indexOf('Gecko')>-1&&navigator.userAgent.indexOf('Safari')<1?1:0;function hasClass(object,className){if(!object.className)return false;return(object.className.search('(^|\\s)'+className+'(\\s|$)')!=-1);}+function hasValue(object,value){if(!object)return false;return(object.search('(^|\\s)'+value+'(\\s|$)')!=-1);}+function removeClass(object,className){if(!object)return;object.className=object.className.replace(new RegExp('(^|\\s)'+className+'(\\s|$)'),RegExp.$1+RegExp.$2);}+function addClass(object,className){if(!object||hasClass(object,className))return;if(object.className){object.className+=' '+className;}else{object.className=className;}}+function GetElementsWithClassName(elementName,className){var allElements=document.getElementsByTagName(elementName);var elemColl=new Array();for(var i=0;i<allElements.length;i++){if(hasClass(allElements[i],className)){elemColl[elemColl.length]=allElements[i];}}+return elemColl;}+function isParentOrSelf(element,id){if(element==null||element.nodeName=='BODY')return false;else if(element.id==id)return true;else return isParentOrSelf(element.parentNode,id);}+function nodeValue(node){var result="";if(node.nodeType==1){var children=node.childNodes;for(var i=0;i<children.length;++i){result+=nodeValue(children[i]);}}+else if(node.nodeType==3){result=node.nodeValue;}+return(result);}+function slideLabel(){var slideColl=GetElementsWithClassName('*','slide');var list=document.getElementById('jumplist');smax=slideColl.length;for(var n=0;n<smax;n++){var obj=slideColl[n];var did='slide'+n.toString();obj.setAttribute('id',did);if(isOp)continue;var otext='';var menu=obj.firstChild;if(!menu)continue;while(menu&&menu.nodeType==3){menu=menu.nextSibling;}+if(!menu)continue;var menunodes=menu.childNodes;for(var o=0;o<menunodes.length;o++){otext+=nodeValue(menunodes[o]);}+list.options[list.length]=new Option(n+' : '+otext,n);}}+function currentSlide(){var cs;if(document.getElementById){cs=document.getElementById('currentSlide');}else{cs=document.currentSlide;}+cs.innerHTML='<span id="csHere">'+snum+'<\/span> '+'<span id="csSep">\/<\/span> '+'<span id="csTotal">'+(smax-1)+'<\/span>';if(snum==0){cs.style.visibility='hidden';}else{cs.style.visibility='visible';}}+function go(step){if(document.getElementById('slideProj').disabled||step==0)return;var jl=document.getElementById('jumplist');var cid='slide'+snum;var ce=document.getElementById(cid);if(incrementals[snum].length>0){for(var i=0;i<incrementals[snum].length;i++){removeClass(incrementals[snum][i],'current');removeClass(incrementals[snum][i],'incremental');}}+if(step!='j'){snum+=step;lmax=smax-1;if(snum>lmax)snum=lmax;if(snum<0)snum=0;}else+snum=parseInt(jl.value);var nid='slide'+snum;var ne=document.getElementById(nid);if(!ne){ne=document.getElementById('slide0');snum=0;}+if(step<0){incpos=incrementals[snum].length}else{incpos=0;}+if(incrementals[snum].length>0&&incpos==0){for(var i=0;i<incrementals[snum].length;i++){if(hasClass(incrementals[snum][i],'current'))+incpos=i+1;else+addClass(incrementals[snum][i],'incremental');}}+if(incrementals[snum].length>0&&incpos>0)+addClass(incrementals[snum][incpos-1],'current');ce.style.visibility='hidden';ne.style.visibility='visible';jl.selectedIndex=snum;currentSlide();number=0;}+function goTo(target){if(target>=smax||target==snum)return;go(target-snum);}+function subgo(step){if(step>0){removeClass(incrementals[snum][incpos-1],'current');removeClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos],'current');incpos++;}else{incpos--;removeClass(incrementals[snum][incpos],'current');addClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos-1],'current');}}+function toggle(){var slideColl=GetElementsWithClassName('*','slide');var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');if(!slides.disabled){slides.disabled=true;outline.disabled=false;s5mode=false;fontSize('1em');for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='visible';}}else{slides.disabled=false;outline.disabled=true;s5mode=true;fontScale();for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='hidden';}+slideColl[snum].style.visibility='visible';}}+function showHide(action){var obj=GetElementsWithClassName('*','hideme')[0];switch(action){case's':obj.style.visibility='visible';break;case'h':obj.style.visibility='hidden';break;case'k':if(obj.style.visibility!='visible'){obj.style.visibility='visible';}else{obj.style.visibility='hidden';}+break;}}+function keys(key){if(!key){key=event;key.which=key.keyCode;}+if(key.which==84){toggle();return;}+if(s5mode){switch(key.which){case 10:case 13:if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;if(number!=undef){goTo(number);break;}+case 32:case 34:case 39:case 40:if(number!=undef){go(number);}else if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}+break;case 33:case 37:case 38:if(number!=undef){go(-1*number);}else if(!incrementals[snum]||incpos<=0){go(-1);}else{subgo(-1);}+break;case 36:goTo(0);break;case 35:goTo(smax-1);break;case 67:showHide('k');break;}+if(key.which<48||key.which>57){number=undef;}else{if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;number=(((number!=undef)?number:0)*10)+(key.which-48);}}+return false;}+function clicker(e){number=undef;var target;if(window.event){target=window.event.srcElement;e=window.event;}else target=e.target;if(target.getAttribute('href')!=null||hasValue(target.rel,'external')||isParentOrSelf(target,'controls')||isParentOrSelf(target,'embed')||isParentOrSelf(target,'object'))return true;if(!e.which||e.which==1){if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}}}+function findSlide(hash){var target=null;var slides=GetElementsWithClassName('*','slide');for(var i=0;i<slides.length;i++){var targetSlide=slides[i];if((targetSlide.name&&targetSlide.name==hash)||(targetSlide.id&&targetSlide.id==hash)){target=targetSlide;break;}}+while(target!=null&&target.nodeName!='BODY'){if(hasClass(target,'slide')){return parseInt(target.id.slice(5));}+target=target.parentNode;}+return null;}+function slideJump(){if(window.location.hash==null)return;var sregex=/^#slide(\d+)$/;var matches=sregex.exec(window.location.hash);var dest=null;if(matches!=null){dest=parseInt(matches[1]);}else{dest=findSlide(window.location.hash.slice(1));}+if(dest!=null)+go(dest-snum);}+function fixLinks(){var thisUri=window.location.href;thisUri=thisUri.slice(0,thisUri.length-window.location.hash.length);var aelements=document.getElementsByTagName('A');for(var i=0;i<aelements.length;i++){var a=aelements[i].href;var slideID=a.match('\#slide[0-9]{1,2}');if((slideID)&&(slideID[0].slice(0,1)=='#')){var dest=findSlide(slideID[0].slice(1));if(dest!=null){if(aelements[i].addEventListener){aelements[i].addEventListener("click",new Function("e","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"if (e.preventDefault) e.preventDefault();"),true);}else if(aelements[i].attachEvent){aelements[i].attachEvent("onclick",new Function("","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"event.returnValue = false;"));}}}}}+function externalLinks(){if(!document.getElementsByTagName)return;var anchors=document.getElementsByTagName('a');for(var i=0;i<anchors.length;i++){var anchor=anchors[i];if(anchor.getAttribute('href')&&hasValue(anchor.rel,'external')){anchor.target='_blank';addClass(anchor,'external');}}}+function createControls(){var controlsDiv=document.getElementById("controls");if(!controlsDiv)return;var hider=' onmouseover="showHide(\'s\');" onmouseout="showHide(\'h\');"';var hideDiv,hideList='';if(controlVis=='hidden'){hideDiv=hider;}else{hideList=hider;}+controlsDiv.innerHTML='<form action="#" id="controlForm"'+hideDiv+'>'+'<div id="navLinks">'+'<a accesskey="t" id="toggle" href="javascript:toggle();">&#216;<\/a>'+'<a accesskey="z" id="prev" href="javascript:go(-1);">&laquo;<\/a>'+'<a accesskey="x" id="next" href="javascript:go(1);">&raquo;<\/a>'+'<div id="navList"'+hideList+'><select id="jumplist" onchange="go(\'j\');"><\/select><\/div>'+'<\/div><\/form>';if(controlVis=='hidden'){var hidden=document.getElementById('navLinks');}else{var hidden=document.getElementById('jumplist');}+addClass(hidden,'hideme');}+function fontScale(){if(!s5mode)return false;var vScale=22;var hScale=32;if(window.innerHeight){var vSize=window.innerHeight;var hSize=window.innerWidth;}else if(document.documentElement.clientHeight){var vSize=document.documentElement.clientHeight;var hSize=document.documentElement.clientWidth;}else if(document.body.clientHeight){var vSize=document.body.clientHeight;var hSize=document.body.clientWidth;}else{var vSize=700;var hSize=1024;}+var newSize=Math.min(Math.round(vSize/vScale),Math.round(hSize/hScale));fontSize(newSize+'px');if(isGe){var obj=document.getElementsByTagName('body')[0];obj.style.display='none';obj.style.display='block';}}+function fontSize(value){if(!(s5ss=document.getElementById('s5ss'))){if(!isIE){document.getElementsByTagName('head')[0].appendChild(s5ss=document.createElement('style'));s5ss.setAttribute('media','screen, projection');s5ss.setAttribute('id','s5ss');}else{document.createStyleSheet();document.s5ss=document.styleSheets[document.styleSheets.length-1];}}+if(!isIE){while(s5ss.lastChild)s5ss.removeChild(s5ss.lastChild);s5ss.appendChild(document.createTextNode('body {font-size: '+value+' !important;}'));}else{document.s5ss.addRule('body','font-size: '+value+' !important;');}}+function notOperaFix(){slideCSS=document.getElementById('slideProj').href;var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');slides.setAttribute('media','screen');outline.disabled=true;if(isGe){slides.setAttribute('href','null');slides.setAttribute('href',slideCSS);}+if(isIE&&document.styleSheets&&document.styleSheets[0]){document.styleSheets[0].addRule('img','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('div','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('.slide','behavior: url(ui/default/iepngfix.htc)');}}+function getIncrementals(obj){var incrementals=new Array();if(!obj)+return incrementals;var children=obj.childNodes;for(var i=0;i<children.length;i++){var child=children[i];if(hasClass(child,'incremental')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'incremental');for(var j=0;j<child.childNodes.length;j++){if(child.childNodes[j].nodeType==1){addClass(child.childNodes[j],'incremental');}}}else{incrementals[incrementals.length]=child;removeClass(child,'incremental');}}+if(hasClass(child,'show-first')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'show-first');if(child.childNodes[isGe].nodeType==1){removeClass(child.childNodes[isGe],'incremental');}}else{incrementals[incrementals.length]=child;}}+incrementals=incrementals.concat(getIncrementals(child));}+return incrementals;}+function createIncrementals(){var incrementals=new Array();for(var i=0;i<smax;i++){incrementals[i]=getIncrementals(document.getElementById('slide'+i));}+return incrementals;}+function defaultCheck(){var allMetas=document.getElementsByTagName('meta');for(var i=0;i<allMetas.length;i++){if(allMetas[i].name=='defaultView'){defaultView=allMetas[i].content;}+if(allMetas[i].name=='controlVis'){controlVis=allMetas[i].content;}}}+function trap(e){if(!e){e=event;e.which=e.keyCode;}+try{modifierKey=e.ctrlKey||e.altKey||e.metaKey;}+catch(e){modifierKey=false;}+return modifierKey||e.which==0;}+function startup(){defaultCheck();if(!isOp)+createControls();slideLabel();fixLinks();externalLinks();fontScale();if(!isOp){notOperaFix();incrementals=createIncrementals();slideJump();if(defaultView=='outline'){toggle();}+document.onkeyup=keys;document.onkeypress=trap;document.onclick=clicker;}}+window.onload=startup;window.onresize=function(){setTimeout('fontScale()',50);}+</script>++</head+  ><body+  ><div class="layout">+<div id="controls"></div>+<div id="currentSlide"></div>+<div id="header"></div>+<div id="footer">+<h1 id="cefp-budapest-&amp;-kom&#225;rno-25-30-may-2009"+    >CEFP, Budapest &amp; Komárno, 25-30 May 2009</h1+    ><h2 id="implementing-pointer-algorithms-in-haskell---exercises"+    >Implementing Pointer Algorithms in Haskell &mdash; Exercises</h2+    ></div>+</div>+<div class="presentation">++<div class="slide">+<h1 id="implementing-pointer-algorithms-in-haskell---exercises-1"+    >Implementing Pointer Algorithms in Haskell &mdash; Exercises</h1+    ><h3 id="p&#233;ter-divi&#225;nszky"+    >Péter Diviánszky</h3+    ><h4 id="cefp-budapest-&amp;-kom&#225;rno-25-30-may-2009-1"+    >CEFP, Budapest &amp; Komárno, 25-30 May 2009</h4+    ></div>+<div class="slide">+<h1 id="legend"+    >Legend</h1+    ><p+    >E2: exercise<br+       />*E3: exercise, hard to solve<br+       />-E6: exercise, easy to solve</p+    ></div>+<div class="slide">+<h1 id="programming-environment"+    >Programming Environment</h1+    ><p+    ><code+      >GHC</code+      > and <code+      >cabal-install</code+      > are needed.</p+    ><ol style="list-style-type: decimal;"+    ><li+      >Run the following commands in a terminal:</li+      ></ol+    ><pre class="sourceCode bash"+    ><code+      ><span class="Normal NormalText"+	>cabal update</span+	><br+	 /><span class="Normal NormalText"+	>cabal </span+	><span class="Keyword Command"+	>install</span+	><span class="Normal NormalText"+	> linear</span+	><span class="Normal Option"+	>-maps</span+	><span class="Normal NormalText"+	> </span+	><span class="Normal Option"+	>-fcheck</span+	><br+	 /><span class="Normal NormalText"+	>firefox </span+	><span class="Keyword Backquote"+	>`</span+	><span class="Normal NormalText"+	>linear</span+	><span class="Normal Option"+	>-maps-exercises</span+	><span class="Keyword Backquote"+	>`</span+	><br+	 /></code+      ></pre+    ><ol start="2" style="list-style-type: decimal;"+    ><li+      >Open an editor and save an empty file <code+	>Maps.hs</code+	> (do not quit).</li+      ><li+      >Run the command &ldquo;<code+	>ghci Maps.hs</code+	>&rdquo; in a terminal &mdash; this is an interpreter.</li+      ></ol+    ></div>+<div class="slide">+<h1 id="first-steps"+    >First Steps</h1+    ><ul+    ><li+      >Enter <code+	>3*23</code+	> in the interpreter. The result should be <code+	>69</code+	>.</li+      ><li+      >Write <code+	>x = 3*3</code+	> in the editor and save the file. Enter <code+	>:r</code+	> (reload) and enter <code+	>x</code+	> in the interpreter. The result should be <code+	>9</code+	>.</li+      ><li+      >You can navigate between previous commands with up and down arrows.</li+      ><li+      ><p+	><code+	  >:t x</code+	  > shows the type of <code+	  >x</code+	  >.</p+	></li+      ><li+      ><p+	>Get acquainted with Haskell (look at <a href="http://haskell.org"+	  >haskell.org</a+	  > if necessary).</p+	></li+      ></ul+    ></div>+<div class="slide">+<h1 id="e1-depth-first-walk"+    >E1: Depth-First Walk</h1+    ><p+    >If we start from A then we get A, B, D, E, C, F, G, H.</p+    ><p+    ><img src="graph.png" alt="graph"+       /></p+    ></div>+<div class="slide">+<h1 id="instructions"+    >Instructions</h1+    ><p+    >Define a function with the following type signature:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Keyword"+	>import</span+	><span class="Normal NormalText"+	> </span+	><span class="Normal ModuleName"+	>Data.IdMap</span+	><span class="Normal NormalText"+	>   </span+	><span class="Comment"+	>-- at the beginning of the file</span+	><br+	 /><span class="Keyword"+	>import</span+	><span class="Normal NormalText"+	> </span+	><span class="Normal ModuleName"+	>Data.Graph.IdMap.Tests</span+	><br+	 /><br+	 /><span class="Keyword"+	>type</span+	><span class="Normal NormalText"+	> ChildrenFun k = Id k -&gt; [Id k]</span+	><br+	 /><br+	 /><span class="Function FunctionDefinition"+	>depthFirstWalk ::</span+	><span class="Normal NormalText"+	> </span+	><br+	 /><span class="Normal NormalText"+	>    I i =&gt;            </span+	><span class="Comment"+	>-- type level integer </span+	><br+	 /><span class="Normal NormalText"+	>    ChildrenFun k -&gt;  </span+	><span class="Comment"+	>-- children function</span+	><br+	 /><span class="Normal NormalText"+	>    Set i k -&gt;        </span+	><span class="Comment"+	>-- set of already visited nodes </span+	><br+	 /><span class="Normal NormalText"+	>    [Id k] -&gt;         </span+	><span class="Comment"+	>-- nodes to be visited</span+	><br+	 /><span class="Normal NormalText"+	>        [Id k]        </span+	><span class="Comment"+	>-- visited nodes</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="instructions-continued"+    >Instructions (continued)</h1+    ><p+    >Use the following primitives:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>member    ::</span+	><span class="Normal NormalText"+	> I i =&gt; Id k -&gt; Set i k -&gt; </span+	><span class="DataType TypeConstructor"+	>Bool</span+	><br+	 /><span class="Function FunctionDefinition"+	>setInsert ::</span+	><span class="Normal NormalText"+	> I i =&gt; Id k -&gt; Set i k -&gt; Set i k</span+	><br+	 /></code+      ></pre+    ><p+    >Test your function in the interpreter:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>*Main&gt; testWalk depthFirstWalk </span+	><span class="String"+	>&quot;A&quot;</span+	><br+	 /><span class="String"+	>&quot;ABDECFGH&quot;</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="help"+    >Help</h1+    ><p+    >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).</p+    ><p+    >You will probably need the functions <code+      >(++)</code+      > and <code+      >(:)</code+      >.</p+    ></div>+<div class="slide">+<h1 id="e2-postorder-walk"+    >E2: Postorder Walk</h1+    ><p+    >If we start from A then we get D, E, B, F, H, G, C, A.</p+    ><p+    ><img src="graph.png" alt="graph"+       /></p+    ></div>+<div class="slide">+<h1 id="instructions-1"+    >Instructions</h1+    ><p+    >Define a postorder walk:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>postOrderWalk ::</span+	><span class="Normal NormalText"+	> I i =&gt; ChildrenFun k -&gt; Set i k -&gt; [Id k] -&gt; [Id k]</span+	><br+	 /></code+      ></pre+    ><p+    >Use the following data structure inside in a &ldquo;task list&rdquo;:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Keyword"+	>data</span+	><span class="Normal NormalText"+	> Task a = Return a | Visit a</span+	><br+	 /></code+      ></pre+    ><p+    >Use the same primitives as in <code+      >depthFirstWalk</code+      >. Test your function in the interpreter:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>*Main&gt; testWalk postOrderWalk </span+	><span class="String"+	>&quot;A&quot;</span+	><br+	 /><span class="String"+	>&quot;DEBFHGCA&quot;</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="help-1"+    >Help</h1+    ><p+    >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 <code+      >Visit</code+      > tasks.</p+    ><p+    >The local function is a recursive function.<br+       />Make pattern matching on the identifier list. If it is not empty, and the first identifier is a <code+      >Return</code+      > task then return it and make a recursive call.<br+       />If the first identifier is a <code+      >Visit</code+      > task then test whether it is in the set.<br+       />If it is not in the set, make a recursive call with a modified set and an extended task list.<br+       />The extended task list should contain the children of the first identifier (as <code+      >Visit</code+      > tasks) and the first identifier as <code+      >Return</code+      > task, and the old tasks.</p+    ></div>+<div class="slide">+<h1 id="e2-postorder-walk-variant"+    >E2&rsquo;: Postorder Walk Variant</h1+    ><p+    >Define the function:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>revPostOrderWalk ::</span+	><br+	 /><span class="Normal NormalText"+	>    I i =&gt; </span+	><br+	 /><span class="Normal NormalText"+	>    Children k -&gt; </span+	><br+	 /><span class="Normal NormalText"+	>    Set i k -&gt; </span+	><br+	 /><span class="Normal NormalText"+	>    [Id k] -&gt; </span+	><br+	 /><span class="Normal NormalText"+	>        ( Set i k   </span+	><span class="Comment"+	>-- set of visited nodes</span+	><br+	 /><span class="Normal NormalText"+	>        , [Id k])   </span+	><span class="Comment"+	>-- visited nodes in reversed postorder</span+	><br+	 /></code+      ></pre+    ><p+    >Help: Use accumulation (define a local function with an additional list parameter which accumulates the values).</p+    ></div>+<div class="slide">+<h1 id="e3-mapped-walk"+    >*E3: Mapped Walk</h1+    ><p+    >If we start from B, G, A then we get E, D, B; H, G; F, C, A.</p+    ><p+    ><img src="graph.png" alt="graph"+       /></p+    ></div>+<div class="slide">+<h1 id="instructions-2"+    >Instructions</h1+    ><p+    >Define the function:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>mapWalk ::</span+	><span class="Normal NormalText"+	> I i =&gt; ChildrenFun k -&gt; Set i k -&gt; [Id k] -&gt; [[Id k]]</span+	><br+	 /></code+      ></pre+    ><p+    ><code+      >mapWalk</code+      > 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. &hellip;</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>*Main&gt; testMapWalk mapWalk </span+	><span class="String"+	>&quot;BGA&quot;</span+	><br+	 /><span class="Normal NormalText"+	>[</span+	><span class="String"+	>&quot;EDB&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;HG&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;FCA&quot;</span+	><span class="Normal NormalText"+	>]</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e3-mapped-walk-variant"+    >E3&rsquo;: Mapped Walk Variant</h1+    ><p+    >Define a function similar to <code+      >mapWalk</code+      > but</p+    ><ul+    ><li+      >The result is reversed.</li+      ><li+      >Collect the nodes which are present in the set.</li+      ></ul+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>revMapWalk ::</span+	><span class="Normal NormalText"+	> I i =&gt; Children k -&gt; Set i k -&gt; [Id k] -&gt; [[Id k]]</span+	><br+	 /></code+      ></pre+    ><p+    >Help: Use accumulation.</p+    ></div>+<div class="slide">+<h1 id="e4-strongly-connected-components"+    >*E4: Strongly Connected Components</h1+    ><p+    >If we start from A then we get D; E; B; I, H, G; C, F, A.<br+       />(If these are modules then this is the compilation order.)</p+    ><p+    ><img src="graph.png" alt="graph"+       /></p+    ></div>+<div class="slide">+<h1 id="instructions-3"+    >Instructions</h1+    ><p+    >Define the function:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>scc ::</span+	><span class="Normal NormalText"+	> I i =&gt; </span+	><br+	 /><span class="Normal NormalText"+	>    ChildrenFun k -&gt;  </span+	><span class="Comment"+	>-- children</span+	><br+	 /><span class="Normal NormalText"+	>    ChildrenFun k -&gt;  </span+	><span class="Comment"+	>-- parents</span+	><br+	 /><span class="Normal NormalText"+	>    Set i k -&gt;        </span+	><span class="Comment"+	>-- an empty set</span+	><br+	 /><span class="Normal NormalText"+	>    [Id k] -&gt;         </span+	><span class="Comment"+	>-- initial nodes</span+	><br+	 /><span class="Normal NormalText"+	>        ( Set i k     </span+	><span class="Comment"+	>-- an empty set</span+	><br+	 /><span class="Normal NormalText"+	>        , [[Id k]])   </span+	><span class="Comment"+	>-- the scc of the reachable nodes</span+	><br+	 /></code+      ></pre+    ><p+    >Test case:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>*Main&gt; testSCC scc </span+	><span class="String"+	>&quot;A&quot;</span+	><br+	 /><span class="Normal NormalText"+	>[</span+	><span class="String"+	>&quot;D&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;E&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;B&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;HG&quot;</span+	><span class="Normal NormalText"+	>,</span+	><span class="String"+	>&quot;CFA&quot;</span+	><span class="Normal NormalText"+	>]</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e5-replaceLast"+    >-E5: <code+      >replaceLast</code+      ></h1+    ><p+    >Define a function which replaces the last element of a list.</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>replaceLast ::</span+	><span class="Normal NormalText"+	> [a] -&gt; a -&gt; [a]</span+	><br+	 /></code+      ></pre+    ><p+    >Test cases:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>replaceLast [</span+	><span class="DecVal Decimal"+	>1</span+	><span class="Normal NormalText"+	>,</span+	><span class="DecVal Decimal"+	>4</span+	><span class="Normal NormalText"+	>,</span+	><span class="DecVal Decimal"+	>6</span+	><span class="Normal NormalText"+	>] </span+	><span class="DecVal Decimal"+	>7</span+	><span class="Normal NormalText"+	> == [</span+	><span class="DecVal Decimal"+	>1</span+	><span class="Normal NormalText"+	>,</span+	><span class="DecVal Decimal"+	>4</span+	><span class="Normal NormalText"+	>,</span+	><span class="DecVal Decimal"+	>7</span+	><span class="Normal NormalText"+	>]</span+	><br+	 /><span class="Normal NormalText"+	>replaceLast </span+	><span class="String"+	>&quot;take&quot;</span+	><span class="Normal NormalText"+	> </span+	><span class="Char"+	>'x'</span+	><span class="Normal NormalText"+	> == </span+	><span class="String"+	>&quot;takx&quot;</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e6-replaceAndShiftOne"+    >-E6: <code+      >replaceAndShiftOne</code+      ></h1+    ><p+    >Define a function which replaces a list&rsquo;s nth element and shift the old element one position to the right.</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>replaceAndShiftOne ::</span+	><span class="Normal NormalText"+	> </span+	><span class="DataType TypeConstructor"+	>Int</span+	><span class="Normal NormalText"+	> -&gt; [a] -&gt; a -&gt; [a]</span+	><br+	 /></code+      ></pre+    ><p+    >Test cases:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>replaceAndShiftOne </span+	><span class="DecVal Decimal"+	>0</span+	><span class="Normal NormalText"+	> </span+	><span class="String"+	>&quot;abcd&quot;</span+	><span class="Normal NormalText"+	> </span+	><span class="Char"+	>'e'</span+	><span class="Normal NormalText"+	> == </span+	><span class="String"+	>&quot;eacd&quot;</span+	><br+	 /><span class="Normal NormalText"+	>replaceAndShiftOne </span+	><span class="DecVal Decimal"+	>1</span+	><span class="Normal NormalText"+	> </span+	><span class="String"+	>&quot;abcd&quot;</span+	><span class="Normal NormalText"+	> </span+	><span class="Char"+	>'e'</span+	><span class="Normal NormalText"+	> == </span+	><span class="String"+	>&quot;aebd&quot;</span+	><br+	 /><span class="Normal NormalText"+	>replaceAndShiftOne </span+	><span class="DecVal Decimal"+	>2</span+	><span class="Normal NormalText"+	> </span+	><span class="String"+	>&quot;abcd&quot;</span+	><span class="Normal NormalText"+	> </span+	><span class="Char"+	>'e'</span+	><span class="Normal NormalText"+	> == </span+	><span class="String"+	>&quot;abec&quot;</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e7-pointer-reversal-walk"+    >*E7: Pointer Reversal Walk</h1+    ><p+    >Define the pointer reversal algorithm.</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>prWalk ::</span+	><span class="Normal NormalText"+	> </span+	><br+	 /><span class="Normal NormalText"+	>    (I i, I i') =&gt;</span+	><br+	 /><span class="Normal NormalText"+	>    Map i k [Id k] -&gt;  </span+	><span class="Comment"+	>-- a graph</span+	><br+	 /><span class="Normal NormalText"+	>    Map i' k </span+	><span class="DataType TypeConstructor"+	>Int</span+	><span class="Normal NormalText"+	> -&gt;    </span+	><span class="Comment"+	>-- an empty map</span+	><br+	 /><span class="Normal NormalText"+	>    Id k -&gt;            </span+	><span class="Comment"+	>-- start node</span+	><br+	 /><span class="Normal NormalText"+	>        [Id k]         </span+	><span class="Comment"+	>-- reachable nodes in depth first order</span+	><br+	 /></code+      ></pre+    ><p+    ><em+      >next slide</em+      ></p+    ></div>+<div class="slide">+<h1 id="e7-pointer-reversal-walk-continued"+    >*E7: Pointer Reversal Walk (continued)</h1+    ><p+    >Use the helper functions:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>follow, </span+	><span class="Function FunctionDefinition"+	>back ::</span+	><span class="Normal NormalText"+	> </span+	><br+	 /><span class="Normal NormalText"+	>    (I i, I i') =&gt;</span+	><br+	 /><span class="Normal NormalText"+	>    Map i k [Id k] -&gt;  </span+	><span class="Comment"+	>-- modified graph</span+	><br+	 /><span class="Normal NormalText"+	>    Map i' k </span+	><span class="DataType TypeConstructor"+	>Int</span+	><span class="Normal NormalText"+	> -&gt;    </span+	><span class="Comment"+	>-- index map</span+	><br+	 /><span class="Normal NormalText"+	>    Id k -&gt;            </span+	><span class="Comment"+	>-- previous node</span+	><br+	 /><span class="Normal NormalText"+	>    Id k -&gt;            </span+	><span class="Comment"+	>-- this node</span+	><br+	 /><span class="Normal NormalText"+	>        [Id k]         </span+	><span class="Comment"+	>-- reachable nodes in depth first order</span+	><br+	 /></code+      ></pre+    ><p+    ><code+      >follow</code+      > follows an edge, <code+      >back</code+      > goes back on an edge.<br+       />The index map contains already visited nodes. The index show how many children of the node was completely visited.<br+       />The graph is transformed in each step a little but at the end it will have its original shape.</p+    ></div>+<div class="slide">+<h1 id="e7-pointer-reversal-walk-continued-1"+    >*E7: Pointer Reversal Walk (continued)</h1+    ><p+    >Use the following library functions:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>lookUp ::</span+	><span class="Normal NormalText"+	> I i =&gt; Id k -&gt; Map i k a -&gt; </span+	><span class="DataType TypeConstructor"+	>Maybe</span+	><span class="Normal NormalText"+	> a</span+	><br+	 /><br+	 /><span class="Function FunctionDefinition"+	>insert ::</span+	><span class="Normal NormalText"+	> I i =&gt; Id k -&gt; a -&gt; Map i k a -&gt; Map i k a</span+	><br+	 /><br+	 /><span class="Normal NormalText"+	>(!)    :: I i =&gt; Map i k a -&gt; Id k -&gt; a</span+	><br+	 /></code+      ></pre+    ><p+    >Test Cases:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Normal NormalText"+	>*Main&gt; testPrWalk prWalk </span+	><span class="String"+	>&quot;A&quot;</span+	><br+	 /><span class="String"+	>&quot;ABDECFGH&quot;</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e8-linear-time-type-inference"+    >*E8: Linear Time Type Inference</h1+    ><p+    >Begin a new file with the rows:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Keyword"+	>import</span+	><span class="Normal NormalText"+	> </span+	><span class="Normal ModuleName"+	>Data.LinkMap</span+	><br+	 /><br+	 /><span class="Keyword"+	>type</span+	><span class="Normal NormalText"+	> Link i k = LinkMap i k ()</span+	><br+	 /></code+      ></pre+    ><p+    ><code+      >Link</code+      > is a disjoint set data structure.<br+       />We will use the following primitives:</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>link   ::</span+	><span class="Normal NormalText"+	> I i =&gt; Id k -&gt; Id k -&gt; Link i k -&gt; Link i k</span+	><br+	 /><span class="Normal NormalText"+	>        </span+	><span class="Comment"+	>-- make a link from the first id to the second id</span+	><br+	 /><span class="Function FunctionDefinition"+	>follow ::</span+	><span class="Normal NormalText"+	> I i =&gt; Link i k -&gt; Id k -&gt; Id k</span+	><br+	 /><span class="Normal NormalText"+	>        </span+	><span class="Comment"+	>-- follow the links until no link is found</span+	><br+	 /><span class="Function FunctionDefinition"+	>same   ::</span+	><span class="Normal NormalText"+	> I i =&gt; Link i k -&gt; Id k -&gt; Id k -&gt; </span+	><span class="DataType TypeConstructor"+	>Bool</span+	><br+	 /><span class="Normal NormalText"+	>        </span+	><span class="Comment"+	>-- True if follow id1 == follow id2</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e8--types"+    >*E8 / Types</h1+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Keyword"+	>data</span+	><span class="Normal NormalText"+	> TypeNode k</span+	><br+	 /><span class="Normal NormalText"+	>    = Var               </span+	><span class="Comment"+	>-- type variable</span+	><br+	 /><span class="Normal NormalText"+	>    | Con </span+	><span class="DataType TypeConstructor"+	>String</span+	><span class="Normal NormalText"+	>        </span+	><span class="Comment"+	>-- type constructor</span+	><br+	 /><span class="Normal NormalText"+	>    | App (Id k) (Id k) </span+	><span class="Comment"+	>-- application</span+	><br+	 /><br+	 /><span class="Keyword"+	>type</span+	><span class="Normal NormalText"+	> Types k = Id k -&gt; TypeNode k</span+	><br+	 /><span class="Normal NormalText"+	>    </span+	><span class="Comment"+	>-- many types in one graph</span+	><br+	 /></code+      ></pre+    ><p+    >For example, &ldquo;<code+      >[a]-&gt;a</code+      >&rdquo; is first transformed to &ldquo;<code+      >((-&gt;) ([] a)) a</code+      >&rdquo;.</p+    ></div>+<div class="slide">+<h1 id="e8--types-continued"+    >*E8 / Types (continued)</h1+    ><p+    >&ldquo;<code+      >[a]-&gt;a</code+      >&rdquo; has the graph:</p+    ><p+    ><img src="type.png" alt="type"+       /></p+    ></div>+<div class="slide">+<h1 id="e8--type-equations"+    >*E8 / Type Equations</h1+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Keyword"+	>type</span+	><span class="Normal NormalText"+	> TEq k = (Id k, Id k)</span+	><br+	 /></code+      ></pre+    ></div>+<div class="slide">+<h1 id="e8--instruction"+    >*E8 / Instruction</h1+    ><p+    >Define a function</p+    ><pre class="sourceCode haskell"+    ><code+      ><span class="Function FunctionDefinition"+	>solveEqs ::</span+	><br+	 /><span class="Normal NormalText"+	>    I i =&gt; </span+	><br+	 /><span class="Normal NormalText"+	>    Link i k -&gt;     </span+	><span class="Comment"+	>-- fully separated map    </span+	><br+	 /><span class="Normal NormalText"+	>    Types k -&gt;      </span+	><span class="Comment"+	>-- typing environment</span+	><br+	 /><span class="Normal NormalText"+	>    [TEq k] -&gt;      </span+	><span class="Comment"+	>-- type equations</span+	><br+	 /><span class="Normal NormalText"+	>        ( [TEq k]   </span+	><span class="Comment"+	>-- failed equations</span+	><br+	 /><span class="Normal NormalText"+	>        , Link i k) </span+	><span class="Comment"+	>-- unifications</span+	><br+	 /></code+      ></pre+    ><p+    >The definition is just 13 rows..</p+    ></div>+</div>+</body+  ></html+>+

@@ -0,0 +1,361 @@+% 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++`GHC` and `cabal-install` are needed.++1. Run the following commands in a terminal:++~~~~~~~~~~~~ {.bash}+cabal update+cabal install linear-maps -fcheck+firefox `linear-maps-exercises`+~~~~~~~~~~~~++2. Open an editor and save an empty file `Maps.hs` (do not quit).+3. 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](http://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](graph.png)++# Instructions+++Define a function with the following type signature:++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+*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](graph.png)+++# Instructions++Define a postorder walk:++~~~~~~~~ {.haskell}+postOrderWalk :: I i => ChildrenFun k -> Set i k -> [Id k] -> [Id k]+~~~~~~~~++Use the following data structure inside in a "task list":++~~~~~~~~ {.haskell}+data Task a = Return a | Visit a+~~~~~~~~++Use the same primitives as in `depthFirstWalk`.+Test your function in the interpreter:++~~~~~~~~ {.haskell}+*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:++~~~~~~~~ {.haskell}+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](graph.png)++# Instructions++Define the function:++~~~~~~~~ {.haskell}+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. ...++~~~~~~~~ {.haskell}+*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.++~~~~~~~~ {.haskell}+revMapWalk :: I i => Children 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](graph.png)++# Instructions++Define the function:++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+*Main> testSCC scc "A"+["D","E","B","HG","CFA"]+~~~~~~~~+++# -E5: `replaceLast`++Define a function which replaces the last element of a list.++~~~~~~~~ {.haskell}+replaceLast :: [a] -> a -> [a]+~~~~~~~~++Test cases:++~~~~~~~~ {.haskell}+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.++~~~~~~~~ {.haskell}+replaceAndShiftOne :: Int -> [a] -> a -> [a]+~~~~~~~~++Test cases:++~~~~~~~~ {.haskell}+replaceAndShiftOne 0 "abcd" 'e' == "eacd"+replaceAndShiftOne 1 "abcd" 'e' == "aebd"+replaceAndShiftOne 2 "abcd" 'e' == "abec"+~~~~~~~~++# *E7: Pointer Reversal Walk++Define the pointer reversal algorithm.++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+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:++~~~~~~~~ {.haskell}+*Main> testPrWalk prWalk "A"+"ABDECFGH"+~~~~~~~~+++# *E8: Linear Time Type Inference++Begin a new file with the rows:++~~~~~~~~ {.haskell}+import Data.LinkMap++type Link i k = LinkMap i k ()+~~~~~~~~++`Link` is a disjoint set data structure.  +We will use the following primitives:++~~~~~~~~ {.haskell}+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++~~~~~~~~ {.haskell}+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](type.png)+++# *E8 / Type Equations++~~~~~~~~ {.haskell}+type TEq k = (Id k, Id k)+~~~~~~~~+++# *E8 / Instruction++Define a function++~~~~~~~~ {.haskell}+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..+

@@ -6,7 +6,7 @@     ><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"      /><meta name="generator" content="pandoc"      /><meta name="author" content="P&#233;ter Divi&#225;nszky"-     /><meta name="date" content="CEFP 2009, Komarno"+     /><meta name="date" content="CEFP, Budapest &amp; Kom&#225;rno, 25-30 May 2009"      /><style type="text/css"     > table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode, table.sourceCode pre @@ -301,8 +301,8 @@ <div id="currentSlide"></div> <div id="header"></div> <div id="footer">-<h1 id="cefp-2009-komarno"-    >CEFP 2009, Komarno</h1+<h1 id="cefp-budapest-&amp;-kom&#225;rno-25-30-may-2009"+    >CEFP, Budapest &amp; Komárno, 25-30 May 2009</h1     ><h2 id="implementing-pointer-algorithms-in-haskell-"     >Implementing Pointer Algorithms in Haskell </h2     ></div>@@ -314,10 +314,22 @@     >Implementing Pointer Algorithms in Haskell </h1     ><h3 id="p&#233;ter-divi&#225;nszky"     >Péter Diviánszky</h3-    ><h4 id="cefp-2009-komarno-1"-    >CEFP 2009, Komarno</h4+    ><h4 id="cefp-budapest-&amp;-kom&#225;rno-25-30-may-2009-1"+    >CEFP, Budapest &amp; Komárno, 25-30 May 2009</h4     ></div> <div class="slide">+<h1 id="section"+    ></h1+    ><p+    >The code and the slides can be found as<br+       /><code+      >linear-maps</code+      > on<br+       /><a href="http://hackage.haskell.org/packages/archive/pkg-list.html"+      >http://hackage.haskell.org</a+      >.</p+    ></div>+<div class="slide"> <h1 id="pointers"     >Pointers</h1     ><ul@@ -2103,12 +2115,6 @@     >Thanks</h1     ><p     >Thanks for your attention!</p-    ><p-    >The code can be found as <code-      >linear-maps</code-      > on <a href="http://hackage.haskell.org/packages/archive/pkg-list.html"-      >HackageDB</a-      >.</p     ></div> </div> </body

@@ -1,8 +1,14 @@ % Implementing Pointer Algorithms in Haskell  % Péter Diviánszky-% CEFP 2009, Komarno+% CEFP, Budapest & Komárno, 25-30 May 2009 +# +The code and the slides can be found as  +`linear-maps` on  +[http://hackage.haskell.org](http://hackage.haskell.org/packages/archive/pkg-list.html).++ # Pointers  -   Pointers are well known.@@ -578,6 +584,5 @@  Thanks for your attention! -The code can be found as `linear-maps` on [HackageDB](http://hackage.haskell.org/packages/archive/pkg-list.html).  

@@ -0,0 +1,6 @@+++import Paths_linear_maps++main = getDataFileName "Exercises.html" >>= putStrLn +

@@ -0,0 +1,6 @@+++import Paths_linear_maps++main = getDataFileName "Intro.html" >>= putStrLn+

@@ -0,0 +1,11 @@++Exercises.html: Exercises.pandoc graph.png type.png+	pandoc -t s5 -S -C header.html $< >$@++Intro.html: Intro.pandoc+	pandoc -t s5 -S -C header.html $< >$@++graph.png type.png: %.png: %.dot+	dot -Tpng -Granksep=0.3 -o $@ $<++

@@ -0,0 +1,92 @@+import Data.IdMap++import Data.Graph.IdMap.Tests++type Children k = Id k -> [Id k]++depthFirstWalk :: I i => Children k -> Set i k -> [Id k] -> [Id k]+depthFirstWalk children _s [] = []+depthFirstWalk children s (h: t)+    | h `member` s = depthFirstWalk children s t+    | otherwise = h : depthFirstWalk children (setInsert h s) (children h ++ t)+++data Task a = Return a | Visit a++postOrderWalk :: I i => Children k -> Set i k -> [Id k] -> [Id k]+postOrderWalk children s = collect s . map Visit where++    collect _s [] = []+    collect s (Return h: t) = h: collect s t+    collect s (Visit h: t)+        | h `member` s = collect s t+        | otherwise = collect (setInsert h s) $ map Visit (children h) ++ Return h: t+++revPostOrderWalk :: I i => Children k -> Set i k -> [Id k] -> (Set i k, [Id k])+revPostOrderWalk children s = collect s [] . map Visit where++    collect s acc [] = (s, acc)+    collect s acc (Return h: t) = collect s (h: acc) t+    collect s acc (Visit h: t)+        | h `member` s = collect s acc t+        | otherwise = collect (setInsert h s) acc $ map Visit (children h) ++ Return h: t+++mapWalk :: I i => Children k -> Set i k -> [Id k] -> [[Id k]]+mapWalk children = f+ where+    f _s [] = []+    f s (h:t) = c : f s' t+        where (s', c) = collect s [] [h]++    -- collect :: Set a -> [a] -> [a] -> (Set a, [a])+    collect s acc [] = (s, acc)+    collect s acc (h:t)+        | h `member` s = collect s acc t+        | otherwise = collect (setInsert h s) (h: acc) (children h ++ t)++revMapWalk :: I i => Children k -> Set i k -> [Id k] -> [[Id k]]+revMapWalk children = f []+ where+    f acc s [] = acc+    f acc s (h:t) = f (c: acc) s' t+        where (s', c) = collect s [] [h]++    -- collect :: Set a -> [a] -> [a] -> (Set a, [a])+    collect s acc [] = (s, acc)+    collect s acc (h:t)+        | not (h `member` s) = collect s acc t+        | otherwise = collect (delete h s) (h: acc) (children h ++ t)++scc :: I i => Children k -> Children k -> Set i k -> [Id k] -> [[Id k]]+scc children revChildren s+    = filter (not . null) . uncurry (revMapWalk revChildren) . revPostOrderWalk children s+++----------------++prWalk :: (I i, I j) => Map i k [Id k] -> Map j k Int -> Id k -> [Id k]+prWalk m0 n t = follow m0 n t t where++    follow m n x t = case lookUp t n of+        Nothing    -> t: case lookUp t m of+            Just (l:r)  -> follow (insert t (x:r) m) (insert t 0 n) t l+            _           -> back m (insert t 0 n) t x+        _  -> back m n t x        -- the node or leaf is already visited++    back m n x t | x==t = unsafeEquivalent m0 m `seq` []+    back m n x t = case m ! t of+        l  -> case lookUp t n of+            Just i | i + 1 == length l -> back   (insert t (replaceLast l x) m) (insert t (i+1) n) t (last l)+            Just i    -> follow (insert t (replaceAndShiftOne i l x) m) (insert t (i+1) n) t (l !! (i+1))++replaceLast :: [a] -> a -> [a]+replaceLast [x] y = [y]+replaceLast (x:xs) y = x: replaceLast xs y++replaceAndShiftOne :: Int -> [a] -> a -> [a]+replaceAndShiftOne 0 (c:_:cs) x = (x:c:cs)+replaceAndShiftOne n (c:cs) x = c: replaceAndShiftOne (n-1) cs x++

@@ -0,0 +1,18 @@+  --+-- | Integrity test of the @linear-maps@ package.++module Test.IdMap where++import qualified Data.LinkMap.Tests+import qualified Data.Sequence.IdMap.Tests++-- | Runs all unit tests found in the @linear-maps@ package.++tests :: IO ()+tests = do+    putStrLn "------ Data.Sequence.IdMap.Tests"+    Data.Sequence.IdMap.Tests.tests+    putStrLn "------ Data.LinkMap.Tests"+    Data.LinkMap.Tests.tests+    return ()+

@@ -0,0 +1,44 @@+import Data.LinkMap++type Link i k = LinkMap i k ()+++type TEq k = (Id k, Id k)++data TypeNode k+	= TyApp (Id k) (Id k)+	| TyVar+	| TyCon String+		deriving Eq+++type Type k = Id k -> TypeNode k++solveEqs+	:: I i => Link i k+	-> Type k+	-> [TEq k]+	-> ([TEq k], Link i k)	-- (faild unifications, )+++solveEqs lm f eqs = foldl solveEq ([], lm) eqs where++	solveEq (skipped, lm) (x, y) +		| same lm x y	= (skipped, lm)+		| otherwise	= case (f $ follow lm x, f $ follow lm y) of++			(TyVar, _)+				-> (skipped, link x y lm)++			(_, TyVar)+				-> (skipped, link y x lm)++			(TyApp a b, TyApp c d)+				-> solveEq (solveEq (skipped, link x y lm) (a, c)) (b, d)++			(TyCon a, TyCon b)	| a == b+				-> (skipped, link x y lm)++			_	-> ((x, y): skipped, lm)++

@@ -0,0 +1,18 @@+digraph G {+    Node [shape = circle, style = filled, fillcolor = lightgray]+    A [fillcolor = black, fontcolor = white]+    A -> B [label = "1."]+    A -> C [label = "2."]+    B -> D [label = "1."]+    B -> E [label = "2."]+    C -> F [label = "1."]+    C -> G [label = "2."]+    F -> A+    G -> H+    H -> G+    Node [fillcolor = white]+    I -> H+    J -> K+}++

binary file changed (absent → 30968 bytes)

@@ -0,0 +1,18 @@+digraph G {+    Node [shape = circle, style = filled, fillcolor = lightgray]+    A [fillcolor = black, fontcolor = white]+    A -> B [label = "1.", d]+    A -> C [label = "2."]+    B -> D [label = "1."]+    B -> E [label = "2."]+    C -> F [label = "1."]+    C -> G [label = "2."]+    F -> A+    G -> H+    H -> G+    Node [fillcolor = white]+    I -> H+    J -> K+}++

@@ -1,5 +1,5 @@ Name:           linear-maps-Version:        0.5+Version:        0.6 Synopsis:       Finite maps for linear use Description:         Finite maps for linear use. @@ -33,7 +33,16 @@ Build-Type:     Simple Extra-Source-Files:      Intro.pandoc,-    Intro.html+    Exercises.pandoc,+    Solutions.hs,+    TypeInf.hs,+    *.dot,+    Makefile,+    runtests+Data-Files:+    Intro.html,+    *.png,+    Exercises.html  Flag check     Description:    Check linear use@@ -43,6 +52,12 @@     Description:    Pure functional implementation     Default:        False +Executable linear-maps-introduction+    Main-Is: LinearMapsIntroduction.hs++Executable linear-maps-exercises+    Main-Is: LinearMapsExercises.hs+ Library     GHC-Options: -Wall -fwarn-tabs -fno-warn-incomplete-patterns  -fcontext-stack=33 @@ -60,15 +75,16 @@     -- applications / uses cases         Data.Sequence.IdMap,         Data.Sequence.IdMap.Tests,---        Data.Sequence.IdMap.Profile,-        Data.Sequence.IdMap2---        Data.Sequence.Profile,---        Data.IdSequence,---        Data.List.IdMap,---        Data.Graph.IdMap,---        Data.LinkMap,---        Data.LinkMap.Tests,---        Test.IdMap+        Data.Sequence.IdMap.Profile,+        Data.Sequence.IdMap2,+        Data.Sequence.Profile,+        Data.IdSequence,+        Data.List.IdMap,+        Data.Graph.IdMap,+        Data.Graph.IdMap.Tests,+        Data.LinkMap,+        Data.LinkMap.Tests+        Test.IdMap     --	Tests.PointerReversal,     --	Tests.RandomGraph 

@@ -0,0 +1,3 @@+#!/bin/sh+ghc -i -e Test.IdMap.tests+

@@ -0,0 +1,14 @@+digraph G {+    f [label = "Con \"->\""]+    l [label = "Con \"[]\""]+    a [label = "Var"]+    Node [label = "App"]+    a1 -> f [label = "1."]+    a1 -> a2 [label = "2."]+    a2 -> a3 [label = "1."]+    a2 -> a [label = "2."]+    a3 -> l [label = "1."]+    a3 -> a [label = "2."]+}++

binary file changed (absent → 26934 bytes)