explicit-sharing 0.3.1.3 → 0.4.0

raw patch · 7 files changed

+305/−265 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Control/Monad/Sharing.hs +6/−140
• Control/Monad/Sharing/Classes.hs +103/−0
• Control/Monad/Sharing/Implementation/CPS.hs +120/−0
• Control/Monad/Sharing/Lazy.hs +0/−121
• Data/Monadic/List.hs +69/−0
• Test.hs +3/−2
• explicit-sharing.cabal +4/−2

@@ -1,7 +1,5 @@-{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, Rank2Types #-}- -- | Module      : Control.Monad.Sharing--- | Copyright   : Sebastian Fischer+-- | Copyright   : Chung-chieh Shan, Oleg Kiselyov, and Sebastian Fischer -- | License     : PublicDomain -- | -- | Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)@@ -15,146 +13,14 @@    -- * Classes -  Sharing(..), Trans(..),--  -- $predefined--  -- * Evaluation--  eval,+  Sharing(..), Trans(..), eval, -  -- * Monadic lists+  -- * Monad transformer -  List(..), nil, cons, isEmpty, first, rest+  Lazy, evalLazy   ) where  import Control.Monad---- | Interface of monads that support explicit sharing.-class Sharing m- where-  -- | Yields an action that returns the same results as the given-  -- | action but whose effects are only executed once. Especially,-  -- | when the resulting action is duplicated it returns the same-  -- | result at every occurrence.-  share :: Trans m a a => m a -> m (m a)---- | Interface to transform nested monadic data types. The provided--- | function @trans@ is supposed to map the given function on every--- | monadic argument. The result of @trans@ may be of the same type--- | as the argument but can also be of a different type, e.g. to--- | convert a value with nested monadic arguments to a corresponding--- | value without.-class Trans m a b- where-  trans :: (forall c d . Trans m c d => m c -> m (m d)) -> a -> m b---- | Lifts all monadic effects in nested monadic values to the top--- | level. If @m@ is a monad for non-determinism and the argument a--- | data structure with nested non-determinism then the result--- | corresponds to the normal form of the argument.-eval :: (Monad m, Trans m a b) => a -> m b-eval = trans (\a -> liftM return (a >>= eval))---- $predefined ------ We provide instances of the @Trans@ class for some predefined--- Haskell types. For flat types the function @trans@ just returns its--- argument which has no arguments to which the given function could--- be applied.--instance Monad m => Trans m Bool Bool- where-  trans _ = return--instance Monad m => Trans m Int Int- where-  trans _ = return--instance Monad m => Trans m Char Char- where-  trans _ = return--instance Monad m => Trans m Float Float- where-  trans _ = return--instance Monad m => Trans m Double Double- where-  trans _ = return--instance Monad m => Trans m [Bool] [Bool]- where-  trans _ = return--instance Monad m => Trans m [Int] [Int]- where-  trans _ = return--instance Monad m => Trans m [Char] [Char]- where-  trans _ = return--instance Monad m => Trans m [Float] [Float]- where-  trans _ = return--instance Monad m => Trans m [Double] [Double]- where-  trans _ = return---- | An instance for lists with monadic elements.-instance (Monad m, Trans m a a) => Trans m [m a] [m a]- where-  trans f = mapM f---- | An instance for lists with monadic elements that lifts all--- | monadic effects to the top level and yields a list with--- | non-monadic elements.-instance (Monad m, Trans m a a) => Trans m [m a] [a]- where-  trans f = mapM (join . f)---- | Data type for lists where both the head and tail are monadic.-data List m a = Nil | Cons (m a) (m (List m a))---- | The empty monadic list.-nil :: Monad m => m (List m a)-nil = return Nil---- | Constructs a non-empty monadic list.-cons :: Monad m => m a -> m (List m a) -> m (List m a)-cons x xs = return (Cons x xs)---- | Checks if monadic list is empty.-isEmpty :: Monad m => m (List m a) -> m Bool-isEmpty ml = do l <- ml-                case l of-                  Nil      -> return True-                  Cons _ _ -> return False---- | Yields the head of a monadic list. Relies on @MonadPlus@ instance--- | to provide a failing implementation of @fail@.-first :: MonadPlus m => m (List m a) -> m a-first ml = do Cons x _ <- ml; x---- | Yields the tail of a monadic list. Relies on @MonadPlus@ instance--- | to provide a failing implementation of @fail@.-rest :: MonadPlus m => m (List m a) -> m (List m a)-rest ml = do Cons _ xs <- ml; xs--instance (Monad m, Trans m a b) => Trans m (List m a) (List m b)- where-  trans _ Nil         = return Nil-  trans f (Cons x xs) = return Cons `ap` f x `ap` f xs--instance (Monad m, Trans m a b) => Trans m (List m a) [b]- where-  trans _ Nil         = return []-  trans f (Cons x xs) = return (:) `ap` join (f x) `ap` join (f xs)--instance (Monad m, Trans m a b) => Trans m [a] (List m b)- where-  trans _ []     = return Nil-  trans f (x:xs) = return Cons `ap` f (return x) `ap` f (return xs)+import Control.Monad.Sharing.Classes            ( Sharing(..), Trans(..), eval )+import Control.Monad.Sharing.Implementation.CPS ( Lazy, evalLazy )

@@ -0,0 +1,103 @@+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, Rank2Types #-}++-- | Module      : Control.Monad.Sharing.Classes+-- | Copyright   : Chung-chieh Shan, Oleg Kiselyov, and Sebastian Fischer+-- | License     : PublicDomain+-- |+-- | Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- | Stability   : experimental+-- |+-- | This library provides type classes for explicit sharing of+-- | monadic effects.+module Control.Monad.Sharing.Classes (++  Sharing(..), ++  -- | We provide instances of the @Trans@ class for some predefined+  -- | Haskell types. For flat types the function @trans@ just returns+  -- | its argument which has no arguments to which the given function+  -- | could be applied.++  Trans(..), eval++ ) where++import Control.Monad ( liftM, join )++-- | Interface of monads that support explicit sharing.+class Sharing m+ where+  -- | Yields an action that returns the same results as the given+  -- | action but whose effects are only executed once. Especially,+  -- | when the resulting action is duplicated it returns the same+  -- | result at every occurrence.+  share :: Trans m a a => m a -> m (m a)++-- | Interface to transform nested monadic data types. The provided+-- | function @trans@ is supposed to map the given function on every+-- | monadic argument. The result of @trans@ may be of the same type+-- | as the argument but can also be of a different type, e.g. to+-- | convert a value with nested monadic arguments to a corresponding+-- | value without.+class Trans m a b+ where+  trans :: (forall c d . Trans m c d => m c -> m (m d)) -> a -> m b++-- | Lifts all monadic effects in nested monadic values to the top+-- | level. If @m@ is a monad for non-determinism and the argument a+-- | data structure with nested non-determinism then the result+-- | corresponds to the normal form of the argument.+eval :: (Monad m, Trans m a b) => a -> m b+eval = trans (\a -> liftM return (a >>= eval))++instance Monad m => Trans m Bool Bool+ where+  trans _ = return++instance Monad m => Trans m Int Int+ where+  trans _ = return++instance Monad m => Trans m Char Char+ where+  trans _ = return++instance Monad m => Trans m Float Float+ where+  trans _ = return++instance Monad m => Trans m Double Double+ where+  trans _ = return++instance Monad m => Trans m [Bool] [Bool]+ where+  trans _ = return++instance Monad m => Trans m [Int] [Int]+ where+  trans _ = return++instance Monad m => Trans m [Char] [Char]+ where+  trans _ = return++instance Monad m => Trans m [Float] [Float]+ where+  trans _ = return++instance Monad m => Trans m [Double] [Double]+ where+  trans _ = return++-- | An instance for lists with monadic elements.+instance (Monad m, Trans m a a) => Trans m [m a] [m a]+ where+  trans f = mapM f++-- | An instance for lists with monadic elements that lifts all+-- | monadic effects to the top level and yields a list with+-- | non-monadic elements.+instance (Monad m, Trans m a a) => Trans m [m a] [a]+ where+  trans f = mapM (join . f)

@@ -0,0 +1,120 @@+{-# LANGUAGE ExistentialQuantification, +             MultiParamTypeClasses,+             FlexibleContexts,+             Rank2Types +  #-}++{-# OPTIONS -fno-warn-name-shadowing #-}++-- | Module      : Control.Monad.Sharing.Implementation.CPS+-- | Copyright   : Chung-chieh Shan, Oleg Kiselyov, and Sebastian Fischer+-- | License     : PublicDomain+-- |+-- | Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- | Stability   : experimental+-- |+-- | Implements explicit sharing by passing a heap using a state monad+-- | implemented by a combination of a continuation- with a reader+-- | monad. The definitions are inlined and hand-optimized to increase+-- | performance.+module Control.Monad.Sharing.Implementation.CPS (++  Lazy, evalLazy++ ) where++import Control.Monad                 ( MonadPlus(..) )+import Control.Monad.Trans           ( MonadTrans(..), MonadIO(..) )+import Control.Monad.Sharing.Classes ( Sharing(..), Trans(..), eval )++-- For fast and easy implementation of typed stores..+import Unsafe.Coerce++import qualified Data.IntMap as M++-- | Continuation-based, store-passing implementation of explicit+-- | sharing. It is an inlined version of @ContT (ReaderT Store m)@+-- | where the result type of continuations is polymorphic.+newtype Lazy m a = Lazy {++  -- | Runs a computation of type @Lazy m a@ with given continuation+  -- | and store.+  fromLazy :: forall w . (a -> Store -> m w) -> Store -> m w+ }++-- | Lifts all monadic effects to the top-level and unwraps the monad+-- | transformer for explicit sharing.+evalLazy :: (Monad m, Trans (Lazy m) a b) => Lazy m a -> m b+evalLazy m = runLazy (m >>= eval)++-- private declarations++runLazy :: Monad m => Lazy m a -> m a+runLazy m = fromLazy m (\a _ -> return a) (Store 1 M.empty)++-- Stores consist of a fresh-reference counter and a heap represented+-- as IntMap.+data Store = Store Int (M.IntMap Untyped)++-- The monad instance is an inlined version of the instances for+-- continuation and reader monads.+instance Monad m => Monad (Lazy m)+ where+  return x = Lazy (\c -> c x)+  a >>= k  = Lazy (\c s -> fromLazy a (\x -> fromLazy (k x) c) s)+  fail err = Lazy (\_ _ -> fail err)++-- The @MonadPlus@ instance reuses corresponding operations of the+-- base monad.+instance MonadPlus m => MonadPlus (Lazy m)+ where+  mzero       = Lazy (\_ _ -> mzero)+  a `mplus` b = Lazy (\c s -> fromLazy a c s `mplus` fromLazy b c s)++-- @Lazy@ is a monad transformer.+instance MonadTrans Lazy+ where+  lift a = Lazy (\c s -> a >>= \x -> c x s)++-- If the underlying monad supports IO we can lift this functionality.+instance MonadIO m => MonadIO (Lazy m)+ where+  liftIO = lift . liftIO++-- The @Sharing@ instance memoizes nested monadic values recursively.+instance Monad m => Sharing (Lazy m)+ where+  share = lazy++-- The more general type is necessary to please the type checker.+lazy :: (Monad m, Trans (Lazy m) a b) => Lazy m a -> Lazy m (Lazy m b)+lazy a = memo (a >>= trans lazy)++-- This is an inlined version of the following definition:+-- +-- > memo :: MonadState Store m => m a -> m (m a)+-- > memo a = do key <- getFreshKey+-- >             return $ do thunk <- lookupHNF key+-- >                         case thunk of+-- >                           Just x  -> return x+-- >                           Nothing -> do x <- a+-- >                                         insertHNF key x+-- >                                         return x+--+memo :: Lazy m a -> Lazy m (Lazy m a)+memo a = Lazy (\c (Store key heap) ->+      c (Lazy (\c s@(Store _ heap) -> +         case M.lookup key heap of+          Just x  -> c (typed x) s+          Nothing -> fromLazy a+           (\x (Store other heap) -> +              c x (Store other (M.insert key (Untyped x) heap))) s))+        (Store (succ key) heap))++-- Easy and fast hack to store typed data. An implementation using+-- Data.Typeable is possible but clutters the code with additional+-- class constraints.+data Untyped = forall a . Untyped a++typed :: Untyped -> a+typed (Untyped x) = unsafeCoerce x

@@ -1,121 +0,0 @@-{-# LANGUAGE ExistentialQuantification, -             MultiParamTypeClasses,-             FlexibleContexts,-             Rank2Types -  #-}--{-# OPTIONS -fno-warn-name-shadowing #-}---- | Module      : Control.Monad.Sharing.Lazy--- | Copyright   : Sebastian Fischer--- | License     : PublicDomain--- |--- | Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)--- | Stability   : experimental--- |--- | Implements explicit sharing by passing a heap using a state monad--- | implemented by a combination of a continuation- with a reader--- | monad. The definitions are inlined and hand-optimized to increase--- | performance.-module Control.Monad.Sharing.Lazy (--  module Control.Monad.Sharing,--  Lazy, evalLazy-- ) where--import Control.Monad.Trans-import Control.Monad.Sharing---- For fast and easy implementation of typed stores..-import Unsafe.Coerce--import qualified Data.IntMap as M---- | Continuation-based, store-passing implementation of explicit--- | sharing. It is an inlined version of @ContT (ReaderT Store m)@--- | where the result type of continuations is polymorphic.-newtype Lazy m a = Lazy {--  -- | Runs a computation of type @Lazy m a@ with given continuation-  -- | and store.-  fromLazy :: forall w . (a -> Store -> m w) -> Store -> m w- }---- | Lifts all monadic effects to the top-level and unwraps the monad--- | transformer for explicit sharing.-evalLazy :: (Monad m, Trans (Lazy m) a b) => Lazy m a -> m b-evalLazy m = runLazy (m >>= eval)---- private declarations--runLazy :: Monad m => Lazy m a -> m a-runLazy m = fromLazy m (\a _ -> return a) (Store 1 M.empty)---- Stores consist of a fresh-reference counter and a heap represented--- as IntMap.-data Store = Store Int (M.IntMap Untyped)---- The monad instance is an inlined version of the instances for--- continuation and reader monads.-instance Monad m => Monad (Lazy m)- where-  return x = Lazy (\c -> c x)-  a >>= k  = Lazy (\c s -> fromLazy a (\x -> fromLazy (k x) c) s)-  fail err = Lazy (\_ _ -> fail err)---- The @MonadPlus@ instance reuses corresponding operations of the--- base monad.-instance MonadPlus m => MonadPlus (Lazy m)- where-  mzero       = Lazy (\_ _ -> mzero)-  a `mplus` b = Lazy (\c s -> fromLazy a c s `mplus` fromLazy b c s)---- @Lazy@ is a monad transformer.-instance MonadTrans Lazy- where-  lift a = Lazy (\c s -> a >>= \x -> c x s)---- If the underlying monad supports IO we can lift this functionality.-instance MonadIO m => MonadIO (Lazy m)- where-  liftIO = lift . liftIO---- The @Sharing@ instance memoizes nested monadic values recursively.-instance Monad m => Sharing (Lazy m)- where-  share = lazy---- The more general type is necessary to please the type checker.-lazy :: (Monad m, Trans (Lazy m) a b) => Lazy m a -> Lazy m (Lazy m b)-lazy a = memo (a >>= trans lazy)---- This is an inlined version of the following definition:--- --- > memo :: MonadState Store m => m a -> m (m a)--- > memo a = do key <- getFreshKey--- >             return $ do thunk <- lookupHNF key--- >                         case thunk of--- >                           Just x  -> return x--- >                           Nothing -> do x <- a--- >                                         insertHNF key x--- >                                         return x----memo :: Lazy m a -> Lazy m (Lazy m a)-memo a = Lazy (\c (Store key heap) ->-      c (Lazy (\c s@(Store _ heap) -> -         case M.lookup key heap of-          Just x  -> c (typed x) s-          Nothing -> fromLazy a-           (\x (Store other heap) -> -              c x (Store other (M.insert key (Untyped x) heap))) s))-        (Store (succ key) heap))---- Easy and fast hack to store typed data. An implementation using--- Data.Typeable is possible but clutters the code with additional--- class constraints.-data Untyped = forall a . Untyped a--typed :: Untyped -> a-typed (Untyped x) = unsafeCoerce x

@@ -0,0 +1,69 @@+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}++-- | Module      : Data.Monadic.List+-- | Copyright   : Chung-chieh Shan, Oleg Kiselyov, and Sebastian Fischer+-- | License     : PublicDomain+-- |+-- | Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- | Stability   : experimental+-- |+-- | This library provides lists with monadic head and tail as an+-- | example for nested monadic data that can be used with the+-- | combinator @share@ for explicit sharing.+module Data.Monadic.List (++  List(..), nil, cons, isEmpty, first, rest++ ) where++import Control.Monad                 ( MonadPlus, ap, join )+import Control.Monad.Sharing.Classes ( Trans(..) )++-- | Data type for lists where both the head and tail are monadic.+data List m a = Nil | Cons (m a) (m (List m a))++-- | The empty monadic list.+nil :: Monad m => m (List m a)+nil = return Nil++-- | Constructs a non-empty monadic list.+cons :: Monad m => m a -> m (List m a) -> m (List m a)+cons x xs = return (Cons x xs)++-- | Checks if monadic list is empty.+isEmpty :: Monad m => m (List m a) -> m Bool+isEmpty ml = do l <- ml+                case l of+                  Nil      -> return True+                  Cons _ _ -> return False++-- | Yields the head of a monadic list. Relies on @MonadPlus@ instance+-- | to provide a failing implementation of @fail@.+first :: MonadPlus m => m (List m a) -> m a+first ml = do Cons x _ <- ml; x++-- | Yields the tail of a monadic list. Relies on @MonadPlus@ instance+-- | to provide a failing implementation of @fail@.+rest :: MonadPlus m => m (List m a) -> m (List m a)+rest ml = do Cons _ xs <- ml; xs++-- | This instance allows to use nested monadic lists as argument to+-- | the @Control.Monad.Sharing.share@ combinator.+instance (Monad m, Trans m a b) => Trans m (List m a) (List m b)+ where+  trans _ Nil         = return Nil+  trans f (Cons x xs) = return Cons `ap` f x `ap` f xs++-- | This instance enables the function @Control.Monad.Sharing.eval@+-- | to transform nested monadic lists into ordinary Haskell lists.+instance (Monad m, Trans m a b) => Trans m (List m a) [b]+ where+  trans _ Nil         = return []+  trans f (Cons x xs) = return (:) `ap` join (f x) `ap` join (f xs)++-- | This instance enables the function @Control.Monad.Sharing.eval@+-- | to transform ordinary Haskell lists into nested monadic lists.+instance (Monad m, Trans m a b) => Trans m [a] (List m b)+ where+  trans _ []     = return Nil+  trans f (x:xs) = return Cons `ap` f (return x) `ap` f (return xs)

@@ -6,7 +6,8 @@      FlexibleContexts   #-} -import Control.Monad.Sharing.Lazy+import Control.Monad.Sharing+import Data.Monadic.List  main = do   putStr "failing tests: "@@ -148,7 +149,7 @@   x <- share (share coin >>= id)   return (x,x) -dup_dup = assertEqual [((0::Int,0::Int),(0::Int,0::Int)),((1,1),(1,1))] $ +dup_dup = assertEqual [((0::Int,0::Int),(0::Int,0::Int)),((1,1),(1,1))]             (dup (dup coin :: Lazy [] (Lazy [] Int,Lazy [] Int))               :: Lazy [] (Lazy [] (Lazy [] Int,Lazy [] Int),                           Lazy [] (Lazy [] Int,Lazy [] Int)))

@@ -1,5 +1,5 @@ Name:          explicit-sharing-Version:       0.3.1.3+Version:       0.4.0 Cabal-Version: >= 1.6 Synopsis:      Explicit Sharing of Monadic Effects Description:   @@ -21,7 +21,9 @@ Library   Build-Depends:    base, containers ==0.2.0.0, mtl   Exposed-Modules:  Control.Monad.Sharing,-                    Control.Monad.Sharing.Lazy+                    Control.Monad.Sharing.Classes,+                    Data.Monadic.List+  Other-Modules:    Control.Monad.Sharing.Implementation.CPS   Ghc-Options:      -Wall   Extensions:       ExistentialQuantification,                     MultiParamTypeClasses,