MemoTrie 0.0 → 0.1

raw patch · 3 files changed

+96/−43 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• MemoTrie.cabal +1/−1
• src/Data/MemoTrie.hs +77/−42
• wikipage.tw +18/−0

@@ -1,5 +1,5 @@ Name:                MemoTrie-Version:             0.0+Version:             0.1 Cabal-Version:       >= 1.2 Synopsis:            Trie-based memo functions Category:            Data

@@ -1,5 +1,8 @@-{-# LANGUAGE GADTs, TypeFamilies, TypeOperators #-}-{-# OPTIONS_GHC -Wall #-}+{-# LANGUAGE GADTs, TypeFamilies, TypeOperators, ScopedTypeVariables #-}+{-# OPTIONS_GHC -Wall -frewrite-rules #-}+-- ScopedTypeVariables works around a 6.10 bug.  The forall keyword is+-- supposed to be recognized+ ---------------------------------------------------------------------- -- | -- Module      :  Data.MemoTrie@@ -16,7 +19,7 @@ module Data.MemoTrie   ( HasTrie(..)   , memo, memo2, memo3, mup-  , trieBits, untrieBits+  -- , untrieBits   ) where  import Data.Bits@@ -24,13 +27,14 @@ import Control.Applicative import Data.Monoid --- Mapping from all elements of 'a' to the results of some function+-- | Mapping from all elements of @a@ to the results of some function class HasTrie a where+    -- | Representation of trie with domain type @a@     data (:->:) a :: * -> *-    -- create the trie-    trie   :: (a -> b) -> (a :->: b)-    -- access a field of the trie-    untrie :: (a :->: b) -> (a -> b)+    -- Create the trie for the entire domain of a function+    trie   :: (a  ->  b) -> (a :->: b)+    -- | Convert a trie to a function, i.e., access a field of the trie+    untrie :: (a :->: b) -> (a  ->  b)  {-# RULES "trie/untrie"   forall t. trie (untrie t) = t@@ -59,40 +63,53 @@  ---- Instances +instance HasTrie () where+    data () :->: a = UnitTrie a+    trie f = UnitTrie (f ())+    untrie (UnitTrie x) () = x+ instance HasTrie Bool where     data Bool :->: a = BoolTrie a a     trie f = BoolTrie (f False) (f True)     untrie (BoolTrie f _) False = f     untrie (BoolTrie _ t) True  = t -instance HasTrie () where-    data () :->: a = UnitTrie a-    trie f = UnitTrie (f ())-    untrie (UnitTrie x) () = x- instance (HasTrie a, HasTrie b) => HasTrie (Either a b) where     data (Either a b) :->: x = EitherTrie (a :->: x) (b :->: x)-    untrie (EitherTrie f _) (Left  x) = untrie f x-    untrie (EitherTrie _ g) (Right y) = untrie g y+    untrie (EitherTrie f g) = either (untrie f) (untrie g)     trie f = EitherTrie (trie (f . Left)) (trie (f . Right))  instance (HasTrie a, HasTrie b) => HasTrie (a,b) where     data (a,b) :->: x = PairTrie (a :->: (b :->: x))-    untrie (PairTrie f) (a,b) = untrie (untrie f a) b     trie f = PairTrie $ trie $ \a -> trie $ \b -> f (a,b)+    untrie (PairTrie t) = uncurry (untrie .  untrie t) -instance (HasTrie a, HasTrie b, HasTrie c) => HasTrie (a,b, c) where-    data (a,b,c) :->: x = TripleTrie (a :->: (b :->: (c :->: x)))-    untrie (TripleTrie f) (a,b,c) = untrie (untrie (untrie f a) b) c-    trie f = TripleTrie $-      trie $ \a -> trie $ \b -> trie $ \ c -> f (a,b,c)+trip :: ((a,b),c) -> (a,b,c)+trip ((a,b),c) = (a,b,c) +detrip :: (a,b,c) -> ((a,b),c)+detrip (a,b,c) = ((a,b),c)++instance (HasTrie a, HasTrie b, HasTrie c) => HasTrie (a,b,c) where+    data (a,b,c) :->: x = TripleTrie (((a,b),c) :->: x)+    trie f = TripleTrie (trie (f . trip))+    untrie (TripleTrie t) = untrie t . detrip++list :: Either () (x,[x]) -> [x]+list = either (const []) (uncurry (:))++delist :: [x] -> Either () (x,[x])+delist []     = Left ()+delist (x:xs) = Right (x,xs)+ instance HasTrie x => HasTrie [x] where-    data [x] :->: a = ListTrie a (x :->: ([x] :->: a))-    trie f = ListTrie (f []) $ trie (\x -> trie (f . (x:)))-    untrie (ListTrie n _) []     = n-    untrie (ListTrie _ t) (x:xs) = untrie (untrie t x) xs+    data [x] :->: a = ListTrie (Either () (x,[x]) :->: a)+    trie f = ListTrie (trie (f . list))+    untrie (ListTrie t) = untrie t . delist +-- TODO: make these definitions more systematic.++ -- Handy for Bits types  -- | Extract bits in little-endian order@@ -110,23 +127,15 @@ unbits [] = 0 unbits (x:xs) = unbit x .|. shiftL (unbits xs) 1 --- | Handy for 'trie' in a bits-based 'Trie' instance-trieBits :: Bits t => (t -> a) -> ([Bool] :->: a)-trieBits f = trie (f . unbits)---- | Handy for 'untrie' in a bits-based 'Trie' instance-untrieBits :: Bits t => ([Bool] :->: a) -> (t -> a)-untrieBits t x = untrie t (bits x)- instance HasTrie Word where     data Word :->: a = WordTrie ([Bool] :->: a)-    untrie (WordTrie t) = untrieBits t-    trie = WordTrie . trieBits+    trie f = WordTrie (trie (f . unbits))+    untrie (WordTrie t) = untrie t . bits  -- Although Int is a Bits instance, we can't use bits directly for -- memoizing, because the "bits" function gives an infinite result, since -- shiftR (-1) 1 == -1.  Instead, convert between Int and Word, and use--- a Word trie.+-- a Word trie.  Any Integral type can be handled similarly.  instance HasTrie Int where     data Int :->: a = IntTrie (Word :->: a)@@ -138,21 +147,47 @@  {- -'untrie' is a 'Functor'-, 'Applicative'-, and 'Monoid'-morphism, i.e.,+The \"semantic function\" 'untrie' is a morphism over 'Monoid', 'Functor',+'Applicative', and 'Monad', i.e., +  untrie mempty          == mempty+  untrie (s `mappend` t) == untrie s `mappend` untrie t+   untrie (fmap f t)      == fmap f (untrie t)    untrie (pure a)        == pure a   untrie (tf <*> tx)     == untrie tf <*> untrie tx -  untrie mempty          == mempty-  untrie (s `mappend` t) == untrie s `mappend` untrie t+  untrie (return a)      == return a+  untrie (u >>= k)       == untrie u >>= untrie . k +These morphism properties imply that all of the expected laws hold,+assuming that we interpret equality semantically (or observationally).+For instance,++  untrie (mempty `mappend` a)+    == untrie mempty `mappend` untrie a+    == mempty `mappend` untrie a+    == untrie a++  untrie (fmap f (fmap g a))+    == fmap f (untrie (fmap g a))+    == fmap f (fmap g (untrie a))+    == fmap (f.g) (untrie a)+    == untrie (fmap (f.g) a)+ The implementation instances then follow from applying 'trie' to both sides of each of these morphism laws. +Correctness of these instances follows by applying 'untrie' to each side+of each definition and using the property @'untrie' . 'trie' == 'id'@.+ -} +instance (HasTrie a, Monoid b) => Monoid (a :->: b) where+  mempty        = trie mempty+  s `mappend` t = trie (untrie s `mappend` untrie t)+ instance HasTrie a => Functor ((:->:) a) where   fmap f t      = trie (fmap f (untrie t)) @@ -160,6 +195,6 @@   pure b        = trie (pure b)   tf <*> tx     = trie (untrie tf <*> untrie tx) -instance (HasTrie a, Monoid b) => Monoid (a :->: b) where-  mempty        = trie mempty-  s `mappend` t = trie (untrie s `mappend` untrie t)+instance HasTrie a => Monad ((:->:) a) where+  return a      = trie (return a)+  u >>= k       = trie (untrie u >>= untrie . k)

@@ -0,0 +1,18 @@+[[Category:Packages]]++== Abstract ==++'''MemoTrie''' is functional library for creating efficient memo functions, using [http://en.wikipedia.org/wiki/Trie trie]s.  It's based on some code I got from Spencer Janssen and uses type families.++Besides this wiki page, here are more ways to find out about MemoTrie:+* Read [http://code.haskell.org/MemoTrie/doc/html/ the library documentation].+* Get the code repository: '''<tt>darcs get http://code.haskell.org/MemoTrie</tt>'''.+* Install from [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MemoTrie Hackage].+* See the [[MemoTrie/Versions| version history]].++Please leave comments at the [[Talk:MemoTrie|Talk page]].++== See also ==++* [http://www.haskell.org/haskellwiki/GHC/Indexed_types#An_associated_data_type_example An associated data type example]+* [http://citeseer.ist.psu.edu/233124.html Generalizing Generalized Tries]