nondeterminism (empty) → 1.0

raw patch · 5 files changed

+476/−0 lines, 5 filesdep +basedep +containersdep +mtlsetup-changed

Dependencies added: base, containers, mtl

Files

• Control/Monad/Amb.hs +260/−0
• LICENSE +165/−0
• README.md +24/−0
• Setup.lhs +4/−0
• nondeterminism.cabal +23/−0

@@ -0,0 +1,260 @@+{-# LANGUAGE RankNTypes #-}++module Control.Monad.Amb+       (+         -- * Overview+         -- $overview++         -- * Creating computations+         amb,+         aPartitionOfSize,+         aPartitionOf,+         aPermutationOf,+         aSplitOf,+         anIntegerBetween,+         aSubsetOf,+         aMemberOf,+         aBoolean,+         fail',+         either',+         -- * Running computations+         isPossible,+         isPossibleT,+         isNecessary,+         isNecessaryT,+         allValues,+         allValuesT,+         oneValue,+         oneValueT,+         -- * Low-level internals+         tell',+         tellState,+         uponFailure,+         runAmbT,+         runAmbTI,+         ambCC,+         forEffects,+         -- * Types+         AmbT(..),+         AmbT',+         Amb,+         Amb'+       ) where+import Control.Monad.Cont+import Control.Monad.State.Strict+import Control.Monad.Identity+import Data.Monoid++-- $overview+--+-- A nondeterministic computation makes a series of choices which it+-- can then backtrack to. As an example, here is a program which+-- computes Pythagorean triples of a certain size.+--+-- @+--import Control.Monad+--import Control.Monad.Amb+--+--pyTriple :: (Num t, Ord t) => t -> Amb r (t, t, t)+--pyTriple n = do a <- 'anIntegerBetween' 1 n+--                b <- 'anIntegerBetween' (a + 1) n+--                c <- 'anIntegerBetween' (b + 1) n+--                when (a*a + b*b /= c*c) 'fail''+--                return (a,b,c)+-- @+--+-- You can run this computation and ask for one or more of its+-- possible values.+--+-- >>> oneValue $ pyTriple 20+-- (3,4,5)+--+-- >>> allValues $ pyTriple 20+-- [(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)]++-- | @AmbT r m a@ is a computation whose current value is of type @a@+-- and which will ultimately return a value of type @r@. The same as+-- @ContT@.+data AmbT r m a = AmbT { +  {- | From left to right:++       * the computation to run on failure+       +       * the continuation captured when making nondeterministic choices++       * record keeping of solutions found so far+ -}+  unAmbT ::+     StateT (AmbT r m r)+     (ContT r            +      (StateT [r] m))+     a }++type Amb r = AmbT r Identity+type AmbT' m a = forall r. AmbT r m a+type Amb' a = AmbT' Identity a++instance MonadTrans (AmbT r) where+    lift = AmbT . lift . lift . lift++instance (Monad m) => Monad (AmbT r m) where+    AmbT a >>= b = AmbT $ a >>= unAmbT . b+    return = AmbT . return++-- Internals++-- | call/cc lifted into the nondeterministic monad. This implements+-- the backtracking behaviour which allows Amb to try different code+-- paths and return multiple results.+ambCC :: ((a -> AmbT r m a1) -> AmbT r m a) -> AmbT r m a+ambCC f = AmbT $ callCC $ \k -> unAmbT $ f $ AmbT . k++-- | Run the nondeterministic computation. This is internal.+runAmbTI :: Monad m => AmbT a m a -> AmbT a m a -> m (a, [a])+runAmbTI (AmbT a) i = runStateT (runContT (evalStateT a i) return) []++-- | Run the nondeterministic computation. This is internal.+runAmbT :: Monad m => AmbT t m t -> m (t, [t])+runAmbT a = runAmbTI a (error "top-level fail")++-- | When the nondeterministic computation backtracks past this state,+-- execute this nondeterministic computation. Generally used to undo+-- side effects.+uponFailure :: Monad m => AmbT r m a -> AmbT r m ()+uponFailure f = do+  old <- AmbT get+  AmbT $ put (f >> old)++-- | A helper to inject state into the backtracking stack+tellState :: (Monoid s, MonadState s m) => s -> m ()+tellState b = do+  a <- get+  put $ a `mappend` b++-- | A helper to inject state into the backtracking stack+tell' :: Monad m => [r] -> AmbT r m ()+tell' t = AmbT $ (lift $ lift $ tellState t)++-- | A low-level internal function which executes a nondeterministic+-- computation for its nondeterministic side-effects, such as its+-- ability to produce different results.+forEffects :: Monad m => ((t, [t]) -> r) -> (t1 -> AmbT t m t) -> AmbT t m t1 -> m r+forEffects f g e = f `liftM` runAmbTI (do ambCC $ \k -> do+                                            AmbT $ put (k undefined)+                                            v <- e+                                            g v)+                                      (return undefined)++-- Run nondeterministic computations++-- | Run a nondeterministic computation and return a result of that+-- computation.+oneValueT :: Monad m => AmbT b m b -> m b+oneValueT c = runAmbT c >>= return . fst++-- | Run a nondeterministic computation and return a result of that+-- computation.+oneValue :: Amb a a -> a+oneValue = runIdentity . oneValueT++-- | Run a nondeterministic computation and return a list of all+-- results that the computation can produce. Note that this function+-- is not lazy its result.+allValuesT :: Monad m => AmbT t m t -> m [t]+allValuesT = forEffects snd (\a -> tell' [a] >> fail')++-- | Run a nondeterministic computation and return a list of all+-- results that the computation can produce. Note that this function+-- is not lazy its result.+allValues :: Amb t t -> [t]+allValues = runIdentity . allValuesT++-- | Run a nondeterministic computation and return @True@+-- if any result is @True@, @False@ otherwise.+isPossibleT :: Monad m => AmbT Bool m Bool -> m Bool+isPossibleT = forEffects (([True] ==) . snd) (\a -> when (a == False) fail' >> tell' [True] >> return undefined)++-- | Run a nondeterministic computation and return @True@+-- if any result is @True@, @False@ otherwise.+isPossible :: Amb Bool Bool -> Bool+isPossible = runIdentity . isPossibleT++-- | Run a nondeterministic computation and return @True@+-- if all possible results are @True@, @False@ otherwise.+isNecessaryT :: Monad m => AmbT Bool m Bool -> m Bool+isNecessaryT = forEffects (([] ==) . snd) (\a -> when (a == True) fail' >> tell' [True] >> return undefined)++-- | Run a nondeterministic computation and return @True@+-- if all possible results are @True@, @False@ otherwise.+isNecessary :: Amb Bool Bool -> Bool+isNecessary = runIdentity . isNecessaryT++-- Generate nondeterministic computations++-- | Nondeterministically choose either of the two computations+either' :: Monad m => AmbT r m b -> AmbT r m b -> AmbT r m b+either' a b = do r <- aBoolean+                 if r then a else b++-- | Terminate this branch of the computation.+fail' :: Monad m => AmbT r m b+fail' = AmbT get >>= (\a -> a >> return undefined)++-- | The most basic primitive that everything else is built out+-- of. Generates @True@ and @False@.+aBoolean :: Monad m => AmbT r m Bool+aBoolean = ambCC $ \k -> do+             old <- AmbT get+             AmbT $ put (AmbT (put old) >> (k False) >> undefined)+             return True++-- | Generate each element of the given list.+aMemberOf :: Monad m => [b] -> AmbT r m b+aMemberOf [] = fail'+aMemberOf (x:xs) =  return x `either'` aMemberOf xs++-- | Generate each subset of any size from the given list.+aSubsetOf :: Monad m => [AmbT r m a] -> AmbT r m [a]+aSubsetOf [] = return []+aSubsetOf (x:xs) = aSubsetOf xs `either'` liftM2 (:) x (aSubsetOf xs)++-- | Generate all numbers between the given bounds, inclusive.+anIntegerBetween :: (Monad m, Num b, Ord b) => b -> b -> AmbT r m b+anIntegerBetween i j | i > j = fail'+                     | otherwise = either' (return i) (anIntegerBetween (i + 1) j) ++-- | Generate all splits of a list.+aSplitOf :: Monad m => [a] -> AmbT r m ([a],[a])+aSplitOf l = loop [] l+    where loop x [] = return (x,[])+          loop x y@(y0:ys)  = either' (return (x,y)) (loop (x ++ [y0]) ys)++-- | Generate all permutations of a list.+aPermutationOf :: Monad m => [a] -> AmbT r m [a]+aPermutationOf [] = return []+aPermutationOf (l0:ls) = do (s1,s2) <- (aPermutationOf ls >>= aSplitOf)+                            return $ s1 ++ (l0:s2)++-- | Generate all partitions of this list.+aPartitionOf :: (Eq t, Monad m) => [t] -> AmbT r m [[t]]+aPartitionOf [] = return []+aPartitionOf (x:xs) = do y <- aPartitionOf xs+                         either' (return ([x]:y))+                                 (do z <- aMemberOf y+                                     return ((x:z) : filter (z /=) y))++-- | Generate all partitions of a given size of this list.+aPartitionOfSize :: (Eq a, Monad m) => Int -> [a] -> AmbT r m [[a]]+aPartitionOfSize 0 _ = error "Can't create a partition of size 0"+aPartitionOfSize k l | length l < k = fail'+                     | otherwise = loop l+    where loop x@(x0:xs) | length x == k = return $ map (:[]) x+                         | otherwise = do y <- loop xs+                                          z <- aMemberOf y+                                          return ((x0:z):filter (z /=) y)+          loop [] = fail'++-- | Just for fun. This is McCarthy's @amb@ operator and is a synonym+-- for @aMemberOf@.+amb :: Monad m => [b] -> AmbT r m b+amb = aMemberOf

@@ -0,0 +1,165 @@+		   GNU LESSER GENERAL PUBLIC LICENSE+                       Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.+++  This version of the GNU Lesser General Public License incorporates+the terms and conditions of version 3 of the GNU General Public+License, supplemented by the additional permissions listed below.++  0. Additional Definitions. ++  As used herein, "this License" refers to version 3 of the GNU Lesser+General Public License, and the "GNU GPL" refers to version 3 of the GNU+General Public License.++  "The Library" refers to a covered work governed by this License,+other than an Application or a Combined Work as defined below.++  An "Application" is any work that makes use of an interface provided+by the Library, but which is not otherwise based on the Library.+Defining a subclass of a class defined by the Library is deemed a mode+of using an interface provided by the Library.++  A "Combined Work" is a work produced by combining or linking an+Application with the Library.  The particular version of the Library+with which the Combined Work was made is also called the "Linked+Version".++  The "Minimal Corresponding Source" for a Combined Work means the+Corresponding Source for the Combined Work, excluding any source code+for portions of the Combined Work that, considered in isolation, are+based on the Application, and not on the Linked Version.++  The "Corresponding Application Code" for a Combined Work means the+object code and/or source code for the Application, including any data+and utility programs needed for reproducing the Combined Work from the+Application, but excluding the System Libraries of the Combined Work.++  1. Exception to Section 3 of the GNU GPL.++  You may convey a covered work under sections 3 and 4 of this License+without being bound by section 3 of the GNU GPL.++  2. Conveying Modified Versions.++  If you modify a copy of the Library, and, in your modifications, a+facility refers to a function or data to be supplied by an Application+that uses the facility (other than as an argument passed when the+facility is invoked), then you may convey a copy of the modified+version:++   a) under this License, provided that you make a good faith effort to+   ensure that, in the event an Application does not supply the+   function or data, the facility still operates, and performs+   whatever part of its purpose remains meaningful, or++   b) under the GNU GPL, with none of the additional permissions of+   this License applicable to that copy.++  3. Object Code Incorporating Material from Library Header Files.++  The object code form of an Application may incorporate material from+a header file that is part of the Library.  You may convey such object+code under terms of your choice, provided that, if the incorporated+material is not limited to numerical parameters, data structure+layouts and accessors, or small macros, inline functions and templates+(ten or fewer lines in length), you do both of the following:++   a) Give prominent notice with each copy of the object code that the+   Library is used in it and that the Library and its use are+   covered by this License.++   b) Accompany the object code with a copy of the GNU GPL and this license+   document.++  4. Combined Works.++  You may convey a Combined Work under terms of your choice that,+taken together, effectively do not restrict modification of the+portions of the Library contained in the Combined Work and reverse+engineering for debugging such modifications, if you also do each of+the following:++   a) Give prominent notice with each copy of the Combined Work that+   the Library is used in it and that the Library and its use are+   covered by this License.++   b) Accompany the Combined Work with a copy of the GNU GPL and this license+   document.++   c) For a Combined Work that displays copyright notices during+   execution, include the copyright notice for the Library among+   these notices, as well as a reference directing the user to the+   copies of the GNU GPL and this license document.++   d) Do one of the following:++       0) Convey the Minimal Corresponding Source under the terms of this+       License, and the Corresponding Application Code in a form+       suitable for, and under terms that permit, the user to+       recombine or relink the Application with a modified version of+       the Linked Version to produce a modified Combined Work, in the+       manner specified by section 6 of the GNU GPL for conveying+       Corresponding Source.++       1) Use a suitable shared library mechanism for linking with the+       Library.  A suitable mechanism is one that (a) uses at run time+       a copy of the Library already present on the user's computer+       system, and (b) will operate properly with a modified version+       of the Library that is interface-compatible with the Linked+       Version. ++   e) Provide Installation Information, but only if you would otherwise+   be required to provide such information under section 6 of the+   GNU GPL, and only to the extent that such information is+   necessary to install and execute a modified version of the+   Combined Work produced by recombining or relinking the+   Application with a modified version of the Linked Version. (If+   you use option 4d0, the Installation Information must accompany+   the Minimal Corresponding Source and Corresponding Application+   Code. If you use option 4d1, you must provide the Installation+   Information in the manner specified by section 6 of the GNU GPL+   for conveying Corresponding Source.)++  5. Combined Libraries.++  You may place library facilities that are a work based on the+Library side by side in a single library together with other library+facilities that are not Applications and are not covered by this+License, and convey such a combined library under terms of your+choice, if you do both of the following:++   a) Accompany the combined library with a copy of the same work based+   on the Library, uncombined with any other library facilities,+   conveyed under the terms of this License.++   b) Give prominent notice with the combined library that part of it+   is a work based on the Library, and explaining where to find the+   accompanying uncombined form of the same work.++  6. Revised Versions of the GNU Lesser General Public License.++  The Free Software Foundation may publish revised and/or new versions+of the GNU Lesser General Public License from time to time. Such new+versions will be similar in spirit to the present version, but may+differ in detail to address new problems or concerns.++  Each version is given a distinguishing version number. If the+Library as you received it specifies that a certain numbered version+of the GNU Lesser General Public License "or any later version"+applies to it, you have the option of following the terms and+conditions either of that published version or of any later version+published by the Free Software Foundation. If the Library as you+received it does not specify a version number of the GNU Lesser+General Public License, you may choose any version of the GNU Lesser+General Public License ever published by the Free Software Foundation.++  If the Library as you received it specifies that a proxy can decide+whether future versions of the GNU Lesser General Public License shall+apply, that proxy's public statement of acceptance of any version is+permanent authorization for you to choose that version for the+Library.

@@ -0,0 +1,24 @@+# Nondeterminism++This provides nondeterministic computations in Haskell. It implements+an `Amb` monad in which you can perform nondeterministic choices along+with a monad transformer version, `AmbT`.++## Amb++An example which finds Pythagorean triplets up to a certain size, project Euler problem 9.++    import Control.Monad+    import Control.Monad.Amb+    pyTriple :: (Num t, Ord t) => t -> Amb r (t, t, t)+    pyTriple n = do a <- anIntegerBetween 1 n+                    b <- anIntegerBetween (a + 1) n+                    c <- anIntegerBetween (b + 1) n+                    when (a*a + b*b /= c*c) fail'+                    return (a,b,c)++    length $ allValues $ pyTriple 10000++## Future++ - Docs!

@@ -0,0 +1,4 @@+#! /usr/bin/env runhaskell++> import Distribution.Simple+> main = defaultMain

@@ -0,0 +1,23 @@+Name:                nondeterminism+Version:             1.0+Description:         Nondeterministic computations+License:             LGPL+License-file:        LICENSE+Author:              Andrei Barbu <andrei@0xab.com>+Maintainer:          Andrei Barbu <andrei@0xab.com>+Category:            Control, AI, Constraints, Failure, Monads+Build-Type:          Simple+cabal-version:       >= 1.6+Synopsis:+    A monad and monad transformer for nondeterministic computations.+extra-source-files:  README.md++source-repository head+  type: git+  location: git://github.com/abarbu/nondeterminism-haskell.git++Library+  Build-Depends:     base >= 3 && < 5, mtl >= 2, containers+  Exposed-modules:+                     Control.Monad.Amb+  ghc-options:       -Wall