-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Finite maps for linear use
--
-- 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.
--
@package linear-maps
@version 0.6
module Data.Sequence.Profile
prof1 :: Int -> Int -> Int
prof2 :: Int -> Int
-- | Functor2 and Functor3 type classes
module Control.Functor
class Functor2 f :: (* -> * -> *)
fmap2 :: (Functor2 f) => (a -> b) -> f a x -> f b x
class Functor3 f :: (* -> * -> * -> *)
fmap3 :: (Functor3 f) => (a -> b) -> f a x y -> f b x y
module Data.Subtyping
data (:|:) a b
class Incl c
left :: (Incl c) => c a -> c (a :|: b)
right :: (Incl c) => c b -> c (a :|: b)
class Incl2 c
left2 :: (Incl2 c) => c a x -> c (a :|: b) x
right2 :: (Incl2 c) => c b x -> c (a :|: b) x
-- | Very simple type-level integers
module Data.TypeInt
-- | 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
num :: (I m) => m -> Int
induction :: (I m) => m -> a -> (a -> a) -> a
induction' :: (I m) => a Zero -> (forall i. a i -> a (Succ i)) -> a m
induction'' :: (I m) => a Zero x -> (forall i. a i x -> a (Succ i) x) -> a m x
instance (I a) => I (Succ a)
instance I Zero
-- | Linearly usable maps and sets on identifiers
module Data.IdMap
-- | 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.
--
data Id k
-- | 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
-- | 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
-- | 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 ()
-- | 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.
insert :: (MaplikeClass i a) => Id k -> a -> Maplike i k a -> Maplike i k a
-- | 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 :: (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 :: (MaplikeClass i a) => Id k -> Maplike i k a -> Maybe a
member :: (MaplikeClass i a) => Id k -> Maplike i k a -> Bool
-- | 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.
--
union :: Maplike i k1 a -> Maplike i k2 a -> Maplike i (k1 :|: k2) a
unsafeInsert :: (MaplikeClass i a) => Id k -> a -> Maplike i k 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
-- | 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).
data Sets i k
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).
data Maps i 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 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
data Maplike i k a
class MaplikeClass i x
inserts :: (I i) => Map i k a -> [(Id k, a)] -> Map i k a
(!) :: (I i) => Map i k a -> Id k -> a
-- | 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
setInserts :: (I i) => Set i k -> [Id k] -> Set i k
module Data.IdMap.Static
-- | Identifiers with static data.
data (:.) k x
(:.) :: !Id k -> !x -> :. k x
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
lookUp :: (MaplikeClass i a) => k :. d -> Maplike i k a -> Maybe a
(!) :: (I i) => Map i k a -> k :. d -> a
member :: (MaplikeClass i a) => k :. d -> Maplike i k a -> Bool
inserts :: (I i) => Map i k a -> [(k :. d, a)] -> Map i k a
setInsert :: (I i) => k :. d -> Set i k -> Set i k
setInserts :: (I i) => Set i k -> [k :. d] -> Set i k
instance Functor ((:.) x)
instance Incl2 :.
module Data.Sequence.IdMap2
data Seq a
empty :: Seq a
singleton :: a -> Seq a
(<|) :: a -> Seq a -> Seq a
(|>) :: Seq a -> a -> Seq a
(><) :: Seq a -> Seq a -> Seq a
fromList :: [a] -> Seq a
toList :: Seq a -> [a]
viewr :: Seq a -> ViewR a
data ViewR a
EmptyR :: ViewR a
(:>) :: Seq a -> a -> ViewR a
viewl :: Seq a -> ViewL a
data ViewL a
EmptyL :: ViewL a
(:<) :: a -> Seq a -> ViewL a
module Data.Sequence.IdMap
data Seq a
empty :: Seq a
singleton :: a -> Seq a
(<|) :: a -> Seq a -> Seq a
(|>) :: Seq a -> a -> Seq a
(><) :: Seq a -> Seq a -> Seq a
fromList :: [a] -> Seq a
toList :: Seq a -> [a]
viewr :: Seq a -> ViewR a
data ViewR a
EmptyR :: ViewR a
(:>) :: Seq a -> !a -> ViewR a
viewl :: Seq a -> ViewL a
data ViewL a
EmptyL :: ViewL a
(:<) :: !a -> Seq a -> ViewL a
module Data.Sequence.IdMap.Tests
tests :: IO Counts
module Data.Sequence.IdMap.Profile
prof1 :: Int -> Int -> Int
prof2 :: Int -> Int
module Data.IdSequence
data Seq k a
previous :: Seq k a -> Id k -> Maybe (Id k)
next :: Seq k a -> Id k -> Maybe (Id k)
value :: Seq k a -> Id k -> Maybe a
member :: Id k -> Seq k a -> Bool
update :: Id k -> a -> Seq k a -> Seq k a
delete :: Id k -> Seq k a -> Seq k a
insertBefore :: Id k -> a -> Seq k a -> (forall k'. Seq (k :|: k') a -> e) -> e
fromList :: [a] -> (forall k. Id k -> Id k -> Seq k a -> e) -> e
module Data.List.IdMap
nubId :: (I m) => Set m a -> [Id a] -> (Set m a, [Id a])
fromList' :: (I m) => Map m a [b] -> [(Id a, b)] -> Map m a [b]
module Data.Graph.IdMap
type Children a = a -> [a]
depthFirstWalk' :: (I m) => Children (Id a) -> Set m a -> [Id a] -> (Set m a, [Id a])
depthFirstWalk :: (I m) => Children (Id a) -> Set m a -> [Id a] -> [Id a]
data Task a
Return :: a -> Task a
Visit :: a -> Task a
postOrderWalk :: (I m) => Children (Id a) -> Set m a -> [Id a] -> [Id a]
scc :: (I m) => Set m a -> Set m a -> Children (Id a) -> Children (Id a) -> [Id a] -> [[Id a]]
mapWalk :: (I m) => Set m a -> Children (Id a) -> [Id a] -> [[Id a]]
module Data.Graph.IdMap.Tests
toFunction :: (I i) => Map i k [a] -> Id k -> [a]
relationToFunction :: (Eq a) => [(a, b)] -> a -> [b]
testWalk :: (forall k i. (I i) => Children (Id k) -> Set i k -> [Id k] -> [Id k]) -> [Char] -> [Char]
testPrWalk :: (forall k i i'. (I i, I i') => Map i k [Id k] -> Map i' k Int -> Id k -> [Id k]) -> Char -> [Char]
testMapWalk :: (forall k i. (I i) => Children (Id k) -> Set i k -> [Id k] -> [[Id k]]) -> [Char] -> [[Char]]
testSCC :: (forall k i. (I i) => Children (Id k) -> Children (Id k) -> Set i k -> [Id k] -> [[Id k]]) -> [Char] -> [[Char]]
withGraph :: (forall k i i' i'' i''' i4. (I i, I i', I i'', I i''', I i4) => (Id k -> Char) -> (Char -> Id k) -> Map i'' k [Id k] -> Map i''' k [Id k] -> Set i k -> Set i' k -> (forall x. Map i4 k x) -> a) -> a
tests :: IO Counts
module Data.LinkMap
data LinkMap i k a
linkMap :: (forall b. Map i k b) -> LinkMap i k a
link :: (I i) => Id k -> Id k -> LinkMap i k a -> LinkMap i k a
follow :: (I i) => LinkMap i k a -> Id k -> Id k
lookUp :: (I i) => Id k -> LinkMap i k a -> Maybe a
insert :: (I i) => Id k -> a -> LinkMap i k a -> LinkMap i k a
delete :: (I i) => Id k -> LinkMap i k a -> LinkMap i k a
union :: LinkMap i k a -> LinkMap i l a -> LinkMap i (k :|: l) a
member :: (I i) => Id k -> LinkMap i k a -> Bool
notMember :: (I i) => Id k -> LinkMap i k a -> Bool
same :: (I i) => LinkMap i k a -> Id k -> Id k -> Bool
(!) :: (I i) => LinkMap i k a -> Id k -> a
fromList :: (I i) => (forall b. Map i k b) -> [(Id k, a)] -> LinkMap i k a
instance Functor (LinkMap i k)
instance Functor2 Pointer
instance Functor (Pointer k)
module Data.LinkMap.Tests
tests :: IO Counts
-- | Integrity test of the linear-maps package.
module Test.IdMap
-- | Runs all unit tests found in the linear-maps package.
tests :: IO ()