<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>I did not know about ChoiceT.</div><div><br></div><div>It does offer the same basic functionality:</div><div><span class="Apple-style-span" style="font-family: Times; "><pre><span class="definition">runChoiceT</span> <span class="keyglyph" style="color: red; ">::</span> <span class="layout" style="color: red; ">(</span><span class="conid">Monad</span> <span class="varid">m</span><span class="layout" style="color: red; ">)</span> <span class="keyglyph" style="color: red; ">=></span> <span class="conid">ChoiceT</span> <span class="varid">m</span> <span class="varid">a</span> <span class="keyglyph" style="color: red; ">-></span> <span class="varid">m</span> <span class="layout" style="color: red; ">(</span><span class="conid">Maybe</span> <span class="layout" style="color: red; ">(</span><span class="varid">a</span><span class="layout" style="color: red; ">,</span><span class="conid">ChoiceT</span> <span class="varid">m</span> <span class="varid">a</span><span class="layout" style="color: red; ">)</span><span class="layout" style="color: red; ">)</span></pre></span></div><div>runChoiceT is equivalent to my runListT, and for the "Hamurabi" example ChoiceT would work just as well as ListT.</div><div><br></div><div>An interesting thing is that I arrived to ListT from a totally different perpective:</div><div>A monadic list as an alternative to Lazy IO and Iteratee (I'm not claiming this provides everything Iteratee does).</div><div>That's what brought me to implement scanl, takeWhile, and other list operations for ListT.</div><div><br></div><div>Other related monads:</div><div><br></div><div>Sebastian Fisher's "Reinventing Haskell Backtracking" (<a href="http://www-ps.informatik.uni-kiel.de/~sebf/pub/atps09.html">http://www-ps.informatik.uni-kiel.de/~sebf/pub/atps09.html</a>)</div><div>seems to be similar (I think).</div><div>and Dan Piponi's PList monad (<a href="http://blog.sigfpe.com/2009/07/monad-for-combinatorial-search-with.html)">http://blog.sigfpe.com/2009/07/monad-for-combinatorial-search-with.html)</a></div><div>offers a similar functionality to my bestFirstSeachSortedChildrenOn function</div><div>(<a href="http://hackage.haskell.org/packages/archive/generator/0.5.1/doc/html/Data-List-Tree.html#v%3AbestFirstSearchSortedChildrenOn">http://hackage.haskell.org/packages/archive/generator/0.5.1/doc/html/Data-List-Tree.html#v%3AbestFirstSearchSortedChildrenOn</a>).</div><div><span class="Apple-style-span" style="font-family: sans-serif; "><pre style="font-size: 12px; ">pythagorianTriplets =
catMaybes .
fmap fst .
bestFirstSearchSortedChildrenOn snd .
generate $ do
x <- lift [1..]
yield (Nothing, x)
y <- lift [1..]
yield (Nothing, x + y)
z <- lift [1..]
yield (Nothing, x + y + z)
lift . guard $ x^2 + y^2 == z^2
yield (Just (x, y, z), 0)
> print $ take 10 pythagorianTriplets
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(15,8,17),(8,15,17)]</pre></span></div>cheers,<div>Yair</div><div><br><div><div>On Jul 16, 2009, at 12:24 AM, Sjoerd Visscher wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>This sounds similar to ChoiceT from the monadLib package. Did you know ChoiceT?</div><div><br></div><div>greetings,</div><div>Sjoerd</div><br><div><div>On Jul 15, 2009, at 3:33 PM, Yair Chuchem wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>A new "generator" package has been uploaded to Hackage.</div><div><br></div><div>It implements an alternative list monad transformer, a list class, and related functions.</div><div><br></div><div>The difference from mtl/transformers's ListT is that</div><div><div>mtl is a monadic action that returns a list:</div><div><span class="Apple-style-span" style="font-family: monospace; white-space: pre; "><span class="keyword" style="color: blue; ">newtype</span> <span class="conid">ListT</span> <span class="varid">m</span> <span class="varid">a</span> <span class="keyglyph" style="color: red; ">=</span> <span class="conid">ListT</span> <span class="layout" style="color: red; ">{</span> <span class="varid">runListT</span> <span class="keyglyph" style="color: red; ">::</span> <span class="varid">m</span> <span class="keyglyph" style="color: red; ">[</span><span class="varid">a</span><span class="keyglyph" style="color: red; ">]</span> <span class="layout" style="color: red; ">}</span></span></div><pre><font class="Apple-style-span" color="#FF0000"><span class="Apple-style-span" style="color: rgb(0, 0, 0); font-family: Helvetica; white-space: normal; "><div>generator's is a monadic list:</div><div><span class="Apple-style-span" style="font-family: monospace; white-space: pre; "><span class="keyword" style="color: blue; ">data</span> <span class="conid">ListItem</span> <span class="varid">l</span> <span class="varid">a</span> <span class="keyglyph" style="color: red; ">=<span class="Apple-style-span" style="color: rgb(0, 0, 0); "> <span class="conid">Nil</span> <span class="keyglyph" style="color: red; ">|<span class="Apple-style-span" style="color: rgb(0, 0, 0); "> <span class="conid">Cons</span> <span class="layout" style="color: red; ">{</span> <span class="varid">headL</span> <span class="keyglyph" style="color: red; ">::</span> <span class="varid">a</span><span class="layout" style="color: red; ">,</span> <span class="varid">tailL</span> <span class="keyglyph" style="color: red; ">::</span> <span class="varid">l</span> <span class="varid">a</span> <span class="layout" style="color: red; ">}</span></span></span></span></span></span></div></span></font></pre><pre><font class="Apple-style-span" color="#FF0000"><span class="Apple-style-span" style="color: rgb(0, 0, 0); font-family: Times; white-space: normal; "><pre><a name="line-41"></a><a name="ListT"></a><span class="keyword" style="color: blue; ">newtype</span> <span class="conid">ListT</span> <span class="varid">m</span> <span class="varid">a</span> <span class="keyglyph" style="color: red; ">=</span> <span class="conid">ListT</span> <span class="layout" style="color: red; ">{</span> <span class="varid">runListT</span> <span class="keyglyph" style="color: red; ">::</span> <span class="varid">m</span> <span class="layout" style="color: red; ">(</span><span class="conid">ListItem</span> <span class="layout" style="color: red; ">(</span><span class="conid">ListT</span> <span class="varid">m</span><span class="layout" style="color: red; ">)</span> <span class="varid">a</span><span class="layout" style="color: red; ">)</span> <span class="layout" style="color: red; ">}</span>
</pre><div><font class="Apple-style-span" color="#FF0000" face="monospace"><span class="Apple-style-span" style="white-space: pre; "><span class="Apple-style-span" style="color: rgb(0, 0, 0); font-family: Helvetica; white-space: normal; "><div>A short example program which reads numbers from the user and interactively sums them up:</div><div><span class="Apple-style-span" style="font-family: sans-serif; "><pre style="font-size: 13px; "><span class="Apple-style-span" style="font-family: sans-serif; font-size: medium; white-space: normal; "><pre style="font-size: 12px; ">import Control.Monad.ListT (ListT)
import Data.List.Class (execute, joinM, repeat, scanl, takeWhile)
import Prelude hiding (repeat, scanl, takeWhile)
main =
execute . joinM . fmap print .
scanl (+) 0 .
fmap (fst . head) .
takeWhile (not . null) .
fmap reads .
joinM $ (repeat getLine :: ListT IO (IO String))</pre><pre style="font-size: 13px; "><span class="Apple-style-span" style="font-family: Helvetica; font-size: medium; white-space: normal; "><div>I also wrote an example/blog-post about using ListT to add an undo option to the classic game of "hamurabi":</div><div><a href="http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.html">http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.html</a></div><div><br></div><div>Another interesting observation is that "ListT [] a" is a tree of "a"s.</div><div>The module Data.List.Tree includes functions to prune and search such trees (dfs, bfs, bestFirstSearchOn, etc).</div><div>This can be useful for modularizing code that uses the list monad for combinatoric search by decoupling tree creation from processing and pruning.</div><div><br></div></span></pre></span></pre></span></div></span></span></font></div></span></font></pre></div></div>_______________________________________________<br>Haskell mailing list<br><a href="mailto:Haskell@haskell.org">Haskell@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell">http://www.haskell.org/mailman/listinfo/haskell</a><br></blockquote></div><br><div apple-content-edited="true"> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>--</div><div>Sjoerd Visscher</div><div><a href="mailto:sjoerd@w3future.com">sjoerd@w3future.com</a></div><div><br></div></div></span><br class="Apple-interchange-newline"> </div><br></div></blockquote></div><br></div></body></html>