linear-maps (empty) → 0.5
raw patch · 19 files changed
+4152/−0 lines, 19 filesdep +HUnitdep +basedep +containerssetup-changed
Dependencies added: HUnit, base, containers
Files
- Control/Functor.hs +17/−0
- Data/Array/Simple.hs +56/−0
- Data/Control/Kvantum.hs +43/−0
- Data/Control/Kvantum/Void.hs +40/−0
- Data/IdMap.hs +45/−0
- Data/IdMap/Core.hs +19/−0
- Data/IdMap/Core/Fast.hs +385/−0
- Data/IdMap/Core/Pure.hs +194/−0
- Data/IdMap/Static.hs +81/−0
- Data/Sequence/IdMap.hs +136/−0
- Data/Sequence/IdMap/Tests.hs +24/−0
- Data/Sequence/IdMap2.hs +120/−0
- Data/Subtyping.hs +55/−0
- Data/TypeInt.hs +93/−0
- Intro.html +2117/−0
- Intro.pandoc +583/−0
- LICENSE +29/−0
- Setup.hs +2/−0
- linear-maps.cabal +113/−0
+ Control/Functor.hs view
@@ -0,0 +1,17 @@+{-# LANGUAGE KindSignatures #-} +-----------------------------------------------------------------------------+-- | @Functor2@ and @Functor3@ type classes+-----------------------------------------------------------------------------+module Control.Functor (+ Functor2(fmap2)+ , Functor3(fmap3)+ ) where+++class Functor2 (f :: * -> * -> *) where+ fmap2 :: (a -> b) -> f a x -> f b x++class Functor3 (f :: * -> * -> * -> *) where+ fmap3 :: (a -> b) -> f a x y -> f b x y++
+ Data/Array/Simple.hs view
@@ -0,0 +1,56 @@+ --+-----------------------------------------------------------------------------+-- | +-- @Int@-indexed, boxed, mutable @IO@-arrays.+--+-- Reference implementation (more portable but slower):+--+-- > type Array a = Data.Array.IO.IOArray Int a+-- > +-- > newArray i a = Data.Array.IO.newArray (0, i) a+-- > +-- > writeArray = Data.Array.IO.writeArray+-- > +-- > readArray = Data.Array.IO.readArray+-----------------------------------------------------------------------------++{-# LANGUAGE MagicHash, UnboxedTuples #-}++module Data.Array.Simple+ ( Array -- instance Eq+ , newArray+ , writeArray+ , readArray+ ) where++import GHC.Base+import GHC.ST+import GHC.IOBase++-- | @(Array a)@ is similar to @('Data.Array.IO.IOArray' 'Int' a)@, but without boundary information.++data Array a = A !(MutableArray# RealWorld a)++instance Eq (Array a) where+ A a == A b = sameMutableArray# a b++-- | @(newArray i a)@ is similar to @('Data.Array.IO.newArray' (0, i) a)@.++newArray :: Int -> a -> IO (Array a)+newArray (I# n#) a + = stToIO $ ST $ \s1# -> case newArray# n# a s1# of+ (# s2#, arr# #) -> (# s2#, A arr# #)++-- | @writeArray@ is similar to 'Data.Array.IO.writeArray', but without boundary check.++writeArray :: Array a -> Int -> a -> IO ()+writeArray (A arr#) (I# n#) a + = stToIO $ ST $ \s1# -> (# writeArray# arr# n# a s1#, () #)++-- | @readArray@ is similar to 'Data.Array.IO.readArray', but without boundary check.++readArray :: Array a -> Int -> IO a+readArray (A arr#) (I# n#) + = stToIO $ ST $ \s1# -> readArray# arr# n# s1#++
+ Data/Control/Kvantum.hs view
@@ -0,0 +1,43 @@+ --+-----------------------------------------------------------------------------+-- | Data control kvantums+-----------------------------------------------------------------------------+module Data.Control.Kvantum + ( K+ , create -- IO K+ , hit -- K -> IO ()+ , kill -- K -> IO ()+ , renew -- K -> IO K+ , join -- K -> K -> IO K+ ) where++import Control.Concurrent.MVar++----------------------------------------------++type K = [MVar ()]+++create :: IO K+create = fmap (:[]) $ newMVar ()++hit :: K -> IO ()+hit = mapM_ f where++ f x = do + y <- readMVar x+ y `seq` return y++kill :: String -> K -> IO ()+kill msg = mapM_ $ flip swapMVar $ error msg++renew :: String -> K -> IO K+renew msg k = do + hit k+ kill msg k+ create++join :: K -> K -> IO K+join k1 k2 = return $ k1 ++ k2++
+ Data/Control/Kvantum/Void.hs view
@@ -0,0 +1,40 @@+{-# LANGUAGE BangPatterns #-}+-----------------------------------------------------------------------------+-- | Data control kvantums (phony implementation)+-----------------------------------------------------------------------------+module Data.Control.Kvantum.Void+ ( K+ , create -- IO K+ , hit -- K -> IO ()+ , kill -- K -> IO ()+ , renew -- K -> IO K+ , join -- K -> K -> IO K+ ) where++----------------------------------------------++data K = K++{-# INLINE create #-} +create :: IO K+create = return K++{-# INLINE hit #-} +hit :: K -> IO ()+hit !_ = return ()++{-# INLINE kill #-} +kill :: String -> K -> IO ()+kill _ !_ = return ()++{-# INLINE renew #-} +renew :: String -> K -> IO K+renew _ !k = return k++{-# INLINE join #-} +join :: K -> K -> IO K+join a b = return (a `seq` b)++++
+ Data/IdMap.hs view
@@ -0,0 +1,45 @@+{-# LANGUAGE NoBangPatterns #-}++ --+-----------------------------------------------------------------------------+-- | Linearly usable maps and sets on identifiers+-----------------------------------------------------------------------------++module Data.IdMap + ( module Data.IdMap.Core++ , inserts+ , (!)++ , setInsert+ , setInserts+ ) where++------------------------------------++import Data.IdMap.Core++import Data.List (foldl')++------------------------------------++infixl 8 ! -- better to be weaker than (~>)++(!) :: I i => Map i k a -> Id k -> a+m ! i = maybe (error "Data.IdMap.!") id (lookUp i m)++inserts :: I i => Map i k a -> [(Id k, a)] -> Map i k a+inserts = foldl' (\m (i,x) -> insert i x m)+++-- | /O(1)/. Insert a new key in the set. If the key is already in the set, the original set is returned.+--+-- After insertion, the original set may not be used.++setInsert :: I i => Id k -> Set i k -> Set i k+setInsert k = insert k ()++setInserts :: I i => Set i k -> [Id k] -> Set i k+setInserts = foldl' (flip setInsert)++
+ Data/IdMap/Core.hs view
@@ -0,0 +1,19 @@+{-# LANGUAGE CPP #-}++{- | +This module reexports either "Data.IdMap.Core.Pure" or "Data.IdMap.Core.Fast" +depending on whether the @pure@ flag was turned on during the installation of the package.+-}++module Data.IdMap.Core+ ( module+#ifdef __PURE__+ Data.IdMap.Core.Pure+#else+ Data.IdMap.Core.Fast+#endif+ ) where++import Data.IdMap.Core.Pure+import Data.IdMap.Core.Fast+
+ Data/IdMap/Core/Fast.hs view
@@ -0,0 +1,385 @@+{-# LANGUAGE CPP, MultiParamTypeClasses, FlexibleInstances, ScopedTypeVariables, RankNTypes, TypeOperators, GADTs, BangPatterns, EmptyDataDecls #-}++module Data.IdMap.Core.Fast+ ( module Data.Subtyping+ , module Data.TypeInt+ , module Control.Functor++ -- * Identifiers+ , Id+ , equalBy++ -- * Finite maps and sets+ , Map+ , Set+ , insert+ , delete+ , lookUp+ , member+ , union++ -- * Unsafe operations+ , unsafeInsert+ , unsafeEquivalent++ -- * Range of sets and maps+ , Sets (PlusSet)+ , Maps (PlusMap)++ -- * Creation of sets, maps and identifiers+ , ICC, runICC+ , ICCS, runICCS++ -- * For internal use+ , Maplike, MaplikeClass+ ) where++------------------------------------++#ifdef __CHECK__+import Data.Control.Kvantum+#else+import Data.Control.Kvantum.Void+#endif++import Data.Array.Simple+import Data.Bits (setBit, clearBit, testBit)+import System.IO.Unsafe (unsafePerformIO)+import GHC.Base (Any)++import Data.Subtyping+import Data.TypeInt+import Control.Functor++import Unsafe.Coerce (unsafeCoerce)++-------------------------------- Interface++-- | Identifiers indexed by @k@. @(Id k)@ can be seen as a set of identifiers. +--+-- The possible identifier indexes form a recursive set. An identifier index is either+--+-- * an uninstantiated type variable (inside invocations of 'runICC' and 'runICCS'), or+--+-- * @(a :|: b)@, where @a@ and @b@ are identifier indexes.++newtype Id k + = Id (Array (Maybe Any))++instance Incl Id where+ left = unsafeCoerce+ right = unsafeCoerce+++-- | Equality check of identifiers.+-- The first map parameter is the witness that the identifiers are sane.+--+-- The first parameter prevents identifiers of type @'Id' (a :|: a)@ which could cause strange runtime behaviour. +-- 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++-- | Family of finite maps from keys @('Id' k)@ to values @a@.+-- For efficiency reasons, use only with concrete type integers:+--+-- > Map I0 k a+-- > Map I1 k a+-- > Map I2 k a+-- > ...++type Map i k a + = Maplike (M i) k a++data M i++newtype Maplike i k a + = Maplike K+++-- | /O(1)/. Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value.+--+-- After insertion, the original map may not be used.++{-# SPECIALIZE insert :: Id k -> a -> Map I0 k a -> Map I0 k a #-}+{-# SPECIALIZE insert :: Id k -> a -> Map I1 k a -> Map I1 k a #-}+{-# SPECIALIZE insert :: Id k -> a -> Map I2 k a -> Map I2 k a #-}+insert :: forall i k a. MaplikeClass i a => Id k -> a -> Maplike i k a -> Maplike i k a+insert !(Id a) x (Maplike k) = unsafePerformIO $ do+ k' <- renew "insert" k+ set (undefined :: i) (Just x) a+ return $ Maplike k'+++-- | /O(1)/. Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.+--+-- After deletion, the original map may not be used.++delete :: forall i k a. MaplikeClass i a => Id k -> Maplike i k a -> Maplike i k a++-- | /O(1)/. Look up the value at a key in the map.++lookUp :: forall i k a. MaplikeClass i a => Id k -> Maplike i k a -> Maybe a+lookUp {-!-}(Id a) (Maplike k) = unsafePerformIO $ do + hit k+ x <- get (undefined :: i) a+ return x+++member :: MaplikeClass i a => Id k -> Maplike i k a -> Bool+member i m = case lookUp i m of+ Just _ -> True+ _ -> False+++unsafeInsert :: forall i k a. MaplikeClass i a => Id k -> a -> Maplike i k a -> ()+unsafeInsert !(Id a) x !_ = unsafePerformIO $ do+ set (undefined :: i) (Just x) a+ return ()+++++-- | /O(0)/. Union of two maps.+--+-- Linearity constraints:+--+-- * After union, the component maps /may/ also be used. +--+-- * After insertion into either components, the union map may not be used.+--+-- * After insertion into the union map, the components may not be used.++infixr 2 `union`++union :: Maplike i k1 a -> Maplike i k2 a -> Maplike i (k1 :|: k2) a++-- | Unsafe equality coercion of maps.+--+-- The two maps are equal, so every link to the first map could be safely replaced by a link to the second map.++unsafeEquivalent :: Maplike i k a -> Maplike i k a -> Maplike i k a+++-- | Family of finite sets of keys @('Id' k)@.+-- For efficiency reasons, use only with concrete type integers:+--+-- > Set I0 k+-- > Set I1 k+-- > Set I2 k+-- > ...++type Set i k + = Maplike (S Zero i) k ()++data S i j++++-- | Helps to store a range of sets numbered from 0 to @i@-1.+-- For example, @(Sets I3 k)@ is similar to @(Set I2 k, Set I1 k, Set I0 k)@.++infixr 2 `PlusSet`++data Sets i k where++ PlusSet :: Set i k -> Sets i k -> Sets (Succ i) k+++-- | Helps to store a range of maps numbered from 1 to @i@.+-- For example, @(Maps1 I3 k)@ is similar to @(forall a . Map I3 k a, forall a . Map I2 k a, forall a . Map I1 k a)@.++infixr 2 `PlusMap`++data Maps i k where++ PlusMap :: (forall a . Map (Succ i) k a) -> Maps i k -> Maps (Succ i) k++-- | Identifier-consuming computation. @i@ is a type-level integer.+-- A computation of type @(ICC i k a)@ +-- gets @i@ maps numbered from 0 to @i@-1, an infinite list of different identifiers, +-- and returns a value of type @a@. ++type ICC i k a+ = Maps i k+ -> (forall b . Map Zero k b)+ -> [Id k] + -> a++-- | Return the value computed by an identifier-consuming computation. +-- @forall k@ ensures that the identifiers indexed by @k@ are inaccessible to the rest of the program. ++runICC :: I i => (forall k . ICC i k a) -> a+++-- | Identifier-consuming computation with sets. @i@ is a type-level integer.+-- A computation of type @(ICCS i k a)@ +-- gets 32 sets numbered from 0 to 31, @i@ maps numbered from 1 to @i@, an infinite list of different identifiers, +-- and returns a value of type @a@. ++type ICCS i k a+ = Maps i k + -> Sets I32 k+ -> [Id k]+ -> a++-- | Return the value computed by an identifier-consuming computation with sets. +-- @forall k@ ensures that the identifiers indexed by @k@ are inaccessible to the rest of the program. ++runICCS :: I i => (forall k . ICCS i k a) -> a+++++newId :: Int -> IO (Id k)+newId n = fmap Id $ newArray (n + 1) Nothing++newIdS :: Int -> IO (Id k)+newIdS n = fmap Id $ do+ a <- newArray (n+1) Nothing+ writeArray a 0 $ unsafeCoerce (0 :: Int)+ return a++---------------------------------------------++---------------------------------------------++class MaplikeClass i x where++ set :: i -> Maybe x -> Array (Maybe Any) -> IO ()++ get :: i -> Array (Maybe Any) -> IO (Maybe x)+++instance I i => MaplikeClass (M i) a where++ {-# SPECIALIZE instance MaplikeClass (M I0) a #-}+ {-# SPECIALIZE instance MaplikeClass (M I1) a #-}+ {-# SPECIALIZE instance MaplikeClass (M I2) a #-}++ set m x a = writeArray a (ind m) $ unsafeCoerce x++ get m a = fmap unsafeCoerce $ readArray a (ind m)+++instance (I i, I j) => MaplikeClass (S j i) () where++ set m (Just _) a = do+ z <- readArray' m a+ writeArray' m a $ z `setBit` indS m++ set m Nothing a = do+ z <- readArray' m a+ writeArray' m a $ z `clearBit` indS m++ get m a = do+ z <- readArray' m a+ return $ if z `testBit` indS m then Just () else Nothing++++delete !(Id a) (Maplike k) = unsafePerformIO $ do+ k' <- renew "delete" k+ set (undefined :: i) (Nothing :: Maybe a) a+ return $ Maplike k'+++-----------++ind :: forall i. I i => M i -> Int+ind _ = num (undefined :: i)++--------++indS :: forall i j. I i => S j i -> Int+indS _ = num (undefined :: i)+++readArray' :: forall i j. I i => S i j -> Array (Maybe Any) -> IO Int+readArray' _ a = fmap unsafeCoerce $ readArray a $ num (undefined :: i)++writeArray' :: forall i j. I i => S i j -> Array (Maybe Any) -> Int -> IO ()+writeArray' _ a i = writeArray a (num (undefined :: i)) $ unsafeCoerce i+ +----------+++++union (Maplike k1) (Maplike k2) = unsafePerformIO $ do+ k <- join k1 k2+ return $ Maplike k+++++instance Functor (Maplike i k) where + fmap _ _ = error "fmap on Map"++instance Functor2 (Maplike i) where + fmap2 _ _ = error "fmap2 on Map"+++unsafeEquivalent !_ b = b+++--------------------------------++runICC = runICC'++runICC' :: forall i a . I i => (forall k . ICC i k a) -> a++runICCS = runICCS'++runICCS' :: forall i a . I i => (forall k . ICCS i k a) -> a++#ifdef __CHECK__+runICC' f = f (maps_ f) (map0_ f) $ unsafeRepeat (newId (num (undefined :: i))) f++runICCS' f = f (maps_ f) (sets_ f) $ unsafeRepeat (newIdS (num (undefined :: i))) f+#else+runICC' f = f maps map0 $ unsafeRepeat (newId (num (undefined :: i))) f++runICCS' f = f maps sets $ unsafeRepeat (newIdS (num (undefined :: i))) f+#endif+++map0 :: Map Zero k a+map0 = Maplike kk++maps :: Maps i k+maps = unsafeCoerce (Maplike kk `PlusMap` maps)++sets :: Sets i k+sets = unsafeCoerce (Maplike kk `PlusSet` sets)++kk :: K+kk = unsafePerformIO create+++map0_ :: x -> Map I0 k a+map0_ a = unsafePerformIO $ do+ k <- create+ return $ unsafeCoerce (do_nothing a `seq` Maplike k)++maps_ :: a -> Maps i k+maps_ a = unsafePerformIO $ do+ k <- create+ return $ unsafeCoerce (Maplike k `PlusMap` maps_ (do_nothing a))++sets_ :: a -> Sets i k+sets_ a = unsafePerformIO $ do+ k <- create+ return $ unsafeCoerce (Maplike k `PlusSet` sets_ (do_nothing a))+++unsafeRepeat :: IO x -> a -> [x]+unsafeRepeat f g = unsafePerformIO $ do+ i <- f+ return (i: unsafeRepeat f (do_nothing g))++{-# NOINLINE do_nothing #-}+do_nothing :: a -> a+do_nothing i = i++
+ Data/IdMap/Core/Pure.hs view
@@ -0,0 +1,194 @@+{-# LANGUAGE ScopedTypeVariables, RankNTypes, TypeOperators, GADTs #-}+{-# OPTIONS_GHC -fcontext-stack=33 #-}+module Data.IdMap.Core.Pure+ ( module Data.Subtyping+ , module Data.TypeInt+ , module Control.Functor++ -- * Identifiers+ , Id+ , equalBy++ -- * Finite maps and sets+ , Map+ , Set+ , insert+ , delete+ , lookUp+ , member+ , union++ , unsafeInsert+ , unsafeEquivalent++ -- * Range of sets and maps+ , Sets (PlusSet)+ , Maps (PlusMap)++ -- * Creation of sets, maps and identifiers+ , ICC, runICC+ , ICCS, runICCS+ ) where++------------------------------------++import qualified Data.Map as M++import Data.Subtyping+import Data.TypeInt+import Control.Functor++-------------------------------- Interface++-- | Identifiers indexed by @k@. @(Id k)@ can be seen as a set of identifiers. +--+-- The possible identifier indexes form a recursive set. An identifier index is either+--+-- * an uninstantiated type variable (inside invocations of 'runICC' and 'runICCS'), or+--+-- * @(a :|: b)@, where @a@ and @b@ are identifier indexes.++newtype Id k + = Id IdCore++data IdCore + = I Integer+ | L IdCore+ | R IdCore+ deriving (Eq, Ord)+++instance Incl Id where++ left (Id k) = Id (L k)+ right (Id k) = Id (R k)+++-- | Equality check of identifiers.+-- 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+++-- | Finite maps from keys @('Id' k)@ to values @a@.+-- The first parameter has a role only in the other implementations.++newtype Map i k a + = Map (M.Map IdCore a)++instance Functor (Map i k) where + fmap f (Map m) = Map $ fmap f m++-- | Finite sets of @('Id' k)@ values.+-- The first parameter has a role only in the other implementations.++type Set i k + = Map i k ()+++-- | Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value.+insert :: Id k -> a -> Map i k a -> Map i k a+insert (Id k) a (Map m) = Map $ M.insert k a m++-- | Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.+delete :: Id k -> Map i k a -> Map i k a+delete (Id k) (Map m) = Map $ M.delete k m++-- | Look up the value at a key in the map.+lookUp :: Id k -> Map i k a -> Maybe a+lookUp (Id k) (Map m) = M.lookup k m++member :: Id k -> Map i k a -> Bool+member (Id k) (Map m) = M.member k m+++-- It is actually safe in this implementation, but does nothing.++unsafeInsert :: I i => Id k -> a -> Map i k a -> ()+unsafeInsert _ _ _ = ()++++-- | Union of two maps.++infixr 2 `union`++union :: Map i k1 a -> Map i k2 a -> Map i (k1 :|: k2) a+union (Map m) (Map m') = Map $ M.union (M.mapKeys L m) (M.mapKeys R m')++-- | Unsafe equality coercion of maps.+--+-- The two maps are equal, so every link to the first map could be safely replaced by a link to the second map.+-- It is actually safe in this implementation.++unsafeEquivalent :: Map i k a -> Map i k a -> Map i k a+unsafeEquivalent _ m = m++++-- | Helps to store a range of sets numbered from 0 to @i@-1.+-- For example, @(Sets I3 k)@ is similar to @(Set I2 k, Set I1 k, Set I0 k)@.++infixr 2 `PlusSet`++data Sets i k where++ NoSets :: Sets Zero k+ PlusSet :: Set i k -> Sets i k -> Sets (Succ i) k++-- | Helps to store a range of maps numbered from 0 to @i@-1.+-- For example, @(Maps0 I3 k)@ is similar to @(forall a . Map I2 k a, forall a . Map I1 k a, forall a . Map I0 k a)@.++infixr 2 `PlusMap`++data Maps i k where++ NoMaps :: Maps Zero k+ PlusMap :: (forall a . Map (Succ i) k a) -> Maps i k -> Maps (Succ i) k++-- | Identifier-consuming computation. @i@ is a type-level integer.+-- A computation of type @(ICC i k a)@ +-- gets @i@ maps numbered from 0 to @i@-1, an infinite list of different identifiers, +-- and returns a value of type @a@. ++type ICC i k a+ = Maps i k+ -> (forall x . Map I0 k x)+ -> [Id k] + -> a++-- | Return the value computed by an identifier-consuming computation. +-- @forall k@ ensures that the identifiers indexed by @k@ are inaccessible to the rest of the program. ++runICC :: I i => (forall k . ICC i k a) -> a+runICC f = f maps1 (Map M.empty) [Id (I n) | n<-[1..]]+++-- | Identifier-consuming computation with sets. @i@ is a type-level integer.+-- A computation of type @(ICCS i k a)@ +-- gets 32 sets numbered from 0 to 31, @i@ maps numbered from 1 to @i@, an infinite list of different identifiers, +-- and returns a value of type @a@. ++type ICCS i k a+ = Maps i k + -> Sets I32 k+ -> [Id k]+ -> a++-- | Return the value computed by an identifier-consuming computation with sets. +-- @forall k@ ensures that the identifiers indexed by @k@ are inaccessible to the rest of the program. ++runICCS :: I i => (forall k . ICCS i k a) -> a+runICCS f = f maps1 sets [Id (I n) | n<-[1..]]++++maps1 :: forall i k. I i => Maps i (Id k)+maps1 = induction'' NoMaps (\x-> Map M.empty `PlusMap` x)++sets :: forall i k. I i => Sets i (Id k)+sets = induction'' NoSets (\x -> Map M.empty `PlusSet` x)+++
+ Data/IdMap/Static.hs view
@@ -0,0 +1,81 @@+{-# LANGUAGE NoBangPatterns, CPP #-}++module Data.IdMap.Static+ ( module Data.IdMap++ , (:.)((:.))++ , insert, delete, lookUp+ , (!), member, inserts++ , setInsert+ , setInserts+ ) where++------------------------------------++import qualified Data.IdMap as I+import Data.IdMap hiding+ ( insert, delete, lookUp+ , (!), member, inserts++ , setInsert, setInserts+ )++import Data.Maybe+import Data.List (foldl')++------------------------------------++-- | Identifiers with static data.++data k :. x = !(Id k) :. !x++instance Incl2 (:.) where+ left2 (i :. x) = left i :. x+ right2 (i :. x) = right i :. x++instance Functor ((:.) x) where fmap f (i :. x) = i :. (f x)++---------------------------------------------++#ifdef __PURE__+lookUp :: k :. d -> Map i k a -> Maybe a++insert :: k :. d -> a -> Map i k a -> Map i k a++delete :: k :. d -> Map i k a -> Map i k a++member :: k :. d -> Map i k a -> Bool+#else+lookUp :: MaplikeClass i a => k :. d -> Maplike i k a -> Maybe a++insert :: MaplikeClass i a => k :. d -> a -> Maplike i k a -> Maplike i k a++delete :: MaplikeClass i a => k :. d -> Maplike i k a -> Maplike i k a++member :: MaplikeClass i a => k :. d -> Maplike i k a -> Bool+#endif++lookUp (a :. _) m = I.lookUp a m++insert (a :. _) x m = I.insert a x m++delete (a :. _) m = I.delete a m++member i = isJust . lookUp i++infixl 8 ! -- 9 lenne, de ~> miatt 8++(!) :: I i => Map i k a -> k :. d -> a+m ! i = maybe (error "Data.IdMap.!") id (lookUp i m)++inserts :: I i => Map i k a -> [(k :. d, a)] -> Map i k a+inserts = foldl' (\m (i,x) -> insert i x m)++setInsert :: I i => k :. d -> Set i k -> Set i k+setInsert (a :. _) m = I.insert a () m++setInserts :: I i => Set i k -> [k :. d] -> Set i k+setInserts = foldl' (flip setInsert)+
+ Data/Sequence/IdMap.hs view
@@ -0,0 +1,136 @@+{-# LANGUAGE ExistentialQuantification, ScopedTypeVariables #-}+module Data.Sequence.IdMap+ ( Seq+ , empty+ , singleton+ , (<|)+ , (|>)+ , (><)+ , fromList+ , toList+ , viewr+ , ViewR (..)+ , viewl+ , ViewL (..)+-- , size+ ) where++import Data.IdMap hiding (insert)+import qualified Data.IdMap as M++import qualified Data.List as List+import Prelude hiding (last)+++------------------------------------------++data Seq a + = forall k . Seq+ { first :: Id k+ , last :: Id k+ , prev :: {-# UNPACK #-} !(Map I0 k (Id k))+ , next :: {-# UNPACK #-} !(Map I1 k (Id k))+ , value :: {-# UNPACK #-} !(Map I2 k a)+ }+ | Empty++empty :: Seq a+empty = Empty++singleton :: forall a. a -> Seq a+singleton a = runICC f where++ f :: ICC I2 v (Seq a)+ f (v `PlusMap` n `PlusMap` _) p (i:_) = Seq+ { first = i+ , last = i+ , prev = p+ , next = n+ , value = M.insert i a v+ }+{-+ f :: ICC1 I2 v (Seq a)+ f (v `PlusMap1` n `PlusMap1` _) p (i:_) = Seq+ { first = i+ , last = i+ , prev = p+ , next = n+ , value = M.insert i a v+ }+-}+(><) :: Seq a -> Seq a -> Seq a+Empty >< x = x+x >< Empty = x+(Seq f l p n v) >< (Seq f' l' p' n' v') + = Seq+ { first = left f+ , last = right l'+ , prev = M.insert (right f') (left l) $ fmap left p `union` fmap right p'+ , next = M.insert (left l) (right f') $ fmap left n `union` fmap right n'+ , value = v `union` v'+ }+ +(<|) :: a -> Seq a -> Seq a+a <| x = singleton a >< x++(|>) :: Seq a -> a -> Seq a+x |> a = x >< singleton a++++data ViewR a+ = EmptyR+ | Seq a :> !a++viewr :: Seq a -> ViewR a+viewr Empty = EmptyR+viewr (Seq f l p n v) = s' :> vl where ++ vl = v M.! l++ s' = case lookUp l p of+ Nothing -> Empty+ Just pl -> Seq+ { first = f+ , last = pl+ , prev = p+ , next = M.delete pl n+ , value = v+ }+++data ViewL a+ = EmptyL+ | !a :< Seq a++viewl :: Seq a -> ViewL a+viewl Empty = EmptyL+viewl (Seq f l p n v) = vf :< s' where++ vf = v M.! f++ s' = case lookUp f n of+ Nothing -> Empty+ Just nf -> Seq+ { first = nf+ , last = l+ , prev = M.delete nf p+ , next = n+ , value = v+ }+++++----------------------------+++toList :: Seq a -> [a]+toList s = case viewl s of+ EmptyL -> []+ a :< ss -> a: toList ss++fromList :: [a] -> Seq a+fromList l = List.foldl' (|>) empty l++
+ Data/Sequence/IdMap/Tests.hs view
@@ -0,0 +1,24 @@++module Data.Sequence.IdMap.Tests where+++import Data.Sequence.IdMap+import Test.HUnit+import Data.List (foldl')++---------------------------++tests :: IO Counts+tests = runTestTT $ TestList ++ [ 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))+ ]++
+ Data/Sequence/IdMap2.hs view
@@ -0,0 +1,120 @@+module Data.Sequence.IdMap2+ ( Seq+ , empty+ , singleton+ , (<|)+ , (|>)+ , (><)+ , fromList+ , toList+ , viewr+ , ViewR (..)+ , viewl+ , ViewL (..)+-- , size+ ) where++import Data.IdMap.Static hiding (insert)+import qualified Data.IdMap.Static as M++import qualified Data.List as List+import Prelude hiding (last)+++------------------------------------------++data Seq a + = forall k . Seq+ { first :: (k :. a)+ , last :: (k :. a)+ , prev :: {-# UNPACK #-} !(Map I0 k (k :. a))+ , next :: {-# UNPACK #-} !(Map I1 k (k :. a))+ }+ | Empty++empty :: Seq a+empty = Empty++singleton :: forall a. a -> Seq a+singleton a = runICC f where++ f :: ICC I1 v (Seq a)+ f (n `PlusMap` _) p (i:_) = Seq+ { first = i'+ , last = i'+ , prev = p+ , next = n+ }+ where+ i' = i :. a+++(><) :: Seq a -> Seq a -> Seq a+Empty >< x = x+x >< Empty = x+Seq f l p n >< Seq f' l' p' n'+ = Seq+ { first = left2 f+ , last = right2 l'+ , prev = M.insert (right2 f') (left2 l) $ fmap left2 p `union` fmap right2 p'+ , next = M.insert (left2 l) (right2 f') $ fmap left2 n `union` fmap right2 n'+ }+ +(<|) :: a -> Seq a -> Seq a+a <| x = singleton a >< x++(|>) :: Seq a -> a -> Seq a+x |> a = x >< singleton a++++data ViewR a+ = EmptyR+ | Seq a :> a++viewr :: Seq a -> ViewR a+viewr Empty = EmptyR+viewr (Seq f l@(_ :. a) p n) = s' :> a where ++ s' = case lookUp l p of+ Nothing -> Empty+ Just pl -> Seq+ { first = f+ , last = pl+ , prev = p+ , next = M.delete pl n+ }+++data ViewL a+ = EmptyL+ | a :< Seq a++viewl :: Seq a -> ViewL a+viewl Empty = EmptyL+viewl (Seq f@(_ :. a) l p n) = a :< s' where++ s' = case lookUp f n of+ Nothing -> Empty+ Just nf -> Seq+ { first = nf+ , last = l+ , prev = M.delete nf p+ , next = n+ }+++----------------------------+++toList :: Seq a -> [a]+toList s = case viewl s of+ EmptyL -> []+ a :< ss -> a: toList ss++fromList :: [a] -> Seq a+fromList l = List.foldl' (|>) empty l++++
+ Data/Subtyping.hs view
@@ -0,0 +1,55 @@+{-# LANGUAGE CPP, TypeOperators, EmptyDataDecls, RankNTypes #-}+module Data.Subtyping+ ( (:|:)+ , Incl (left, right)+ , Incl2 (left2, right2)+ ) where++import Unsafe.Coerce (unsafeCoerce)+++-- | @(:|:)@ is intended to be used only in data type indexes. +-- @T (a :|: b)@ represents the disjoint union of the sets represented by @T a@ and @T b@.++-- @T (a :|: b)@ is a subtype of both @T a@ and @T b@.+-- There is no subtyping in Haskell, so the 'left' and 'right' functions should be used to express+-- the subtyping coercions.+-- Examples: +-- +-- * If @x :: T a@ then @'left' x :: T (a :|: b)@.+--+-- * If @x :: T b@ then @'right' x :: T (a :|: b)@.+--+-- * If @(x, y) :: (T a, T b)@ then @['left' x, 'right' y] :: [T (a :|: b)]@.+--+-- * If @x :: T a@ then @['left' x, 'right' x] :: [T (a :|: a)]@.+--+-- * If @x :: [T a]@ then @('fmap' 'left' x) :: [T (a :|: b)]@.+--+-- * If @x :: [(T a, 'Int')]@ then @'fmap' ('fmap2' 'left') x :: [(T (a :|: b), 'Int')]@ for all @b@.+--+-- * If @x :: 'Either' (T a) (T b)@ then @'fmap2' ('fmap' 'right' x) :: 'Either' (T (a :|: b)) (T b)@.+++infixr 2 :|:++data a :|: b++class Incl c where++ left :: c a -> c (a :|: b)+ right :: c b -> c (a :|: b)++class Incl2 c where++ left2 :: c a x -> c (a :|: b) x+ right2 :: c b x -> c (a :|: b) x+++#ifndef __PURE__+{-# RULES+"fmap/left" forall x . fmap left x = unsafeCoerce x+"fmap/right" forall x . fmap right x = unsafeCoerce x+ #-}+#endif+
+ Data/TypeInt.hs view
@@ -0,0 +1,93 @@+{-# LANGUAGE ScopedTypeVariables, EmptyDataDecls, RankNTypes #-}+-----------------------------------------------------------------------------+-- | Very simple type-level integers+-----------------------------------------------------------------------------+module Data.TypeInt+ ( + -- * Constructors+ Zero+ , Succ++ -- * Predefined values+ , I0, I1, I2, I3, I4, I5, I6, I7, I8, I9+ , I10, I11, I12, I13, I14, I15, I16, I17, I18, I19+ , I20, I21, I22, I23, I24, I25, I26, I27, I28, I29+ , I30, I31, I32++ -- * Conversion to 'Int'+ , I+ ( num+ , induction+ , induction'+ , induction''+ )+ ) where++------------------------------------++-- | @Zero@ represents 0 at the type level++data Zero++-- | If @a@ represents the natural number @n@ at the type level then @(Succ a)@ represents @(1 + n)@ at the type level.++data Succ a++type I0 = Zero+type I1 = Succ I0+type I2 = Succ I1+type I3 = Succ I2+type I4 = Succ I3+type I5 = Succ I4+type I6 = Succ I5+type I7 = Succ I6+type I8 = Succ I7+type I9 = Succ I8+type I10 = Succ I9+type I11 = Succ I10+type I12 = Succ I11+type I13 = Succ I12+type I14 = Succ I13+type I15 = Succ I14+type I16 = Succ I15+type I17 = Succ I16+type I18 = Succ I17+type I19 = Succ I18+type I20 = Succ I19+type I21 = Succ I20+type I22 = Succ I21+type I23 = Succ I22+type I24 = Succ I23+type I25 = Succ I24+type I26 = Succ I25+type I27 = Succ I26+type I28 = Succ I27+type I29 = Succ I28+type I30 = Succ I29+type I31 = Succ I30+type I32 = Succ I31++-- | Conversion to 'Int' is achieved by the @I@ type class.++class I m where ++ num :: m -> Int+ induction :: m -> a -> (a -> a) -> a+ induction' :: a Zero -> (forall i. a i -> a (Succ i)) -> a m+ induction'' :: a Zero x -> (forall i. a i x -> a (Succ i) x) -> a m x++instance I Zero where ++ num _ = 0+ induction _ x _ = x+ induction' x _ = x+ induction'' x _ = x++instance I a => I (Succ a) where ++ num _ = 1 + num (undefined :: a)+ induction _ x f = f (induction (undefined :: a) x f)+ induction' x f = f (induction' x f)+ induction'' x f = f (induction'' x f)++
+ Intro.html view
@@ -0,0 +1,2117 @@+<!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 </title+ ><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"+ /><meta name="generator" content="pandoc"+ /><meta name="author" content="Péter Diviánszky"+ /><meta name="date" content="CEFP 2009, Komarno"+ /><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();">Ø<\/a>'+'<a accesskey="z" id="prev" href="javascript:go(-1);">«<\/a>'+'<a accesskey="x" id="next" href="javascript:go(1);">»<\/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-2009-komarno"+ >CEFP 2009, Komarno</h1+ ><h2 id="implementing-pointer-algorithms-in-haskell-"+ >Implementing Pointer Algorithms in Haskell </h2+ ></div>+</div>+<div class="presentation">++<div class="slide">+<h1 id="implementing-pointer-algorithms-in-haskell--1"+ >Implementing Pointer Algorithms in Haskell </h1+ ><h3 id="péter-diviánszky"+ >Péter Diviánszky</h3+ ><h4 id="cefp-2009-komarno-1"+ >CEFP 2009, Komarno</h4+ ></div>+<div class="slide">+<h1 id="pointers"+ >Pointers</h1+ ><ul+ ><li+ >Pointers are well known.<ul+ ><li+ >They are called mutable variables in functional languages.</li+ ><li+ >Some algorithms use them heavily.</li+ ></ul+ ></li+ ><li+ >Pointers can be modeled with a global store (heap).<ul+ ><li+ >Efficient implementation on CPU and memory.</li+ ></ul+ ></li+ ><li+ >Hard to find a stateless / modular model for them.<ul+ ><li+ >This would be the functional way.</li+ ></ul+ ></li+ ></ul+ ></div>+<div class="slide">+<h1 id="pointers-in-c"+ >Pointers in C</h1+ ><pre class="sourceCode c"+ ><code+ ><span class="DataType DataType"+ >void</span+ ><span class="Normal NormalText"+ > swap</span+ ><span class="Normal Symbol"+ >(</span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >x</span+ ><span class="Normal Symbol"+ >,</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >y</span+ ><span class="Normal Symbol"+ >)</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >{</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > xv </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >x</span+ ><span class="Normal Symbol"+ >;</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >// read</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > yv </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >y</span+ ><span class="Normal Symbol"+ >;</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >x </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > yv</span+ ><span class="Normal Symbol"+ >;</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >// write</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >*</span+ ><span class="Normal NormalText"+ >y </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > xv</span+ ><span class="Normal Symbol"+ >;</span+ ><br+ /><span class="Normal Symbol"+ >}</span+ ><br+ /><br+ /><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > main</span+ ><span class="Normal Symbol"+ >()</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >{</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > a </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DecVal Decimal"+ >13</span+ ><span class="Normal Symbol"+ >;</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="DataType DataType"+ >int</span+ ><span class="Normal NormalText"+ > b </span+ ><span class="Normal Symbol"+ >=</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DecVal Decimal"+ >14</span+ ><span class="Normal Symbol"+ >;</span+ ><br+ /><span class="Normal NormalText"+ > swap</span+ ><span class="Normal Symbol"+ >(&</span+ ><span class="Normal NormalText"+ >a</span+ ><span class="Normal Symbol"+ >,</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Symbol"+ >&</span+ ><span class="Normal NormalText"+ >b</span+ ><span class="Normal Symbol"+ >);</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >// references</span+ ><br+ /><span class="Normal NormalText"+ > printf</span+ ><span class="Normal Symbol"+ >(</span+ ><span class="String"+ >"%d, %d"</span+ ><span class="Normal Symbol"+ >,</span+ ><span class="Normal NormalText"+ > a</span+ ><span class="Normal Symbol"+ >,</span+ ><span class="Normal NormalText"+ > b</span+ ><span class="Normal Symbol"+ >);</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Keyword"+ >return</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DecVal Decimal"+ >0</span+ ><span class="Normal Symbol"+ >;</span+ ><br+ /><span class="Normal Symbol"+ >}</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="pointers-in-ocaml"+ >Pointers in OCAML</h1+ ><pre class="sourceCode ocaml"+ ><code+ ><span class="Keyword"+ >let</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >swap</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >x</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >y</span+ ><span class="Normal NormalText"+ > =</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Keyword"+ >let</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >vx</span+ ><span class="Normal NormalText"+ > = !</span+ ><span class="Normal Identifier"+ >x</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >(* read *)</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Keyword"+ >and</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >vy</span+ ><span class="Normal NormalText"+ > = !</span+ ><span class="Normal Identifier"+ >y</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Keyword"+ >in</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >x</span+ ><span class="Normal NormalText"+ > := </span+ ><span class="Normal Identifier"+ >vy</span+ ><span class="Normal NormalText"+ >; </span+ ><span class="Comment"+ >(* write *)</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >y</span+ ><span class="Normal NormalText"+ > := </span+ ><span class="Normal Identifier"+ >vx</span+ ><span class="Normal NormalText"+ >;;</span+ ><br+ /><br+ /><span class="Keyword"+ >let</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > = </span+ ><span class="DataType CoreDataType"+ >ref</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DecVal Decimal"+ >13</span+ ><span class="Normal NormalText"+ >;; </span+ ><span class="Comment"+ >(* reference *)</span+ ><br+ /><span class="Keyword"+ >let</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >b</span+ ><span class="Normal NormalText"+ > = </span+ ><span class="DataType CoreDataType"+ >ref</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DecVal Decimal"+ >14</span+ ><span class="Normal NormalText"+ >;;</span+ ><br+ /><span class="Normal Identifier"+ >swap</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Normal Identifier"+ >b</span+ ><span class="Normal NormalText"+ >;;</span+ ><br+ /></code+ ></pre+ ><p+ >Primitives:</p+ ><pre class="sourceCode ocaml"+ ><code+ ><span class="DataType CoreDataType"+ >ref</span+ ><span class="Normal NormalText"+ > : '</span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > -> '</span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType CoreDataType"+ >ref</span+ ><br+ /><span class="Normal NormalText"+ >(!) : '</span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType CoreDataType"+ >ref</span+ ><span class="Normal NormalText"+ > -> '</span+ ><span class="Normal Identifier"+ >a</span+ ><br+ /><span class="Normal NormalText"+ >(:=) : '</span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType CoreDataType"+ >ref</span+ ><span class="Normal NormalText"+ > -> </span+ ><span class="Normal Identifier"+ >a</span+ ><span class="Normal NormalText"+ > -> </span+ ><span class="DataType CoreDataType"+ >unit</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="pointers-in-haskell"+ >Pointers in Haskell</h1+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >swap ::</span+ ><span class="Normal NormalText"+ > IORef a -> IORef a -> </span+ ><span class="DataType TypeConstructor"+ >IO</span+ ><span class="Normal NormalText"+ > ()</span+ ><br+ /><span class="Normal NormalText"+ >swap x y = </span+ ><span class="Keyword"+ >do</span+ ><br+ /><span class="Normal NormalText"+ > vx <- readIORef x</span+ ><br+ /><span class="Normal NormalText"+ > vy <- readIORef y</span+ ><br+ /><span class="Normal NormalText"+ > writeIORef x vy</span+ ><br+ /><span class="Normal NormalText"+ > writeIORef y vx</span+ ><br+ /></code+ ></pre+ ><p+ >Primitives:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >newIORef ::</span+ ><span class="Normal NormalText"+ > a -> </span+ ><span class="DataType TypeConstructor"+ >IO</span+ ><span class="Normal NormalText"+ > (IORef a)</span+ ><br+ /><span class="Function FunctionDefinition"+ >readIORef ::</span+ ><span class="Normal NormalText"+ > IORef a -> </span+ ><span class="DataType TypeConstructor"+ >IO</span+ ><span class="Normal NormalText"+ > a</span+ ><br+ /><span class="Function FunctionDefinition"+ >writeIORef ::</span+ ><span class="Normal NormalText"+ > IORef a -> a -> </span+ ><span class="DataType TypeConstructor"+ >IO</span+ ><span class="Normal NormalText"+ > ()</span+ ><br+ /></code+ ></pre+ ><p+ >Side effects are properly indicated with <code+ >IO</code+ > in types.</p+ ></div>+<div class="slide">+<h1 id="st-pointers-in-haskell"+ >ST Pointers in Haskell</h1+ ><p+ ><code+ >STRef</code+ >s are more safe than <code+ >IORef</code+ >s because they need less privileges.</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >swap ::</span+ ><span class="Normal NormalText"+ > STRef s a -> STRef s a -> ST s ()</span+ ><br+ /><span class="Normal NormalText"+ >swap x y = </span+ ><span class="Keyword"+ >do</span+ ><br+ /><span class="Normal NormalText"+ > vx <- readSTRef x</span+ ><br+ /><span class="Normal NormalText"+ > vy <- readSTRef y</span+ ><br+ /><span class="Normal NormalText"+ > writeSTRef x vy</span+ ><br+ /><span class="Normal NormalText"+ > writeSTRef y vx</span+ ><br+ /></code+ ></pre+ ><p+ >Primitives:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >newSTRef ::</span+ ><span class="Normal NormalText"+ > a -> ST s (STRef s a)</span+ ><br+ /><span class="Function FunctionDefinition"+ >readSTRef ::</span+ ><span class="Normal NormalText"+ > STRef s a -> ST s a</span+ ><br+ /><span class="Function FunctionDefinition"+ >writeSTRef ::</span+ ><span class="Normal NormalText"+ > STRef s a -> a -> ST s ()</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="st-pointers-in-haskell-continued"+ >ST Pointers in Haskell (continued)</h1+ ><p+ >Imperative style Fibonacci function:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >fib ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><span class="Normal NormalText"+ > -> ST s </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><br+ /><span class="Normal NormalText"+ >fib n = </span+ ><span class="Keyword"+ >do</span+ ><br+ /><span class="Normal NormalText"+ > a <- newSTRef </span+ ><span class="DecVal Decimal"+ >0</span+ ><br+ /><span class="Normal NormalText"+ > b <- newSTRef </span+ ><span class="DecVal Decimal"+ >1</span+ ><br+ /><br+ /><span class="Normal NormalText"+ > replicateM_ n $ </span+ ><span class="Keyword"+ >do</span+ ><br+ /><span class="Normal NormalText"+ > av <- readSTRef a</span+ ><br+ /><span class="Normal NormalText"+ > bv <- readSTRef b</span+ ><br+ /><span class="Normal NormalText"+ > writeSTRef a bv</span+ ><br+ /><span class="Normal NormalText"+ > writeSTRef b (av + bv)</span+ ><br+ /><br+ /><span class="Normal NormalText"+ > readSTRef a</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="st-pointers-in-haskell-continued-1"+ >ST Pointers in Haskell (continued)</h1+ ><p+ >Note that the return type of the <code+ >ST</code+ > computation does not depend on <code+ >s</code+ >:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >fib ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><span class="Normal NormalText"+ > -> ST s </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><br+ /></code+ ></pre+ ><p+ >In this case the <code+ >ST</code+ > computation can be turned into a pure value:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >runST ::</span+ ><span class="Normal NormalText"+ > (forall s. ST s a) -> a</span+ ><br+ /></code+ ></pre+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >fib' ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><span class="Normal NormalText"+ > -> </span+ ><span class="DataType TypeConstructor"+ >Integer</span+ ><br+ /><span class="Normal NormalText"+ >fib' n = runST (fib n)</span+ ><br+ /></code+ ></pre+ ><p+ >In that way pointers can be used in a pure function.<br+ />Still, we need a strictly scheduled computation inside.</p+ ></div>+<div class="slide">+<h1 id="other-direction-pointers-in-clean"+ >Other Direction: Pointers in Clean</h1+ ><pre class="clean"+ ><code+ >swap :: (Ptr a) (Ptr a) *Heap -> *Heap+swap x y h1 = h5+where+ (vx, h2) = readPtr x h1+ (vy, h3) = readPtr y h2+ h4 = writePtr x vy h3+ h5 = writePtr y vx h4+</code+ ></pre+ ><p+ >Primitives:</p+ ><pre class="clean"+ ><code+ >newPtr :: a *Heap -> (Ptr a, *Heap)+readPtr :: (Ptr a) *Heap -> (a, *Heap)+writePtr :: (Ptr a) a *Heap -> *Heap+</code+ ></pre+ ></div>+<div class="slide">+<h1 id="problems-with-explicit-heap"+ >Problems with Explicit Heap</h1+ ><p+ >The previous pointer interface is</p+ ><ul+ ><li+ >Typed.</li+ ><li+ >Functional.</li+ ></ul+ ><p+ >However, an explicit heap value should be carried through the program which determines the evaluation order overly.<br+ />The result is an imperative program in a functional guise.</p+ ></div>+<div class="slide">+<h1 id="improvement-interchangeable-pointer-reads"+ >Improvement: Interchangeable Pointer Reads</h1+ ><p+ >Reading a pointer does not alter the heap but it have to be done in time:</p+ ><pre class="clean"+ ><code+ >swap :: (Ptr a) (Ptr a) *Heap -> *Heap+swap x y h + #! vx = sreadPtr x h+ vy = sreadPtr y h+ = writePtr y vx (writePtr x vy h)+</code+ ></pre+ ><p+ >New primitive:</p+ ><pre class="clean"+ ><code+ >sreadPtr :: (Ptr a) Heap -> a+</code+ ></pre+ ><p+ >Note that <code+ >Heap</code+ > is a subtype of <code+ >*Heap</code+ >.</p+ ></div>+<div class="slide">+<h1 id="improvement-typed-heaps"+ >Improvement: Typed Heaps</h1+ ><p+ >An <code+ >Int</code+ >-pointer read and a <code+ >Char</code+ >-pointer write may be interchanged safely.<br+ />This is modeled with typed heaps.</p+ ><p+ >Primitives (as used in the Clean compiler sources):</p+ ><pre class="clean"+ ><code+ >newHeap :: .(Heap a)+newPtr :: a *(Heap a) -> (Ptr a, *(Heap a))+readPtr :: (Ptr a) *(Heap a) -> (a, *(Heap a))+sreadPtr :: (Ptr a) (Heap a) -> a+writePtr :: (Ptr a) a *(Heap a) -> *(Heap a)+</code+ ></pre+ ><p+ >Still a problem: Reading a <code+ >Ptr Char</code+ > in a <code+ >Heap Char</code+ > fails if the pointer was constructed in another <code+ >Heap Char</code+ >.</p+ ></div>+<div class="slide">+<h1 id="improvement-use-the-st-pointer-trick"+ >Improvement: Use the ST Pointer Trick</h1+ ><p+ >We distinguish between different <code+ >Heap Char</code+ > values by adding a phantom type variable: <code+ >Heap k Char</code+ >.</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >newPtr ::</span+ ><span class="Normal NormalText"+ > a -> Heap k a -> (Ptr k, Heap k a)</span+ ><br+ /><span class="Function FunctionDefinition"+ >sreadPtr ::</span+ ><span class="Normal NormalText"+ > Ptr k -> Heap k a -> a</span+ ><br+ /><span class="Function FunctionDefinition"+ >writePtr ::</span+ ><span class="Normal NormalText"+ > Ptr k -> a -> Heap k a -> Heap k a</span+ ><br+ /></code+ ></pre+ ><p+ >Note that the interface use <code+ >Ptr k</code+ > instead of <code+ >Ptr k a</code+ > because <code+ >a</code+ > is not needed.</p+ ><p+ >If the result of a heap-consuming computation does not contain the phantom typevar then we get a heap for free:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >runHCC ::</span+ ><span class="Normal NormalText"+ > (forall k. Heap k a -> b) -> b</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="coming-from-another-direction-finite-maps"+ >Coming from Another Direction: Finite Maps</h1+ ><p+ >Finite maps are functions with finite domain.<br+ />Related phrases: dictionary (Python), hash (Perl), association list.</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >empty ::</span+ ><span class="Normal NormalText"+ > Map k a</span+ ><br+ /><span class="Function"+ >lookup</span+ ><span class="Normal NormalText"+ > :: </span+ ><span class="Keyword Class"+ >Ord</span+ ><span class="Normal NormalText"+ > k => k -> Map k a -> </span+ ><span class="DataType TypeConstructor"+ >Maybe</span+ ><span class="Normal NormalText"+ > a</span+ ><br+ /><span class="Function FunctionDefinition"+ >insert ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Keyword Class"+ >Ord</span+ ><span class="Normal NormalText"+ > k => k -> a -> Map k a -> Map k a</span+ ><br+ /><span class="Function FunctionDefinition"+ >delete ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Keyword Class"+ >Ord</span+ ><span class="Normal NormalText"+ > k => k -> Map k a -> Map k a</span+ ><br+ /></code+ ></pre+ ><p+ >We will need an additional function:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >modify ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Keyword Class"+ >Ord</span+ ><span class="Normal NormalText"+ > k => k -> </span+ ><span class="DataType TypeConstructor"+ >Maybe</span+ ><span class="Normal NormalText"+ > a -> Map k a -> Map k a</span+ ><br+ /><span class="Normal NormalText"+ >modify k </span+ ><span class="Keyword DataConstructor"+ >Nothing</span+ ><span class="Normal NormalText"+ > m = delete k m</span+ ><br+ /><span class="Normal NormalText"+ >modify k (</span+ ><span class="Keyword DataConstructor"+ >Just</span+ ><span class="Normal NormalText"+ > a) m = insert k a m</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="finite-maps-vs-heaps"+ >Finite Maps vs Heaps</h1+ ><p+ ><code+ >Heap k (Maybe a)</code+ > ~ <code+ >Map (Id k) a</code+ ></p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Normal NormalText"+ >newtype Id k = Id </span+ ><span class="DataType TypeConstructor"+ >Int</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Keyword"+ >deriving</span+ ><span class="Normal NormalText"+ > (</span+ ><span class="Keyword Class"+ >Eq</span+ ><span class="Normal NormalText"+ >, </span+ ><span class="Keyword Class"+ >Ord</span+ ><span class="Normal NormalText"+ >)</span+ ><br+ /></code+ ></pre+ ><p+ >We allow only <code+ >Maybe</code+ >-typed heaps, so we can use an interface similar to finite maps.</p+ ></div>+<div class="slide">+<h1 id="pointers-with-finite-map-interface"+ >Pointers with Finite Map Interface</h1+ ><p+ ><code+ >Map</code+ > here is the abstract heap (not a finite map):</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function"+ >lookup</span+ ><span class="Normal NormalText"+ > :: Id k -> Map k a -> </span+ ><span class="DataType TypeConstructor"+ >Maybe</span+ ><span class="Normal NormalText"+ > a</span+ ><br+ /><span class="Function FunctionDefinition"+ >insert ::</span+ ><span class="Normal NormalText"+ > Id k -> a -> Map k a -> Map k a</span+ ><br+ /><span class="Function FunctionDefinition"+ >delete ::</span+ ><span class="Normal NormalText"+ > Id k -> Map k a -> Map k a</span+ ><br+ /></code+ ></pre+ ><p+ >Instead of including <code+ >newPtr</code+ >, pointers are created with the map (this decison pays back later):</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >runICC ::</span+ ><span class="Normal NormalText"+ > (forall k. Map k a -> [Id k] -> b) -> b</span+ ><br+ /></code+ ></pre+ ><p+ ><code+ >runICC</code+ > runs an identifier consuming computation, which receives a map (heap) and an infinite list of identifiers (pointers) allowed to be used with that map.</p+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists"+ >Use Case: Doubly Linked Lists</h1+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DList k a</span+ ><br+ /><span class="Normal NormalText"+ > = Empty</span+ ><br+ /><span class="Normal NormalText"+ > | NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >first ::</span+ ><span class="Normal NormalText"+ > Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > :: Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >nodes ::</span+ ><span class="Normal NormalText"+ > Map k (DListNode k a)</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /><br+ /><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DListNode k a =</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >previous ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType TypeConstructor"+ >Maybe</span+ ><span class="Normal NormalText"+ > (Id k)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >next ::</span+ ><span class="Normal NormalText"+ > </span+ ><span class="DataType TypeConstructor"+ >Maybe</span+ ><span class="Normal NormalText"+ > (Id k)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >value ::</span+ ><span class="Normal NormalText"+ > a</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /><br+ /><span class="Normal NormalText"+ >(<|) :: a -> DList k a -> Id k -> DList k a</span+ ><br+ /><span class="Normal NormalText"+ >(|>) :: DList k a -> a -> Id k -> DList k a</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v2"+ >Use Case: Doubly Linked Lists (v2)</h1+ ><p+ >It is a problem that at insertions free <code+ >Id</code+ >s are needed. This new version solves that problem:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DList k a</span+ ><br+ /><span class="Normal NormalText"+ > = Empty</span+ ><br+ /><span class="Normal NormalText"+ > | NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >first ::</span+ ><span class="Normal NormalText"+ > Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > :: Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >nodes ::</span+ ><span class="Normal NormalText"+ > Map k (DListNode k a)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >freeIds ::</span+ ><span class="Normal NormalText"+ > [Id k] </span+ ><span class="Comment"+ >-- stored free Ids</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /><br+ /><span class="Normal NormalText"+ >(<|) :: a -> DList k a -> DList k a</span+ ><br+ /><span class="Normal NormalText"+ >(|>) :: DList k a -> a -> DList k a</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v3"+ >Use Case: Doubly Linked Lists (v3)</h1+ ><p+ >This version simplifies the creation of <code+ >DList</code+ >s:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DList a</span+ ><br+ /><span class="Normal NormalText"+ > = Empty</span+ ><br+ /><span class="Normal NormalText"+ > | forall k . NonEmpty </span+ ><span class="Comment"+ >-- encapsulated heap</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >first ::</span+ ><span class="Normal NormalText"+ > Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > :: Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >nodes ::</span+ ><span class="Normal NormalText"+ > Map k (DListNode k a)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >freeIds ::</span+ ><span class="Normal NormalText"+ > [Id k]</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /><br+ /><span class="Function FunctionDefinition"+ >singleton ::</span+ ><span class="Normal NormalText"+ > a -> DList a</span+ ><br+ /><br+ /><span class="Normal NormalText"+ >(<|) :: a -> DList a -> DList a</span+ ><br+ /><span class="Normal NormalText"+ >(|>) :: DList a -> a -> DList a</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v3-continued"+ >Use Case: Doubly Linked Lists (v3, continued)</h1+ ><p+ >Code for <code+ >singleton</code+ >:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >singleton ::</span+ ><span class="Normal NormalText"+ > a -> DList a</span+ ><br+ /><span class="Normal NormalText"+ >singleton x = runICC $ \emptyMap (firstId: otherIds) -></span+ ><br+ /><span class="Normal NormalText"+ > NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { first = firstId</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > = firstId</span+ ><br+ /><span class="Normal NormalText"+ > , nodes = insert firstId x emptyMap</span+ ><br+ /><span class="Normal NormalText"+ > , freeIds = otherIds</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /></code+ ></pre+ ><p+ >But <code+ >DList</code+ >s can not be joined because if we open two <code+ >NonEmpty</code+ > values, the phantom variables can not be unified by the type system (which is right).</p+ ></div>+<div class="slide">+<h1 id="improvement-identifier-subtyping"+ >Improvement: Identifier Subtyping</h1+ ><p+ >If <code+ >k1</code+ > ≠ <code+ >k2</code+ > then <code+ >Id k1</code+ > can not be used instead of <code+ >Id k2</code+ >. This is right, because this type variables marks "different regions of memory".<br+ />But sometimes memory regions should be joined.</p+ ><p+ ><code+ >Id (k1 :|: k2)</code+ > is the joined set of <code+ >Id k1</code+ > and <code+ >Id k2</code+ >.</p+ ><p+ ><code+ >:|:</code+ > is an infix type constructor with kind <code+ >* -> * -> *</code+ >:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > (a :|: b)</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >-- no constructors</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="identifier-subtyping-continued"+ >Identifier Subtyping (continued)</h1+ ><p+ ><code+ >Id (k1 :|: k2)</code+ > is the joined set of <code+ >Id k1</code+ > and <code+ >Id k2</code+ >.</p+ ><p+ >A value with type <code+ >Id k1</code+ > is acceptable when a value with type <code+ >Id (k1 :|: k2)</code+ > is needed.<br+ />In other words, <code+ >Id k1</code+ > is a subtype of <code+ >Id (k1 :|: k2)</code+ >.<br+ />There is no subtyping in Haskell so we use explicit conversion functions:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >left ::</span+ ><span class="Normal NormalText"+ > Id k1 -> Id (k1 :|: k2)</span+ ><br+ /><span class="Function FunctionDefinition"+ >right ::</span+ ><span class="Normal NormalText"+ > Id k2 -> Id (k1 :|: k2)</span+ ><br+ /></code+ ></pre+ ><p+ >One can join two maps (two heaps or two "memory regions") with <code+ >union</code+ >:</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >union ::</span+ ><span class="Normal NormalText"+ > Map k1 a -> Map k2 a -> Map (k1 :|: k2) a</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v4"+ >Use Case: Doubly Linked Lists (v4)</h1+ ><p+ >A simplification first: the <code+ >freeIds</code+ > field is not needed because any number of free <code+ >Id</code+ >s can be obtained by joining a new "memory region":</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DList a</span+ ><br+ /><span class="Normal NormalText"+ > = Empty</span+ ><br+ /><span class="Normal NormalText"+ > | forall k . NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >first ::</span+ ><span class="Normal NormalText"+ > Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > :: Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >nodes ::</span+ ><span class="Normal NormalText"+ > Map k (DListNode k a)</span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Comment"+ >-- , freeIds :: [Id k] -- not needed</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v4-continued"+ >Use Case: Doubly Linked Lists (v4, continued)</h1+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Normal NormalText"+ >(><) :: DList a -> DList a -> DList a</span+ ><br+ /><span class="Normal NormalText"+ >Empty >< y = y</span+ ><br+ /><span class="Normal NormalText"+ >x >< Empty = x</span+ ><br+ /><span class="Normal NormalText"+ >x >< y = NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { first = left (first x)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > = right (</span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > y)</span+ ><br+ /><span class="Normal NormalText"+ > , nodes = ... (</span+ ><span class="Function"+ >fmap</span+ ><span class="Normal NormalText"+ > left (nodes x) </span+ ><br+ /><span class="Normal NormalText"+ > </span+ ><span class="Others InfixOperator"+ >`union`</span+ ><span class="Normal NormalText"+ > </span+ ><span class="Function"+ >fmap</span+ ><span class="Normal NormalText"+ > right (nodes y))</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /></code+ ></pre+ ><p+ ><code+ >...</code+ > contains code which redirects<br+ /><code+ >next (last x)</code+ > to <code+ >first y</code+ > and<br+ /><code+ >previous (first y)</code+ > to <code+ >(last x)</code+ >.</p+ ></div>+<div class="slide">+<h1 id="improvement-split-maps"+ >Improvement: Split Maps</h1+ ><p+ >Redirecting <code+ >next (last x)</code+ > to <code+ >first y</code+ > is complicated because a <code+ >DListNode</code+ > record have to be updated.</p+ ><p+ >This could be improved if three different maps were used for <code+ >previous</code+ >, <code+ >next</code+ > and <code+ >value</code+ > values. But a pointer can only point to one object.</p+ ><p+ >Solution: Maps are tagged with type-level integers. A pointer can be a key in several maps with different integers.</p+ ><p+ >We will use <code+ >(Map I0 k a, Map I1 k b, Map I2 k c)</code+ ><br+ />instead of <code+ >Map k (a, b, c)</code+ >.</p+ ></div>+<div class="slide">+<h1 id="improvement-split-maps-continued"+ >Improvement: Split Maps (continued)</h1+ ><p+ >To understand the implementation:<br+ />The finite map <code+ >Map i k a</code+ > represents a scattered memory fragment with the following properties:</p+ ><ul+ ><li+ >The memory fragment contains an <code+ >a</code+ >-typed values.</li+ ><li+ >The pieces of the memory fragment are some record's <code+ >i</code+ >th field.<ul+ ><li+ ><code+ >i</code+ > is a type-level integer (<code+ >I0</code+ >, <code+ >I1</code+ >, <code+ >I2</code+ >, ... in the implementation).</li+ ><li+ >The records need not have the same type.</li+ ></ul+ ></li+ ><li+ ><code+ >k</code+ > is an additional tag (for example, to separate two doubly linked lists)</li+ ></ul+ ></div>+<div class="slide">+<h1 id="use-case-doubly-linked-lists-v5"+ >Use Case: Doubly Linked Lists (v5)</h1+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Keyword"+ >data</span+ ><span class="Normal NormalText"+ > DList a</span+ ><br+ /><span class="Normal NormalText"+ > = Empty</span+ ><br+ /><span class="Normal NormalText"+ > | forall k . NonEmpty</span+ ><br+ /><span class="Normal NormalText"+ > { </span+ ><span class="Function FunctionDefinition"+ >first ::</span+ ><span class="Normal NormalText"+ > Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function"+ >last</span+ ><span class="Normal NormalText"+ > :: Id k</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >previous ::</span+ ><span class="Normal NormalText"+ > Map I0 k (Id k)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >next ::</span+ ><span class="Normal NormalText"+ > Map I1 k (Id k)</span+ ><br+ /><span class="Normal NormalText"+ > , </span+ ><span class="Function FunctionDefinition"+ >value ::</span+ ><span class="Normal NormalText"+ > Map I2 k a</span+ ><br+ /><span class="Normal NormalText"+ > }</span+ ><br+ /></code+ ></pre+ ></div>+<div class="slide">+<h1 id="creation-of-split-maps"+ >Creation of Split Maps</h1+ ><p+ >Basic solution: There are a family of functions</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >runICC1 ::</span+ ><span class="Normal NormalText"+ > (forall k. Map I0 k a -> [Id k] -> b) -> b</span+ ><br+ /><span class="Function FunctionDefinition"+ >runICC2 ::</span+ ><span class="Normal NormalText"+ > (forall k. Map I0 k a -> Map I1 k a -> [Id k] -> b) -> b</span+ ><br+ /><span class="Function FunctionDefinition"+ >runICC3 ::</span+ ><span class="Normal NormalText"+ > (forall k. Map I0 k a -> Map I1 k a -> Map I2 k a -> [Id k] -> b) -> b</span+ ><br+ /><span class="Normal NormalText"+ >...</span+ ><br+ /></code+ ></pre+ ><p+ >Instead of that, the current implementation use a variant of the function</p+ ><pre class="sourceCode haskell"+ ><code+ ><span class="Function FunctionDefinition"+ >runICC ::</span+ ><span class="Normal NormalText"+ > (forall k. Maps i k -> [Id k] -> b) -> b</span+ ><br+ /></code+ ></pre+ ><p+ >where <code+ >Maps</code+ > is a GADT which can be unfolded into <code+ >i</code+ > maps.</p+ ></div>+<div class="slide">+<h1 id="conclusion--efficiency"+ >Conclusion / Efficiency</h1+ ><p+ >The implementation is as efficient as if mutable references were used:</p+ ><ul+ ><li+ ><code+ >Map</code+ >s are not present in the generated code (for example, <code+ >NonEmpty</code+ > has two fields).</li+ ><li+ ><code+ >Id</code+ >s are replaced by pointers to records (arrays actually).</li+ ></ul+ ><p+ >TODOs:</p+ ><ul+ ><li+ >The implementation has to be reviewed.</li+ ><li+ >The <code+ >Maybe</code+ >s still cause some performance loss.</li+ ></ul+ ></div>+<div class="slide">+<h1 id="conclusion--safety"+ >Conclusion / Safety</h1+ ><p+ >Guarantees by the type system:</p+ ><ul+ ><li+ >Pointers are typed (by the type of the pointed value).</li+ ><li+ >Pointers can not escape their scope.<ul+ ><li+ >Pointer in "different regions" can not be exchanged by accident.</li+ ></ul+ ></li+ ></ul+ ><p+ >TODOs:</p+ ><ul+ ><li+ >Linear use is checked <em+ >only in runtime</em+ >.<ul+ ><li+ >This is a big disadvantage.</li+ ><li+ >Should be checked statically, which needs at least annotated types and a strictness analyzer.</li+ ></ul+ ></li+ ></ul+ ></div>+<div class="slide">+<h1 id="conclusion--usability"+ >Conclusion / Usability</h1+ ><p+ >Pros:</p+ ><ul+ ><li+ >Highly functional interface (similar to finite maps).<ul+ ><li+ >Less strict evaluation order (more possibility to parallel execution).</li+ ></ul+ ></li+ ><li+ >One can virtually join <code+ >i</code+ >th fields of different records (if the <code+ >i</code+ >th fields has the same type).</li+ ></ul+ ><p+ >Cons:</p+ ><ul+ ><li+ >Linear use should be obeyed.</li+ ><li+ >Creation of maps is a bit uncomfortable (maps has to be carried).</li+ ></ul+ ></div>+<div class="slide">+<h1 id="conclusion--semantics"+ >Conclusion / Semantics</h1+ ><p+ >The library has a simple semantics.</p+ ><p+ >This is demonstrated by a small pure functional implementation of the interface functions.</p+ ></div>+<div class="slide">+<h1 id="further-extensions"+ >Further Extensions</h1+ ><p+ >Sets can be modeled as maps to unit values.</p+ ><ul+ ><li+ >The current implementation is more efficient than that: 32 sets are packed into 1 integer map.</li+ ><li+ >The interface of sets and maps are unified.</li+ ></ul+ ><p+ >Identifiers can refer to static data.<br+ />For example, if a sequence is implemented by a doubly linked map, <code+ >previous</code+ > and <code+ >next</code+ > are mutable but <code+ >value</code+ > is static. So two maps are sufficient.</p+ ></div>+<div class="slide">+<h1 id="related-work"+ >Related Work</h1+ ><ul+ ><li+ ><a href="http://www.haskell.org/haskellwiki/DDC"+ >DDC</a+ >, The Disciplined Disciple Compiler<ul+ ><li+ >An explicitly lazy dialect of Haskell.</li+ ><li+ >Supports destructive update, computational effects, type directed field projections.</li+ ></ul+ ></li+ ><li+ ><a href="http://okmij.org/ftp/Haskell/regions.html"+ >Monadic Regions</a+ ><ul+ ><li+ >A technique for managing resources (memory areas, file handles, database connections).</li+ ></ul+ ></li+ ></ul+ ></div>+<div class="slide">+<h1 id="forthcoming-use-cases"+ >Forthcoming Use Cases</h1+ ><ul+ ><li+ >Graph walks.<ul+ ><li+ >with tagging</li+ ><li+ >with pointer reversal</li+ ></ul+ ></li+ ><li+ >Strongly connected components computation.</li+ ><li+ >Linear time type inference algorithm with pointers.</li+ ></ul+ ></div>+<div class="slide">+<h1 id="thanks"+ >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+ ></html+>+
+ Intro.pandoc view
@@ -0,0 +1,583 @@+% Implementing Pointer Algorithms in Haskell +% Péter Diviánszky+% CEFP 2009, Komarno+++# Pointers++- Pointers are well known.+ - They are called mutable variables in functional languages.+ - Some algorithms use them heavily.++- Pointers can be modeled with a global store (heap).+ - Efficient implementation on CPU and memory.++- Hard to find a stateless / modular model for them.+ - This would be the functional way.+++# Pointers in C++~~~~~~~~~~~~~~~~~ {.c}+void swap(int *x, int *y) {+ int xv = *x; // read+ int yv = *y;+ *x = yv; // write+ *y = xv;+}++int main() {+ int a = 13;+ int b = 14;+ swap(&a, &b); // references+ printf("%d, %d", a, b);+ return 0;+}+~~~~~~~~~~~~~~~~~+++# Pointers in OCAML+++~~~~~~~~~~~~~~~~~ {.ocaml}+let swap x y =+ let vx = !x (* read *)+ and vy = !y in+ x := vy; (* write *)+ y := vx;;++let a = ref 13;; (* reference *)+let b = ref 14;;+swap a b;;+~~~~~~~~~~~~~~~~~++Primitives:++~~~~~~~~~~~~~~~~~ {.ocaml}+ref : 'a -> 'a ref+(!) : 'a ref -> 'a+(:=) : 'a ref -> a -> unit+~~~~~~~~~~~~~~~~~++# Pointers in Haskell++~~~~~~~~~~~~~~~~~ {.haskell}+swap :: IORef a -> IORef a -> IO ()+swap x y = do+ vx <- readIORef x+ vy <- readIORef y+ writeIORef x vy+ writeIORef y vx+~~~~~~~~~~~~~~~~~++Primitives:++~~~~~~~~~~~~~~~~~ {.haskell}+newIORef :: a -> IO (IORef a)+readIORef :: IORef a -> IO a+writeIORef :: IORef a -> a -> IO ()+~~~~~~~~~~~~~~~~~++Side effects are properly indicated with `IO` in types.+++# ST Pointers in Haskell++`STRef`s are more safe than `IORef`s because they need less privileges.++~~~~~~~~~~~~~~~~~ {.haskell}+swap :: STRef s a -> STRef s a -> ST s ()+swap x y = do+ vx <- readSTRef x+ vy <- readSTRef y+ writeSTRef x vy+ writeSTRef y vx+~~~~~~~~~~~~~~~~~++Primitives:++~~~~~~~~~~~~~~~~~ {.haskell}+newSTRef :: a -> ST s (STRef s a)+readSTRef :: STRef s a -> ST s a+writeSTRef :: STRef s a -> a -> ST s ()+~~~~~~~~~~~~~~~~~++# ST Pointers in Haskell (continued)++Imperative style Fibonacci function:++~~~~~~~~~~~~~~~~~ {.haskell}+fib :: Integer -> ST s Integer+fib n = do+ a <- newSTRef 0+ b <- newSTRef 1++ replicateM_ n $ do+ av <- readSTRef a+ bv <- readSTRef b+ writeSTRef a bv+ writeSTRef b (av + bv)++ readSTRef a+~~~~~~~~~~~~~~~~~++# ST Pointers in Haskell (continued)++Note that the return type of the `ST` computation does not depend on `s`:++~~~~~~~~~~~~~~~~~ {.haskell}+fib :: Integer -> ST s Integer+~~~~~~~~~~~~~~~~~++In this case the `ST` computation can be turned into a pure value:++~~~~~~~~~~~~~~~~~ {.haskell}+runST :: (forall s. ST s a) -> a+~~~~~~~~~~~~~~~~~++~~~~~~~~~~~~~~~~~ {.haskell}+fib' :: Integer -> Integer+fib' n = runST (fib n)+~~~~~~~~~~~~~~~~~++In that way pointers can be used in a pure function. +Still, we need a strictly scheduled computation inside.++# Other Direction: Pointers in Clean ++~~~~~~~~~~~~~~~~~ {.clean}+swap :: (Ptr a) (Ptr a) *Heap -> *Heap+swap x y h1 = h5+where+ (vx, h2) = readPtr x h1+ (vy, h3) = readPtr y h2+ h4 = writePtr x vy h3+ h5 = writePtr y vx h4+~~~~~~~~~~~~~~~~~++Primitives:++~~~~~~~~~~~~~~~~~ {.clean}+newPtr :: a *Heap -> (Ptr a, *Heap)+readPtr :: (Ptr a) *Heap -> (a, *Heap)+writePtr :: (Ptr a) a *Heap -> *Heap+~~~~~~~~~~~~~~~~~++++# Problems with Explicit Heap++The previous pointer interface is++- Typed.+- Functional.++However, an explicit heap value should be carried through the program+which determines the evaluation order overly. +The result is an imperative program in a functional guise.+++# Improvement: Interchangeable Pointer Reads++Reading a pointer does not alter the heap but it have to be done in time:++~~~~~~~~~~~~~~~~~ {.clean}+swap :: (Ptr a) (Ptr a) *Heap -> *Heap+swap x y h + #! vx = sreadPtr x h+ vy = sreadPtr y h+ = writePtr y vx (writePtr x vy h)+~~~~~~~~~~~~~~~~~++New primitive:++~~~~~~~~~~~~~~~~~ {.clean}+sreadPtr :: (Ptr a) Heap -> a+~~~~~~~~~~~~~~~~~++Note that `Heap` is a subtype of `*Heap`.+++# Improvement: Typed Heaps++An `Int`-pointer read and a `Char`-pointer write may be interchanged safely. +This is modeled with typed heaps.++Primitives (as used in the Clean compiler sources):++~~~~~~~~~~~~~~~~~ {.clean}+newHeap :: .(Heap a)+newPtr :: a *(Heap a) -> (Ptr a, *(Heap a))+readPtr :: (Ptr a) *(Heap a) -> (a, *(Heap a))+sreadPtr :: (Ptr a) (Heap a) -> a+writePtr :: (Ptr a) a *(Heap a) -> *(Heap a)+~~~~~~~~~~~~~~~~~++Still a problem: Reading a `Ptr Char` in a `Heap Char` fails if the pointer was constructed in another `Heap Char`.++# Improvement: Use the ST Pointer Trick++We distinguish between different `Heap Char` values by adding a phantom type variable: `Heap k Char`.++~~~~~~~~~~~~~~~~~ {.haskell}+newPtr :: a -> Heap k a -> (Ptr k, Heap k a)+sreadPtr :: Ptr k -> Heap k a -> a+writePtr :: Ptr k -> a -> Heap k a -> Heap k a+~~~~~~~~~~~~~~~~~++Note that the interface use `Ptr k` instead of `Ptr k a` because `a` is not needed.++If the result of a heap-consuming computation does not contain the phantom typevar then we get a heap for free:++~~~~~~~~~~~~~~~~~ {.haskell}+runHCC :: (forall k. Heap k a -> b) -> b+~~~~~~~~~~~~~~~~~++++# Coming from Another Direction: Finite Maps++Finite maps are functions with finite domain. +Related phrases: dictionary (Python), hash (Perl), association list.++~~~~~~~~~~~~~~~~~ {.haskell}+empty :: Map k a+lookup :: Ord k => k -> Map k a -> Maybe a+insert :: Ord k => k -> a -> Map k a -> Map k a+delete :: Ord k => k -> Map k a -> Map k a+~~~~~~~~~~~~~~~~~++We will need an additional function:++~~~~~~~~~~~~~~~~~ {.haskell}+modify :: Ord k => k -> Maybe a -> Map k a -> Map k a+modify k Nothing m = delete k m+modify k (Just a) m = insert k a m+~~~~~~~~~~~~~~~~~++++# Finite Maps vs Heaps++`Heap k (Maybe a)` ~ `Map (Id k) a`++~~~~~~~~~~~~~~~~~ {.haskell}+newtype Id k = Id Int deriving (Eq, Ord)+~~~~~~~~~~~~~~~~~++We allow only `Maybe`-typed heaps, so we can use an interface similar to finite maps.++# Pointers with Finite Map Interface++`Map` here is the abstract heap (not a finite map):++~~~~~~~~~~~~~~~~~ {.haskell}+lookup :: Id k -> Map k a -> Maybe a+insert :: Id k -> a -> Map k a -> Map k a+delete :: Id k -> Map k a -> Map k a+~~~~~~~~~~~~~~~~~++Instead of including `newPtr`, pointers are created with the map (this decison pays back later):++~~~~~~~~~~~~~~~~~ {.haskell}+runICC :: (forall k. Map k a -> [Id k] -> b) -> b+~~~~~~~~~~~~~~~~~++`runICC` runs an identifier consuming computation, which receives a map (heap) and an infinite list of identifiers (pointers)+allowed to be used with that map.+++# Use Case: Doubly Linked Lists++~~~~~~~~~~~~~~~~~ {.haskell}+data DList k a+ = Empty+ | NonEmpty+ { first :: Id k+ , last :: Id k+ , nodes :: Map k (DListNode k a)+ }++data DListNode k a =+ { previous :: Maybe (Id k)+ , next :: Maybe (Id k)+ , value :: a+ }++(<|) :: a -> DList k a -> Id k -> DList k a+(|>) :: DList k a -> a -> Id k -> DList k a+~~~~~~~~~~~~~~~~~++# Use Case: Doubly Linked Lists (v2)++It is a problem that at insertions free `Id`s are needed.+This new version solves that problem:++~~~~~~~~~~~~~~~~~ {.haskell}+data DList k a+ = Empty+ | NonEmpty+ { first :: Id k+ , last :: Id k+ , nodes :: Map k (DListNode k a)+ , freeIds :: [Id k] -- stored free Ids+ }++(<|) :: a -> DList k a -> DList k a+(|>) :: DList k a -> a -> DList k a+~~~~~~~~~~~~~~~~~++# Use Case: Doubly Linked Lists (v3)++This version simplifies the creation of `DList`s:++~~~~~~~~~~~~~~~~~ {.haskell}+data DList a+ = Empty+ | forall k . NonEmpty -- encapsulated heap+ { first :: Id k+ , last :: Id k+ , nodes :: Map k (DListNode k a)+ , freeIds :: [Id k]+ }++singleton :: a -> DList a++(<|) :: a -> DList a -> DList a+(|>) :: DList a -> a -> DList a+~~~~~~~~~~~~~~~~~+++# Use Case: Doubly Linked Lists (v3, continued)++Code for `singleton`:++~~~~~~~~~~~~~~~~~ {.haskell}+singleton :: a -> DList a+singleton x = runICC $ \emptyMap (firstId: otherIds) ->+ NonEmpty+ { first = firstId+ , last = firstId+ , nodes = insert firstId x emptyMap+ , freeIds = otherIds+ }+~~~~~~~~~~~~~~~~~++But `DList`s can not be joined because if we open two `NonEmpty` values, the phantom variables can not be unified by the type system (which is right).+++# Improvement: Identifier Subtyping++If `k1` ≠ `k2` then `Id k1` can not be used instead of `Id k2`.+This is right, because this type variables marks "different regions of memory". +But sometimes memory regions should be joined.++`Id (k1 :|: k2)` is the joined set of `Id k1` and `Id k2`.++`:|:` is an infix type constructor with kind `* -> * -> *`:++~~~~~~~~~~~~~~~~~ {.haskell}+data (a :|: b)+ -- no constructors+~~~~~~~~~~~~~~~~~++# Identifier Subtyping (continued)++`Id (k1 :|: k2)` is the joined set of `Id k1` and `Id k2`.++A value with type `Id k1` is acceptable when a value with type `Id (k1 :|: k2)` is needed. +In other words, `Id k1` is a subtype of `Id (k1 :|: k2)`. +There is no subtyping in Haskell so we use explicit conversion functions:++~~~~~~~~~~~~~~~~~ {.haskell}+left :: Id k1 -> Id (k1 :|: k2)+right :: Id k2 -> Id (k1 :|: k2)+~~~~~~~~~~~~~~~~~++One can join two maps (two heaps or two "memory regions") with `union`:++~~~~~~~~~~~~~~~~~ {.haskell}+union :: Map k1 a -> Map k2 a -> Map (k1 :|: k2) a+~~~~~~~~~~~~~~~~~+++# Use Case: Doubly Linked Lists (v4)++A simplification first: the `freeIds` field is not needed because any number of+free `Id`s can be obtained by joining a new "memory region":++~~~~~~~~~~~~~~~~~ {.haskell}+data DList a+ = Empty+ | forall k . NonEmpty+ { first :: Id k+ , last :: Id k+ , nodes :: Map k (DListNode k a)+ -- , freeIds :: [Id k] -- not needed+ }+~~~~~~~~~~~~~~~~~++# Use Case: Doubly Linked Lists (v4, continued)++~~~~~~~~~~~~~~~~~ {.haskell}+(><) :: DList a -> DList a -> DList a+Empty >< y = y+x >< Empty = x+x >< y = NonEmpty+ { first = left (first x)+ , last = right (last y)+ , nodes = ... (fmap left (nodes x) + `union` fmap right (nodes y))+ }+~~~~~~~~~~~~~~~~~++`...` contains code which redirects +`next (last x)` to `first y` and +`previous (first y)` to `(last x)`.++# Improvement: Split Maps++Redirecting `next (last x)` to `first y` is complicated because a `DListNode` record have to be updated.++This could be improved if three different maps were used for `previous`, `next` and `value` values.+But a pointer can only point to one object.++Solution: Maps are tagged with type-level integers. +A pointer can be a key in several maps with different integers.++We will use `(Map I0 k a, Map I1 k b, Map I2 k c)` +instead of `Map k (a, b, c)`. ++# Improvement: Split Maps (continued)++To understand the implementation: +The finite map `Map i k a` represents a scattered memory fragment with the following properties:++- The memory fragment contains an `a`-typed values.+- The pieces of the memory fragment are some record's `i`th field.+ - `i` is a type-level integer (`I0`, `I1`, `I2`, ... in the implementation).+ - The records need not have the same type.+- `k` is an additional tag (for example, to separate two doubly linked lists)+++# Use Case: Doubly Linked Lists (v5)++~~~~~~~~~~~~~~~~~ {.haskell}+data DList a+ = Empty+ | forall k . NonEmpty+ { first :: Id k+ , last :: Id k+ , previous :: Map I0 k (Id k)+ , next :: Map I1 k (Id k)+ , value :: Map I2 k a+ }+~~~~~~~~~~~~~~~~~++# Creation of Split Maps++Basic solution: There are a family of functions++~~~~~~~~~~~~~~~~~ {.haskell}+runICC1 :: (forall k. Map I0 k a -> [Id k] -> b) -> b+runICC2 :: (forall k. Map I0 k a -> Map I1 k a -> [Id k] -> b) -> b+runICC3 :: (forall k. Map I0 k a -> Map I1 k a -> Map I2 k a -> [Id k] -> b) -> b+...+~~~~~~~~~~~~~~~~~++Instead of that, the current implementation use a variant of the function++~~~~~~~~~~~~~~~~~ {.haskell}+runICC :: (forall k. Maps i k -> [Id k] -> b) -> b+~~~~~~~~~~~~~~~~~++where `Maps` is a GADT which can be unfolded into `i` maps.+++# Conclusion / Efficiency ++The implementation is as efficient as if mutable references were used:++- `Map`s are not present in the generated code (for example, `NonEmpty` has two fields). +- `Id`s are replaced by pointers to records (arrays actually).++TODOs:++- The implementation has to be reviewed.+- The `Maybe`s still cause some performance loss.+++# Conclusion / Safety++Guarantees by the type system:++- Pointers are typed (by the type of the pointed value).+- Pointers can not escape their scope.+ - Pointer in "different regions" can not be exchanged by accident.++TODOs:++- Linear use is checked *only in runtime*.+ - This is a big disadvantage.+ - Should be checked statically, which needs at least annotated types and a strictness analyzer.+++# Conclusion / Usability++Pros:++- Highly functional interface (similar to finite maps).+ - Less strict evaluation order (more possibility to parallel execution).+- One can virtually join `i`th fields of different records (if the `i`th fields has the same type).++Cons:++- Linear use should be obeyed.+- Creation of maps is a bit uncomfortable (maps has to be carried).+++# Conclusion / Semantics++The library has a simple semantics.++This is demonstrated by a small pure functional implementation of the interface functions.+++# Further Extensions ++Sets can be modeled as maps to unit values. ++- The current implementation is more efficient than that: 32 sets are packed into 1 integer map.+- The interface of sets and maps are unified.++Identifiers can refer to static data. +For example, if a sequence is implemented by a doubly linked map, +`previous` and `next` are mutable but `value` is static. So two maps are sufficient.+++# Related Work++- [DDC](http://www.haskell.org/haskellwiki/DDC), The Disciplined Disciple Compiler+ - An explicitly lazy dialect of Haskell.+ - Supports destructive update, computational effects, type directed field projections.+- [Monadic Regions](http://okmij.org/ftp/Haskell/regions.html)+ - A technique for managing resources (memory areas, file handles, database connections).+++# Forthcoming Use Cases++- Graph walks.+ - with tagging+ - with pointer reversal+- Strongly connected components computation.+- Linear time type inference algorithm with pointers.++++# Thanks++Thanks for your attention!++The code can be found as `linear-maps` on [HackageDB](http://hackage.haskell.org/packages/archive/pkg-list.html).++
+ LICENSE view
@@ -0,0 +1,29 @@+Copyright (c) Péter Diviánszky 2007++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of the author nor the names of his contributors+ may be used to endorse or promote products derived from this software+ without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ linear-maps.cabal view
@@ -0,0 +1,113 @@+Name: linear-maps+Version: 0.5+Synopsis: Finite maps for linear use+Description: + Finite maps for linear use. + .+ This package contains three different implementations with the same interface.+ The implementations are controlled by Cabal flags which can be set at installation time+ with the following commands:+ .+ [@cabal install -fcheck@] + Installs an implementation where linear use of maps is needed and checked (at runtime).+ It is recommended to use this version during development.+ .+ [@cabal install@] + Installs an implementation where linear use of maps is needed but not checked.+ It is the fastest implementation so it is ideal for the final product.+ Install this only if you are certain that maps are used linearly.+ .+ [@cabal install -fpure@] + Installs an implementation where linear use of maps is not needed and not checked.+ This is the simplest implementation so it can be read as a documentation. + Do not install this version because it is slow and does not check the linear use of maps.+Category: Data+Author: Péter Diviánszky <divip@aszt.inf.elte.hu>+Maintainer: Péter Diviánszky <divip@aszt.inf.elte.hu>+Copyright: (c) 2009 by Péter Diviánszky+License: BSD3+License-File: LICENSE+Stability: Experimental+Tested-With: GHC == 6.10.2+Cabal-Version: >= 1.6+Build-Type: Simple+Extra-Source-Files: + Intro.pandoc,+ Intro.html++Flag check+ Description: Check linear use+ Default: False++Flag pure+ Description: Pure functional implementation+ Default: False++Library+ GHC-Options: -Wall -fwarn-tabs -fno-warn-incomplete-patterns -fcontext-stack=33++ Exposed-Modules: ++ -- helper+ Data.TypeInt,+ Data.Subtyping,+ Control.Functor,++ -- core+ Data.IdMap,+ Data.IdMap.Static,++ -- 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+ -- Tests.PointerReversal,+ -- Tests.RandomGraph++ Other-Modules:++ Data.Array.Simple,+ Data.Control.Kvantum,+ Data.Control.Kvantum.Void,++ Data.IdMap.Core,+ Data.IdMap.Core.Pure,+ Data.IdMap.Core.Fast++ Build-Depends:+ base == 4.1.*,+ containers == 0.2.*,+ HUnit == 1.2.* +-- random++ if flag(pure)+ CPP-Options: -D__PURE__+ else+ if flag(check)+ CPP-Options: -D__CHECK__+ + Extensions:+ GADTs,+ TypeOperators,+ RankNTypes,+ BangPatterns,+ KindSignatures,+ EmptyDataDecls,+ GeneralizedNewtypeDeriving,+ ScopedTypeVariables,+ TypeFamilies,+ MultiParamTypeClasses++ -- CPP,+ -- MagicHash,+ -- UnboxedTuples,++