A new "generator" package has been uploaded to Hackage. It implements an alternative list monad transformer, a list class, and related functions. The difference from mtl/transformers's ListT is that mtl is a monadic action that returns a list: newtype ListT m a = ListT { runListT :: m [a] } generator's is a monadic list: data ListItem l a = Nil | Cons { headL :: a, tailL :: l a } newtype ListT m a = ListT { runListT :: m (ListItem (ListT m) a) } A short example program which reads numbers from the user and interactively sums them up: 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)) I also wrote an example/blog-post about using ListT to add an undo option to the classic game of "hamurabi": http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.htm... Another interesting observation is that "ListT [] a" is a tree of "a"s. The module Data.List.Tree includes functions to prune and search such trees (dfs, bfs, bestFirstSearchOn, etc). This can be useful for modularizing code that uses the list monad for combinatoric search by decoupling tree creation from processing and pruning.
This sounds similar to ChoiceT from the monadLib package. Did you know ChoiceT? greetings, Sjoerd On Jul 15, 2009, at 3:33 PM, Yair Chuchem wrote:
A new "generator" package has been uploaded to Hackage.
It implements an alternative list monad transformer, a list class, and related functions.
The difference from mtl/transformers's ListT is that mtl is a monadic action that returns a list: newtype ListT m a = ListT { runListT :: m [a] } generator's is a monadic list: data ListItem l a = Nil | Cons { headL :: a, tailL :: l a } newtype ListT m a = ListT { runListT :: m (ListItem (ListT m) a) } A short example program which reads numbers from the user and interactively sums them up: 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)) I also wrote an example/blog-post about using ListT to add an undo option to the classic game of "hamurabi": http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.htm...
Another interesting observation is that "ListT [] a" is a tree of "a"s. The module Data.List.Tree includes functions to prune and search such trees (dfs, bfs, bestFirstSearchOn, etc). This can be useful for modularizing code that uses the list monad for combinatoric search by decoupling tree creation from processing and pruning.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Sjoerd Visscher sjoerd@w3future.com
I did not know about ChoiceT. It does offer the same basic functionality: runChoiceT :: (Monad m) => ChoiceT m a -> m (Maybe (a,ChoiceT m a)) runChoiceT is equivalent to my runListT, and for the "Hamurabi" example ChoiceT would work just as well as ListT. An interesting thing is that I arrived to ListT from a totally different perpective: A monadic list as an alternative to Lazy IO and Iteratee (I'm not claiming this provides everything Iteratee does). That's what brought me to implement scanl, takeWhile, and other list operations for ListT. Other related monads: Sebastian Fisher's "Reinventing Haskell Backtracking" (http://www-ps.informatik.uni-kiel.de/~sebf/pub/atps09.html ) seems to be similar (I think). and Dan Piponi's PList monad (http://blog.sigfpe.com/2009/07/monad-for-combinatorial-search-with.html ) offers a similar functionality to my bestFirstSeachSortedChildrenOn function (http://hackage.haskell.org/packages/archive/generator/0.5.1/doc/html/Data-Li... ). 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)] cheers, Yair
On Jul 16, 2009, at 12:24 AM, Sjoerd Visscher wrote:
This sounds similar to ChoiceT from the monadLib package. Did you know ChoiceT?
greetings, Sjoerd
On Jul 15, 2009, at 3:33 PM, Yair Chuchem wrote:
A new "generator" package has been uploaded to Hackage.
It implements an alternative list monad transformer, a list class, and related functions.
The difference from mtl/transformers's ListT is that mtl is a monadic action that returns a list: newtype ListT m a = ListT { runListT :: m [a] } generator's is a monadic list: data ListItem l a = Nil | Cons { headL :: a, tailL :: l a } newtype ListT m a = ListT { runListT :: m (ListItem (ListT m) a) } A short example program which reads numbers from the user and interactively sums them up: 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)) I also wrote an example/blog-post about using ListT to add an undo option to the classic game of "hamurabi": http://mashebali.blogspot.com/2009/07/charlemagne-disraeli-and-jefferson.htm...
Another interesting observation is that "ListT [] a" is a tree of "a"s. The module Data.List.Tree includes functions to prune and search such trees (dfs, bfs, bestFirstSearchOn, etc). This can be useful for modularizing code that uses the list monad for combinatoric search by decoupling tree creation from processing and pruning.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Sjoerd Visscher sjoerd@w3future.com
On Jul 16, 2009, at 12:31 AM, Yair Chuchem wrote:
Sebastian Fisher's "Reinventing Haskell Backtracking" (http://www-ps.informatik.uni-kiel.de/~sebf/pub/atps09.html ) seems to be similar (I think).
The nested monadic tails of your lists seem more similar to the nested monadic data described in the ICFP'09 paper with Oleg Kiselyov and Chung-chieh Shan [1]. The ideas described in that paper are on Hackage and your ListT seems similar to the List type in Data.Monadic.List [2] although our version not only uses monadic tails but also monadic heads. See [3] for a tutorial. Although the types are similar, we arrived at it for yet another purpose.. Cheers, Sebastian [1]: <http://www-ps.informatik.uni-kiel.de/~sebf/pub/icfp09.html> [2]: <http://hackage.haskell.org/packages/archive/explicit-sharing/latest/doc/html...
[3]: <http://sebfisch.github.com/explicit-sharing/> -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)
On Wed, Jul 15, 2009 at 3:33 PM, Yair Chuchem<yairchu@gmail.com> wrote:
A new "generator" package has been uploaded to Hackage. It implements an alternative list monad transformer, a list class, and related functions.
I see you define ListT as a datatype: http://hackage.haskell.org/packages/archive/generator/0.5.1/doc/html/src/Con... Can't you better define it as a newtype and so avoid the overhead of constructing and deconstructing ListTs? Or do you need to worry about strictness? BTW, note that your ListT is also similar to my StreamT: http://code.haskell.org/~basvandijk/code/stream/Control/Monad/StreamT.hs (not on Hackage) regards, Bas
On Jul 16, 2009, at 10:18 AM, Bas van Dijk wrote:
I see you define ListT as a datatype:
http://hackage.haskell.org/packages/archive/generator/0.5.1/doc/html/src/Con...
Can't you better define it as a newtype I should had done that, and next released version will fix it.
BTW, note that your ListT is also similar to my StreamT: http://code.haskell.org/~basvandijk/code/stream/Control/Monad/StreamT.hs (not on Hackage)
It seems like StreamT is an infinite-list version of ListT. another difference is that StreamT redefines scanl, transpose, etc and for ListT I created a List class (for which regular lists are an instance) for which the standard list functions are defined: filter, takeWhile, everything which keeps items in the list for functions which don't keep the item in the list I define similar functions (because the result is in the item monad the type is different) so you can do import Data.List.Class (takeWhile) import Prelude hiding (takeWhile) and still use takeWhile for lists (except maybe mine isn't as efficient as Data.List's and maybe doesn't bring its useful rewrite rules to play) thanks to SequenceT I also found http://www.haskell.org/haskellwiki/ListT_done_right which at its core is just like my ListT
Yair Chuchem wrote:
A new "generator" package has been uploaded to Hackage. It implements an alternative list monad transformer, a list class, and related functions.
This, and just about all of the other "similar" types mentioned in this thread, are all new names for the venerable "ListT Done Right" that has been around for many years: http://www.haskell.org/haskellwiki/ListT_done_right The ListT that is (still, unbelievably) in the mtl package is very broken, and shouldn't be used. It's not even a monad - it doesn't satisfy the monad laws. So why make up new names? Just call it ListT. I agree, ListT is a very nice approach. Perhaps that is why this wheel has been re-invented so many times, many more even than what has been brought up in this thread. Unfortunately, given the way the standard libraries are currently implemented in GHC, ListT IO cannot be made exception-safe, so ListT has limited usefulness for real software. The main problem is the type of the primitives (un)blockAsyncExceptions# which makes it possible to block exceptions only in IO itself, not in transformations of IO. That, in turn, makes it impossible to implement things like bracket and finally in transformations of IO. What we need is something like startBlocking :: IO () stopBlocking :: IO () Regards, Yitz
On Jul 16, 2009, at 6:18 PM, Yitzchak Gale wrote:
This, and just about all of the other "similar" types mentioned in this thread, are all new names for the venerable "ListT Done Right" that has been around for many years:
http://www.haskell.org/haskellwiki/ListT_done_right
The ListT that is (still, unbelievably) in the mtl package is very broken, and shouldn't be used. It's not even a monad - it doesn't satisfy the monad laws.
So why make up new names? Just call it ListT.
I did call it ListT, although I did place it in the "generator" package. Now I split the package so ListT is in the "List" package (better name - I agree) List: List monad transformer and typeclass. Standard list operations. generator: Python-generator notation for creation of monadic lists.
participants (5)
-
Bas van Dijk -
Sebastian Fischer -
Sjoerd Visscher -
Yair Chuchem -
Yitzchak Gale