deprecated Control.Monad.Trans.MSF.List ?

[madjestic]

Hey guys,

The examples of the paper are using this function:
https://hackage.haskell.org/package/dunai-0.11.0/docs/Control-Monad-Trans-MSF-List.html#v:widthFirst

ListT is also used in bearriver's parB = widthFirst . sequenceS

The module is marked as deprecated. What is the new alternative to the method using widthFirst as described in the paper and the examples?

Thanks!

[madjestic]

Doing some reading, I guess there are at least 2 options:
https://hackage.haskell.org/package/list-t
https://hackage.haskell.org/package/pipes

Should dunai use any of those?

[madjestic]

It looks like list-t package provides a trivial drop-in replacement for runListT, so the dunai example needs only a minor fix:

import ListT

-- we replace 
-- runListT :: forall (m :: * -> *) a. ListT m a -> m [a]
-- with
-- toList: : Monad m => ListT m a -> m [a]

widthFirst :: (Functor m, Monad m) => MSF (ListT m) a b -> MSF m a [b]
widthFirst msf = widthFirst' [msf]
  where
    widthFirst' msfs = MSF $ \a -> do
      (bs, msfs') <- unzip . concat <$> mapM (toList . flip unMSF a) msfs
      return (bs, widthFirst' msfs')

So the fix seems trivial, but then where does it need to go, since widthFirst is a part of (deprecated) Control.Monad.Trans.MSF.List ?

[ivanperez-keera]

Hi,

ListT is deprecated, but the module currently offered by dunai is not, and for the time being that's not going to change. We did talk about using list-t in the past. See: #36.

If this is a problem, we can discuss the alternatives.

I'm making this for now a discussion; if we agree on changing the implementation we can open an issue for that or re-classify this thread.

[turion]

The problem is that ListT is removed in later mtl and transformers versions, so we can't depend indefinitely on it.

[madjestic]

I don't know all implications of this transition, but, syntactically speaking, it seems fairly easy to do the porting.
I am thinking about simply adding synonyms that would reference the list-t instead of dunai for all things ListT, so that the API stays backwards compatible.
Is it a bad idea, am I overlooking something?

I am sorry, Ivan, I could not find anything directly concerning list-t package as a possible dependency in that thread that you linked.

[ivanperez-keera]

I am sorry, Ivan, I could not find anything directly concerning list-t package as a possible dependency in that thread that you linked.

See: 1a3b442

[ivanperez-keera]

Issue #371 was just opened as a consequence of this lack of a better list replacement.

I'm not a user of stackage myself but I'd be happy to revisit / review this if someone has the time and energy to do it well.

[tomsmeding]

This is not only an issue with stackage; any build of dunai with transformers >= 0.6 will fail due to Control.Monad.Trans.List being removed from transformers at version 0.6. In order to not break people's builds, I think dunai has to choose between one of these options:

1. Set an upper version bound in the cabal file: transformers < 0.6 here;
2. Replace the use of Control.Monad.Trans.List from transformers with another package (e.g. list-t);
3. Point (2.), but only when building with transformers >= 0.6 using a cabal conditional;
4. Remove Control.Monad.Trans.MSF.List from dunai.

I'm listing option (4.) for completeness, but you've already indicated to not want that option.

I'm not sure what the best option would be for dunai (I'm only reporting this because I'm running into this when building working package sets for the playground); I would personally say (1.) is a bad idea, because even if few packages currently require transformers >= 0.6, this number will only increase as time goes on. I'm also hesitant about option (3.) because even if the APIs are mostly compatible, minor API differences that depend on the chosen version of a different, seemingly unrelated package, are liable to result in screaming users. Thus I would personally veer towards (2.).

But the choice is yours. :)

[ivanperez-keera]

I'm looking into using list-t, but a quick check shows that, without list-t, these are the dependencies of dunai:

base-orphans-0.9.0
data-array-byte-0.1.0.1
MonadRandom-0.6
primitive-0.8.0.0
random-1.2.1.1
simple-affine-space-0.2.1
splitmix-0.1.0.4
transformers-base-0.4.6
transformers-compat-0.7.2

This is with list-t:

assoc-1.1
base-orphans-0.9.0
bifunctors-5.6.1
comonad-5.0.8
contravariant-1.5.5
data-array-byte-0.1.0.1
distributive-0.6.2.1
foldable1
foldl-1.4.15
hashable-1.4.3.0
indexed-traversable-0.1.2.1
list-t-1.0.5.1
logict-0.7.0.3
mmorph-1.2.0
monad-control-1.0.3.1
MonadRandom-0.6
primitive-0.8.0.0
profunctors-5.6.2
random-1.2.1.1
semigroupoids-6.0.0.1
semigroups-0.20
simple-affine-space-0.2.1
splitmix-0.1.0.4
StateVar-1.2.2
tagged-0.8.8
th-abstraction-0.6.0.0
transformers-base-0.4.6
transformers-compat-0.7.2
unordered-containers-0.2.19.1
vector-0.13.0.0
vector-stream-0.1.0.0

ListT defines a lot of instances that we don't need and pull lots of packages. Without those, list-t only needs:

data-array-byte-0.1.0.1
StateVar-1.2.2
indexed-traversable-0.1.2.1
splitmix-0.1.0.4
tagged-0.8.8

[ivanperez-keera]

So the new ones if we depend on list-t but can hide what we don't want are:

StateVar-1.2.2
indexed-traversable-0.1.2.1
tagged-0.8.8

[ivanperez-keera]

There are several alternatives at this point:

• Depend on list-t as is.
• Depend on list-t only if they introduce a flag to reduce dependencies.
• Create a fork of list-t that only provides what we need. (This is bad for the community and our users, so it's better if avoided.)
• Remove the List combinators and move them to a separate library that depends on list-t.
• Remove the List combinators and define a module like Control.Monad.Trans.List internally in bearriver just to provide what we need.

[tomsmeding]

Depend on list-t only if they introduce a flag to reduce dependencies.

The only dependency they would need to make optional is foldl, it seems; the graph is pretty suggestive.

I agree the situation is suboptimal; it even seems that in this case it's not only an instance in list-t, but actually an exposed function (applyFoldM). And foldl is not quite so common a package that it's going to be a dependency of the users' projects anyway.

[tomsmeding]

Oh sorry, my sentence was awkwardly formulated. My point was that if foldl were so common that it is practically a dependency of any user's project anyway, dunai adding it as a dependency, regardless of how big it is, would hardly affect the typical user. However, foldl is not that common, so its size (including transitive deps) really does matter.

[ivanperez-keera]

Ok. Nikita is as of now not very open to this change (see associated issue) but lets see what happens.

[ivanperez-keera]

The maintainer of list-t said that he won't add a flag, but pointed me to https://hackage.haskell.org/package/list-transformer as an alternative implementation with fewer dependencies.

When it comes to parallelizing MSFs and implementing things like BearRiver's parC, would the behavior with list-transformer be the same as with list-t (and as with the current implementation)?

[tomsmeding]

I hope you're not asking that to me, because I know nothing about dunai, BearRiver or list-t!

I did have a look at the three types, and I saw that old transformers has ListT m a = m [a], which is not the same as the versions in list-t and list-transformer, which are both isomorphic to ListT m a = m (Maybe (a, ListT m a)). The latter two packages claim that their implementation is a monad for all base monads m, whereas transformers' ListT is only a monad for commutative monads m (otherwise associativity fails). My brain is not big enough at the moment to verify that the other two do indeed always work.

The two Monad implementations in list-t and list-transformer do look equivalent.

(Sorry, I hate this interface)

[ivanperez-keera]

Hahah. No problem, it was more of a question for the class 😆

But your response helps.

[ivanperez-keera]

Also tagging @turion who created the first attempt at supporting list-t. Manuel, we are looking at using the library list-transformer, which provides an alternative ListT but has fewer dependencies than list-t. Are the two types equivalent (list-t's and list-transformer's)?

[turion]

list-t and list-transformer are isomorphic. But they are not isomorphic to the kind of ListT we are using in dunai. That ListT is the old one, and it is isomorphic to ListT m a = Compose [] m a. Compositions of functors have Functor and Applicative instances, but not Monad instances. So here is one other option: Replace ListT m a by Compose [] m a (no extra dependencies, it's in base), and lose the Category (MSF (ListT m)) instance (since it needs Monad m => Monad (ListT m). We would still have Applicative (MSF (ListT m) a), and we can still define widthFirst etc. in pretty much the same way as before.

[turion]

It would be surprising though for inexperienced users, because they will not be able to use e.g. arrow syntax anymore, and the error message might be not very helpful. Possibly custom error messages can be added with later GHC versions (9.6, 9.8 maybe?)

[madjestic]

If we loose arrow syntax, does it mean that Bearriver is not going to work either?

[turion]

Very many functions from bearriver and dunai impose a Monad constraint, sometimes because arrow syntax is used. For example:

integralFrom a0 = proc a -> do
  dt <- constM ask        -< ()
  accumulateWith (^+^) a0 -< realToFrac dt *^ a

Sometimes, this constraint is unneeded, as in the definition of occasionally:

proc _ -> do
        r   <- getRandomRS (0, 1) -< ()
        dt  <- timeDelta          -< ()
        let p = 1 - exp (-(dt / tAvg))
        returnA -< if r < p then Event b else NoEvent

This should be definable with Applicative:

let f r dt = if r < 1 - exp (-(dt / tAvg)) then Event b else NoEvent
in f <$> getRandomRS (0, 1) <*> timeDelta

But some definitions really need Monad, so still a lot of constructions will not be possible. One needs to interpret the ListT layer with widthFirst or similar before one can use them.

[turion]

Small addendum: One would also have Alternative (MSF (ListT m) a) instead of ArrowPlus for branching/nondeterminism/choice.

[turion]

There is yet another way to pursue. At monad-bayes we also have the issue of deprecating ListT m. I proposed to replace it with FreeT [] m, which has few dependencies and is a monad. One can easily interpret FreeT [] m a -> m [a] after one has used the monad interface, and then one could apply widthFirst.

The advantage over "ListT done right" is that the free transformer is not biased in the order of alternatives: ListT m done right has nested layers of m, and the nesting increases with the length of the list. So if I have msf1 <+> msf2 <+> msf3 <+> ... then msf3 is buried under 3 layers of m. This is not the case for the free transformers, there the layers of m are the same for all alternatives, they only increase for every use of >>>.

[madjestic]

Hey @turion It looks like FreeT may be a better alternative than ListT. I still don't understand though if that also implies keeping arrow syntax or not?

[turion]

Yes, you could keep it. Let me try and sketch the API:

newtype ListT m a = ListT (Compose [] m a)
  deriving (Functor, Applicative)

newtype FreeListT m a = FreeListT (FreeT [] m a)
  deriving (Functor, Applicative, Monad)

runFreeListT :: Monad m => FreeListT m a -> ListT m a
runFreeListS :: Monad m => MSF (FreeListT m) a b -> MSF (ListT m) a

instance Monad m => Arrow (MSF (FreeListT m)) -- This one you need for arrow syntax
instance ... => ArrowChoice (MSF (FreeListT m)) -- This one you need for case & if inside arrow syntax

instance Functor m => Functor (MSF (ListT m) a)
instance Applicative m => Applicative (MSF (ListT m) a) -- With this one you can do some limited form of do notation
instance Functor m => Profunctor (MSF (ListT m))

-- So to interpret FreeListT, you will need to pass through ListT at some point
widthFirst :: Monad m => MSF (ListT m) a b -> MSF m a [b]

[madjestic]

Thanks for the clarification, @turion !

[ivanperez-keera]

@turion recently pinged me about this.

I'm evaluating addressing this in the next release (release data Feb 21, 2024).

If we have to rely on an external package, I'd favor things like minimal dependencies, established packages, and having a track record of sustained maintenance and good SWE practices.

[DrewFenwick]

Replacing the now removed modules would be good but what is the blocker on fixing the bad bound on the existing version with a revision?

The upper bound claims this library should work with transformers-0,6.* but this isn't true: nobody should be able to build this against transformers-0.6.*

[turion]

I agree, this should be done.

[ivanperez-keera]

Would this be a valid implementation using list-transformer?

https://github.com/ivanperez-keera/dunai/blob/develop-list-transformer/dunai/src/Control/Monad/Trans/MSF/ListTransformer.hs

(Note: The intent is not necessarily to place it in a separate module. I only did that for now to make my life easier on my side.)

I have a bit of brain fog. I want to think that it should be possible to eliminate the ListT $ next bit (here) but I can't figure it out right now.

[ivanperez-keera]

I've just sent a PR to https://github.com/Gabriella439/list-transformer with the proposed change. If/when that is merged and a new version published, we'll be able to rely on list-transformer.

[nullobject]

Nice work @ivanperez-keera 🙌

[ivanperez-keera]

A new version of list-transformer has been published. I've checked that my proposed implementation compiles with it.

Just so that no existing code is broken, and to preserve backwards compatibility for a couple of releases, I'm going to protect the alternative implementation with a flag that can be automatically set and will use the new ListT when available, but default to the old ListT when a modern version of list-transformers is not available or desired.

I'm trying to figure out how to best do this in the most stable way (without producing more API-breaking changes later).

I'll also want to make sure that the behavior is the same. Working with monads and monad transfomers can get pretty tricky, so I'll want to write a few tests that demonstrate that the behavior really is the same.

[turion]

I'll also want to make sure that the behavior is the same. Working with monads and monad transfomers can get pretty tricky, so I'll want to write a few tests that demonstrate that the behavior really is the same.

That's a good point. list-transformer is semantically different from the old list transformer for most inner monads, so it makes sense to write some tests that use such monads. For example, State or Either.

[ivanperez-keera]

I've written a simple test using a couple of monads:

import Control.Monad.Trans.MSF
import Control.Monad.Trans.MSF.List            as LS
import Control.Monad.Trans.MSF.ListTransformer as LT
import Data.Functor.Identity
import Data.MonadicStreamFunction

main :: IO ()
main = do
  putStrLn "Test with identity:"
  lsMain1
  ltMain1
  putStrLn ""
  putStrLn "Test with state:"
  lsMain2
  ltMain2

lsMain1 = print $ runIdentity $ embed lsChain [1, 200, (-300)]
ltMain1 = print $ runIdentity $ embed ltChain [1, 200, (-300)]

lsMain2 = print $ runIdentity $ embed lsStateFlat [0, 200, (-300)]
ltMain2 = print $ runIdentity $ embed ltStateFlat [0, 200, (-300)]

lsChain :: MSF Identity Int [Int]
lsChain = LS.widthFirst lsListOf

lsListOf :: MSF (LS.ListT Identity) Int Int
lsListOf = LS.sequenceS [plus1, plus2]

ltChain :: MSF Identity Int [Int]
ltChain = LT.widthFirst ltListOf

ltListOf :: MSF (LT.ListT Identity) Int Int
ltListOf = LT.sequenceS [plus1, plus2]

plus1 :: MSF Identity Int Int
plus1 = arr (+10)

plus2 :: MSF Identity Int Int
plus2 = arr (+20)

lsStateFlat :: MSF Identity Int [Int]
lsStateFlat = runStateS__ lsStateChain 0

lsStateChain :: MSF (State Int) Int [Int]
lsStateChain = LS.widthFirst lsStateOf

lsStateOf :: MSF (LS.ListT (State Int)) Int Int
lsStateOf = LS.sequenceS [state1, state2]

ltStateFlat :: MSF Identity Int [Int]
ltStateFlat = runStateS__ ltStateChain 0

ltStateChain :: MSF (State Int) Int [Int]
ltStateChain = LT.widthFirst ltStateOf

ltStateOf :: MSF (LT.ListT (State Int)) Int Int
ltStateOf = LT.sequenceS [state1, state2]

state1 :: MSF (State Int) Int Int
state1 = stateS (arr $ \(s, a) -> (s + a + 10, s + 1))

state2 :: MSF (State Int) Int Int
state2 = stateS (arr $ \(s, a) -> (s + a + 20, s - 1))

This is the output:

Test with identity:
[[11,21],[210,220],[-290,-280]]
[[11,21],[210,220],[-290,-280]]

Test with state:
[[1,9],[31,239],[461,169]]
[[1,9],[31,239],[461,169]]

Is there anything else that should be tested?

[ivanperez-keera]

The changes how now been merged in #418. Thanks everyone!

[ivanperez-keera]

This is now released.

[tomsmeding]

The 0.13 release of dunai is not actually buildable with transformers-0.6, because dunai unconditionally depends on transformers < 0.6 and, if the list-transformer flag is set, additionally depends on transformers < 0.7. Cabal constraints are conjunctive, they don't replace earlier occurrences. :) This uniformly handles constraints on a package arising from various packages in the tree, as well as e.g. cabal.project.freeze files and multiple (possibly conditional) blocks in a single cabal file.

I'm afraid the regular transformers < 0.6 constraint will have to go in an else of the if flag(list-transformer) conditional.

[ivanperez-keera]

Oh no. I must have tested it incorrectly! Sorry about that. Can you open a separate bug for this?

[tomsmeding]

Issue created; sorry that I did not test this before the release. (I was lazy...)