stream-monad 0.3 → 0.4
raw patch · 4 files changed
+172/−96 lines, 4 filesdep +criteriondep +logictnew-component:exe:stream-monad-benchmarks
Dependencies added: criterion, logict
Files
- Control/Monad/Stream.hs +0/−94
- src/Control/Monad/Stream.hs +114/−0
- src/benchmarks.hs +39/−0
- stream-monad.cabal +19/−2
− Control/Monad/Stream.hs
@@ -1,94 +0,0 @@--- |--- Module : Control.Monad.Stream--- Copyright : Oleg Kiselyov, Sebastian Fischer--- License : BSD3--- --- Maintainer : Sebastian Fischer (sebf@informatik.uni-kiel.de)--- Stability : experimental--- Portability : portable--- --- This Haskell library provides an implementation of the MonadPlus--- type class that enumerates results of a non-deterministic--- computation by interleaving subcomputations in a way that has--- usually much better memory performance than other strategies with--- the same termination properties.--- --- By using supensions in strategic positions, the user can ensure--- that the search does not diverge if there are remaining--- non-deterministic results.--- --- More information is available on the authors website:--- <http://okmij.org/ftp/Computation/monads.html#fair-bt-stream>--- --- Warning: @Stream@ is only a monad when the results of @runStream@--- are interpreted as a multiset, i.e., a valid transformation--- according to the monad laws may change the order of the results.--- -module Control.Monad.Stream ( Stream, suspended, runStream ) where--import Control.Monad-import Control.Applicative---- |--- Results of non-deterministic computations of type @Stream a@ can be--- enumerated efficiently.--- -data Stream a = Nil | Single a | Cons a (Stream a) | Susp (Stream a)--instance Functor Stream- where- fmap _ Nil = Nil- fmap f (Single x) = Single (f x)- fmap f (Cons x xs) = Cons (f x) (fmap f xs)- fmap f (Susp xs) = Susp (fmap f xs)---- |--- Suspensions can be used to ensure fairness.--- -suspended :: Stream a -> Stream a-suspended = Susp---- |--- The function @runStream@ enumerates the results of a--- non-deterministic computation.--- -runStream :: Stream a -> [a]-runStream Nil = []-runStream (Single x) = [x]-runStream (Cons x xs) = x : runStream xs-runStream (Susp xs) = runStream xs--instance Monad Stream- where- return = Single-- Nil >>= _ = Nil- Single x >>= f = f x- Cons x xs >>= f = f x `mplus` suspended (xs >>= f)- Susp xs >>= f = suspended (xs >>= f)-- fail _ = Nil--instance MonadPlus Stream- where- mzero = Nil-- Nil `mplus` ys = suspended ys -- suspending- Single x `mplus` ys = Cons x ys- Cons x xs `mplus` ys = Cons x (ys `mplus` xs) -- interleaving- xs `mplus` Nil = xs- Susp xs `mplus` Single y = Cons y xs- Susp xs `mplus` Cons y ys = Cons y (xs `mplus` ys)- Susp xs `mplus` Susp ys = suspended (xs `mplus` ys)--instance Applicative Stream where- pure = Single-- Nil <*> _ = Nil- Single f <*> xs = fmap f xs- Cons f fs <*> xs = fmap f xs <|> (xs <**> fs)- Susp fs <*> xs = suspended (xs <**> fs)--instance Alternative Stream where- empty = Nil- (<|>) = mplus
+ src/Control/Monad/Stream.hs view
@@ -0,0 +1,114 @@+-- |+-- Module : Control.Monad.Stream+-- Copyright : Oleg Kiselyov, Sebastian Fischer+-- License : BSD3+-- +-- Maintainer : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- Stability : experimental+-- Portability : portable+-- +-- This Haskell library provides an implementation of the MonadPlus+-- type class that enumerates results of a non-deterministic+-- computation by interleaving subcomputations in a way that has+-- usually much better memory performance than other strategies with+-- the same termination properties.+-- +-- By using supensions in strategic positions, the user can ensure+-- that the search does not diverge if there are remaining+-- non-deterministic results.+-- +-- More information is available on the authors website:+-- <http://okmij.org/ftp/Computation/monads.html#fair-bt-stream>+-- +-- Warning: @Stream@ is only a monad when the results of @runStream@+-- are interpreted as a multiset, i.e., a valid transformation+-- according to the monad laws may change the order of the results.+-- +module Control.Monad.Stream ( Stream, suspended, runStream, toList ) where++import Control.Monad+import Control.Applicative+import Control.Monad.Logic+import Data.Foldable+import Data.Traversable+import Prelude hiding (foldr)++-- |+-- Results of non-deterministic computations of type @Stream a@ can be+-- enumerated efficiently.+-- +data Stream a = Nil | Single a | Cons a (Stream a) | Susp (Stream a)++instance Functor Stream+ where+ fmap _ Nil = Nil+ fmap f (Single x) = Single (f x)+ fmap f (Cons x xs) = Cons (f x) (fmap f xs)+ fmap f (Susp xs) = Susp (fmap f xs)++-- |+-- Suspensions can be used to ensure fairness.+-- +suspended :: Stream a -> Stream a+suspended = Susp++-- |+-- The function @runStream@ enumerates the results of a+-- non-deterministic computation.+-- +runStream :: Stream a -> [a]+runStream = toList+{-# DEPRECATED runStream "use toList" #-}++instance Monad Stream+ where+ return = Single++ Nil >>= _ = Nil+ Single x >>= f = f x+ Cons x xs >>= f = f x `mplus` suspended (xs >>= f)+ Susp xs >>= f = suspended (xs >>= f)++ fail _ = Nil++instance MonadPlus Stream+ where+ mzero = Nil++ Nil `mplus` ys = suspended ys -- suspending+ Single x `mplus` ys = Cons x ys+ Cons x xs `mplus` ys = Cons x (ys `mplus` xs) -- interleaving+ xs `mplus` Nil = xs+ Susp xs `mplus` Single y = Cons y xs+ Susp xs `mplus` Cons y ys = Cons y (xs `mplus` ys)+ Susp xs `mplus` Susp ys = suspended (xs `mplus` ys)++instance Applicative Stream where+ pure = Single++ Nil <*> _ = Nil+ Single f <*> xs = fmap f xs+ Cons f fs <*> xs = fmap f xs <|> (xs <**> fs)+ Susp fs <*> xs = suspended (xs <**> fs)++instance Alternative Stream where+ empty = Nil+ (<|>) = mplus++instance MonadLogic Stream where+ (>>-) = (>>=)+ interleave = mplus++ msplit Nil = return Nothing+ msplit (Single x) = return $ Just (x, Nil)+ msplit (Cons x xs) = return $ Just (x, suspended xs)+ msplit (Susp xs) = suspended $ msplit xs++instance Foldable Stream where+ foldMap = foldMapDefault++instance Traversable Stream where+ traverse _ Nil = pure Nil+ traverse f (Single x) = Single <$> f x+ traverse f (Cons x xs) = Cons <$> f x <*> traverse f xs+ traverse f (Susp xs) = Susp <$> traverse f xs
+ src/benchmarks.hs view
@@ -0,0 +1,39 @@+import Criterion.Main+import Control.Monad+import Control.Monad.Stream++main :: IO ()+main = defaultMain+ [ bench "permsort" $ nf (toList . permSort) ([1..4]++[8,7..5]),+ bench "8 queens" $ nf (toList . nQueens) 8 ]++permSort :: [Int] -> Stream [Int]+permSort xs = do ys <- permute xs+ guard (ascending ys)+ return ys++permute :: [a] -> Stream [a]+permute [] = return []+permute xs = do (y,ys) <- select xs+ zs <- permute ys+ return (y:zs)++select :: [a] -> Stream (a,[a])+select [] = mzero+select (x:xs) = return (x,xs)+ `mplus` do (y,ys) <- select xs+ return (y,x:ys)++ascending :: [Int] -> Bool+ascending [] = True+ascending [_] = True+ascending (x:y:zs) = x <= y && ascending (y:zs)++nQueens :: Int -> Stream [Int]+nQueens n = do qs <- permute [1..n]+ guard (safe qs)+ return qs++safe :: [Int] -> Bool+safe qs = and [ j-i /= abs (qj-qi) | (i,qi) <- iqs, (j,qj) <- iqs, i < j ]+ where iqs = zip [1..] qs
stream-monad.cabal view
@@ -1,5 +1,5 @@ Name: stream-monad-Version: 0.3+Version: 0.4 Cabal-Version: >= 1.6 Synopsis: Simple, Fair and Terminating Backtracking Monad Description: This Haskell library provides an implementation of the@@ -21,9 +21,26 @@ Extra-Source-Files: README Library- Build-Depends: base >= 3 && < 5+ Build-Depends: base >= 3 && < 5,+ logict >= 0.4 && < 0.5+ HS-Source-Dirs: src Exposed-Modules: Control.Monad.Stream Ghc-Options: -Wall++Flag Benchmarks+ Description: Build executable to run benchmarks+ Default: False++Executable stream-monad-benchmarks+ Main-Is: benchmarks.hs+ If flag(Benchmarks)+ Build-Depends: base >= 3 && < 5,+ logict >= 0.4 && < 0.5,+ criterion >= 0.5 && < 0.6+ Else+ Buildable: False+ HS-Source-Dirs: src+ Other-Modules: Control.Monad.Stream Source-Repository head type: git