Use a better ListT

Question

Use a better ListT

turion opened this issue 7 years ago · 10 comments

The ListT implementation we're using (from transformers) is wrong (it's just m [a]) and we should eventually settle for a different, correct version.

Answer 1 · 2017-10-19T14:50:48.000Z

What would the behaviour of other versions be?

Answer 2 · 2017-10-21T13:54:07.000Z

Following https://wiki.haskell.org/ListT_done_right, it would be like so:

-- The monadic list type
data MList' m a = MNil | a `MCons` MList m a
type MList m a  = m (MList' m a)
 
-- This can be directly used as a monad transformer
newtype ListT m a = ListT { runListT :: MList m a }

By the way, this is isomorphic to our MStream. It interleaves one effect of m with one element of the list.

Answer 3 · 2017-10-21T13:55:32.000Z

Also, is this the reason that Control.Monad.Trans.MSF.List is not listed in dunai.cabal? (Because it's deemed incorrect?)

Answer 4 · 2017-10-22T22:40:35.000Z

I don't see any reason not to list it. If there ever was one, I can't recall.

Answer 5 · 2017-10-22T22:57:47.000Z

So, the difference is how the effects in the monad m get unfolded (one by one vs all at once).

Answer 6 · 2017-10-25T12:29:28.000Z

Yes. Also, the `ListT` implementation from `transformers` only works for commutative monads, I think. It can break the monad laws for other monads.

Answer 7 · 2017-10-25T13:35:46.000Z

Yes. Although I don't see anything wrong with ListT only working for commutative monads in principle.

So, essentially, it is possible to obtain the current behaviour with a helper function:

listT2List :: ListT m a -> m [a]
listT2List = mlistT2List . runListT

mlistT2List :: MList m a -> m [a]
mlistT2List MNil            = return []
mlistT2List (MCons a listT) = do
  as <- mlistT2List listT
  return (a : as)

And, probably:

mlistT2List = reverse . foldM (\xs a -> return (a:xs)) []

Answer 8 · 2017-11-01T14:24:09.000Z

I also see no reason not to support the so-called broken ListT. So this ticket could be "provide combinators/lifting/running functions for another list transformer".

Answer 9 · 2018-03-03T23:43:57.000Z

This currently is not bugging me at all. I can either close it and you can re-open when it becomes the one issue you (@turion ) are actively working on, or assign it to you and forget about it.

Answer 10 · 2021-09-06T16:35:14.000Z

This issue has been stagnated for over 3 years. I'm closing it.