Improve documentation for ListT instances

[matthew-hilty]

What kind of effect-sequencing behavior is ListT supposed to exhibit? I ask because in haskell, ListT m a is a newtype wrapper of m [a], and if purescript's ListT is meant to be modeled after haskell's, ListT Effect Int should perhaps then behave like Effect [Int]. However, the haskell community has also considered alternative models for ListT like the following:

-- https://github.com/nikita-volkov/list-t/blob/master/library/ListT.hs
newtype ListT m a =  ListT (m (Maybe (a, ListT m a)))

Because ListT in Pursuit's 'transformers' package is defined as ...

newtype ListT f a = ListT (f (Step a (ListT f a)))
data Step a s = Yield a (Lazy s)  | Skip (Lazy s)  | Done

... Volkov's ListT (shown above) seems to be the underlying model for purescript's own ListT.

What kind of effect-sequencing behavior, then, should Volkov's ListT exhibit? Unfortunately, at the moment, I can't experiment with his code directly; however, it seems that, under specific conditions, Volkov's ListT m Int should behave similarly to [m Int] -- in particular, when a list-like construct in either case (ListT m Int or [m Int]) is fully traversed/consumed with pre-order congruence and the final effect of ListT is pure or ignored. (Or at least I assume; perhaps there are details that invalidate this comparison.)

If this comparison is sound, users in purescript-land might expect values of the analogous purescript types ListT Effect Int, List (Effect Int) and Compose List Effect Int, under appropriate conditions, also to exhibit identical behavior. I'm not sure that's the case, however.

Consider, for example, product0 and product1 below:

import Control.Monad.List.Trans as T
-- other imports ...

io :: forall a b. Show b => b -> a -> Effect a
io x y = log (show x) *> pure y

-- `list0` and `list1` below are meant to have congruent sequences of data AND effects.

list0 :: ListT Effect Int
list0 = fromEffect (io 2 2) <|> fromEffect (io 1 1) <|> fromEffect (io 0 0) <|> T.nil

list1 :: Compose List Effect Int
list1 = Compose $ pure (io 2 2) <|> pure (io 1 1) <|> pure (io 0 0) <|> Nil

f0 :: ListT Effect (Int -> Int)
f0 = fromEffect (io "id" identity)

f1 :: Compose List Effect (Int -> Int)
f1 = Compose (pure (io "id" identity))

product0 = f0 <*> list0 :: ListT Effect Int
product1 = f1 <*> list1 :: Compose List Effect Int

If product0 and product1 are fully traversed, results like the following occur:

sequenceListT :: forall a. ListT Effect a -> Effect (List a)
sequenceListT = foldl' (\x y -> pure (x <> pure y)) Nil

sequenceCompose :: forall a. Compose List Effect a -> Effect (List a)
sequenceCompose = sequence <<< unwrap

-- PROMPT> sequenceListT product0
-- "id"
-- 2
-- 1
-- 0
-- (2 :  1 : 0 : Nil)

-- PROMPT> sequenceCompose product1
-- "id"
-- 2
-- "id"
-- 1
-- "id"
-- 0
-- (2 : 1 : 0 : Nil)

Other helpful comparisons to try might include the following:

product2 = T.nil <*> list0 :: ListT Effect Int
product3 = pure Nil <*> list1 :: Compose List Effect Int
product4 = Backwards f0 <*> Backwards list0 :: Backwards (ListT Effect) Int
product5 = Backwards f1 <*> Backwards list1 :: Backwards (Compose List Effect) Int

Although I've tried to model the same sequence of bundled data and effects as both an instance of ListT Effect Int and as an instance of Compose List Effect Int and although I (myself at least) expect similar behavior because of my assumptions listed above, the two values product0 and product1 have different overall effects when traversed.

The source of this difference in behavior appears to be related to the Apply typeclass. Whereas List's apply member has a static flavor, ListT's implementation of apply is monadic and therefore directionally biased.

I'm not sure which style of applicative multiplication might be generally preferable. I'm not even sure that List and ListT should have exactly identical effect-sequencing semantics (in relevant scenarios). However, because this difference in behavior surprised me at least, I figured I'd note this distinction as an issue for maintainers to consider. Perhaps it's a point confusing/interesting enough to include in documentation.

Thanks much

[natefaubion]

For some background, look around for "ListT done right".

http://h2.jaguarpaw.co.uk/posts/listt-done-wrong/
https://wiki.haskell.org/ListT_done_right

In particular m (List a) does not satisfy Monad laws for all Monads m.

[matthew-hilty]

Hi. Thanks for the references. I'm checking out your first link now, and actually, your second link is how I found my way to Volkov's implementation. The discussion online about how and when List and ListT are monads is pretty interesting. But I guess I wasn't asking so much about their implementations as monads as instead their implementations as applicatives. I'm just wondering how similar List and ListT should be in those kinds of scenarios.

[matthew-hilty]

Wow, Tom Ellis's explanation of the ListT-monad issue is good. It gets to the point, and it makes the crux of the problem immediately apparent. Really, thanks for the link.

[matthew-hilty]

I was experimenting with some code when I noticed what seemed to me an interesting discrepancy between List and ListT, but opening an issue about this difference was probably overly enthusiastic. PureScript's core team of maintainers is doing a phenomenal job, but they have a lot on their plates. I don't want to overwhelm them with minor stuff like this, so I think I'll just close this issue. Thanks, though, for any looks this issue has already gotten.

[hdgarrood]

I wouldn't say overly enthusiastic - the documentation here can definitely be improved, so I think this is worth keeping open.

[matthew-hilty]

Oh, ok. I'm glad this issue has some value then after all. Thanks for reopening it.