On Fri, Oct 3, 2008 at 3:43 PM, Andrew Coppin <[EMAIL PROTECTED]> wrote: > David Menendez wrote: >> >> It wasn't until fairly recently that people realized >> that you could do useful things if you had "return" and "ap", but not >> (>>=), which why we have some unfortunate limitations in the Haskell >> prelude, like Applicative not being a superclass of Monad. >> >> This leads to all the duplication between Applicative and Monad. In a >> perfect world, we would only need the Applicative versions. >> > > OK. So it's broken "for compatibility" then? (Presumably any time you change > something from the Prelude, mass breakage ensues!)
Exactly. Since the Prelude is specified in the Haskell 98 report, you can't add or subtract things without losing Haskell 98 compatibility. We *could* define a new Prelude that did things more sensibly, but then code either has to pick which Prelude to support or else jump through extra hoops to be cross-compatible. >> Would you be willing to share the implementation of ResultSet? If >> you're relying on a list somewhere, then it should be possible to >> switch the implementation to one of the nondeterminism monad >> transformers, which would give you the exception behavior you want. >> > > Consider the following: > > factorise n = do > x <- [1..] > y <- [1..] > if x*y == n then return (x,y) else fail "not factors" > > This is a very stupid way to factorise an integer. (But it's also very > general...) As you may already be aware, this fails miserably because it > tries all possible values for y before trying even one new value for x. And > since both lists there are infinite, this causes an endless loop that > produces (almost) nothing. > > My ResultSet monad works the same way as a list, except that the above > function discovers all finite solutions in finite time. The result is still > infinite, but all the finite solutions are within a finite distance of the > beginning. Achieving this was Seriously Non-Trivial. (!) As in, it's several > pages of seriously freaky code that took me days to develop. > > AFAIK, nothing like this already exists in the standard libraries. Now I'm even more curious to see how you did it. I spent some time a few months ago developing a monad that does breadth-first search. It would be able to handle the example you gave almost without change. Some other possibilities: (1) logict <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict> This defines a backtracking monad transformer (the NondetT I mentioned in my previous message), and provides a "fair" variant of (>>=) that you could use to define factorise. It's not as foolproof as the other options. (2) control-monad-omega <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-omega> This is a monad similar to [] that uses a "diagonal" search pattern. (3) Oleg Kiselyov's fair and backtracking monad <http://okmij.org/ftp/Computation/monads.html#fair-bt-stream> This uses a search pattern that I don't fully understand, and only satisfies the Monad and MonadPlus laws if you ignore the order of results, but think it's at least as robust as Omega. >>> If you look at run_or, you'll see that this is _not_ a simple state >>> monad, >>> as in that function I run two actions starting from _the same_ initial >>> state >>> - something which, AFAIK, is impossible (or at least very awkward) with a >>> state monad. >>> >>> Really, it's a function that takes a state and generates a new state, but >>> it >>> may also happen to generate *multiple* new states. It also consumes a Foo >>> or >>> two in the process. >>> >> >> That's what happens if you apply a state monad transformer to a >> nondeterminism monad. >> >> So it might be possible to rewrite your code along these lines: >> >> type M = StateT State [] >> >> run :: Foo -> M () >> >> runOr :: Foo -> Foo -> M () >> runOr x y = mplus (run x) (run y) >> >> runAnd :: Foo -> Foo -> M () >> runAnd x y = run x >> run y >> >> The type "StateT State [] alpha" is isomorphic to "State -> [(alpha, >> State)]", which means that each of the computations in mplus gets its >> own copy of the state. >> > > What does mplus do in this case? (I know what it does for Maybe, but not for > any other monad.) "mplus a b" returns all the results returned by "a" and "b". For lists, it returns all the results of "a" before the results of "b". I suspect it corresponds to "merge" in your code. For true backtracking monads (that is, not Maybe), mplus also has this property: mplus a b >>= f == mplus (a >>= f) (b >>= f) There is a school of thought that Maybe (and Error/ErrorT) should not be instances of MonadPlus because they do not satisfy that law. >> 2. StateT State (NondetT (Either ErrorType)) alpha >> >> (NondetT isn't in the standard libraries, but I can provide code if >> needed.) >> >> Left uncaught, an exception raised in any branch will cause all >> branches to fail. >> > > That looks more like it, yes. That's what I figured. You'll need a transformer, then, which rules out Omega. Since you don't care about catching exceptions, you can just do something like type M = StateT State (LogicT (Either ErrorType)) throwM :: ErrorType -> M a throwM = lift . lift . Left Or, if you want to try my breadth-first monad, I can send you a copy. It supports exception handling out of the box. -- Dave Menendez <[EMAIL PROTECTED]> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
