stream-monad (empty) → 0.1

raw patch · 5 files changed

+142/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

• Control/Monad/Stream.hs +80/−0
• LICENSE +15/−0
• README +13/−0
• Setup.hs +4/−0
• stream-monad.cabal +30/−0

@@ -0,0 +1,80 @@+-- |+-- Module      : Control.Monad.Stream+-- Copyright   : Oleg Kiselyov+-- License     : PublicDomain+-- +-- 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++-- |+-- 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)++-- |+-- 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)++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+  Susp xs   `mplus` ys = ys `splus` xs            -- using `splus`++-- The function `splus` is similar to `mplus` but suspends its result+-- if the first argument is a suspension. It uses `mplus` in recursive+-- calls.+--+splus :: Stream a -> Stream a -> Stream a+Nil       `splus` ys = suspended ys+Single x  `splus` ys = Cons x ys+Cons x xs `splus` ys = Cons x (ys `mplus` xs)+Susp xs   `splus` ys = suspended (ys `mplus` xs)  -- suspending+

@@ -0,0 +1,15 @@+ALL PUBLIC DOMAIN MATERIAL IS OFFERED AS-IS. NO REPRESENTATIONS OR+WARRANTIES OF ANY KIND ARE MADE CONCERNING THE MATERIALS, EXPRESS,+IMPLIED, STATUTORY OR OTHERWISE, INCLUDING, WITHOUT LIMITATION,+WARRANTIES OF TITLE, MERCHANTIBILITY, FITNESS FOR A PARTICULAR+PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT OR OTHER DEFECTS,+ACCURACY, OR THE PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT+DISCOVERABLE.++IN NO EVENT WILL THE AUTHOR(S), PUBLISHER(S), OR PRESENTER(S) OF ANY+PUBLIC DOMAIN MATERIAL BE LIABLE TO YOU ON ANY LEGAL THEORY FOR ANY+SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY DAMAGES+ARISING OUT OF THIS LICENSE OR THE USE OF THE WORK, EVEN IF THE+AUTHOR(S), PUBLISHER(S), OR PRESENTER(S) HAVE BEEN ADVISED OF THE+POSSIBILITY OF SUCH DAMAGES.+

@@ -0,0 +1,13 @@+Simple, Fair and Terminating Backtracking Monad+===============================================++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.++More information is available on the authors website:++    http://okmij.org/ftp/Computation/monads.html#fair-bt-stream+

@@ -0,0 +1,4 @@+import Distribution.Simple++main = defaultMain+

@@ -0,0 +1,30 @@+Name:          stream-monad+Version:       0.1+Cabal-Version: >= 1.6+Synopsis:      Simple, Fair and Terminating Backtracking Monad+Description:   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.+Category:      Control, Monads+License:       PublicDomain+License-File:  LICENSE+Author:        Oleg Kiselyov+Maintainer:    Sebastian Fischer (sebf@informatik.uni-kiel.de)+Bug-Reports:   mailto:sebf@informatik.uni-kiel.de+Homepage:      http://github.com/sebfisch/stream-monad+Build-Type:    Simple+Stability:     experimental++Extra-Source-Files: README++Library+  Build-Depends:    base+  Exposed-Modules:  Control.Monad.Stream+  Ghc-Options:      -Wall++Source-Repository head+  type:     git+  location: git://github.com/sebfisch/stream-monad.git