A faithful strictly-accumulating writer

newer
[CFP] Final Day for submissions to...

older
Call for scholarship applications:...

David Feuer

30 Aug 2019 30 Aug '19

2:11 a.m.

It's widely known that the classic WriterT tends to leak space, and that in some cases this leak can be resolved by using StateT instead. The implementations I've seen of this idea both use the module system to prevent the computation from gaining unauthorized access to the state. I believe I've found a way to avoid this. Does this look right? {-# language RankNTypes, FlexibleInstances, MultiParamTypeClasses #-} import qualified Control.Monad.Writer.Class as W import Control.Monad.State.Strict import Control.Monad.Reader import Control.Applicative -- The key idea is that the computation -- can't inspect the state because it doesn't know the type newtype WriterT w m a = WriterT { unWriterT :: forall s. ReaderT ((w -> w) -> s -> s) (StateT s m) a } runWriterT :: Monoid w => WriterT w m a -> m (a, w) runWriterT m = runStateT (runReaderT (unWriterT m) id) mempty instance Functor m => Functor (WriterT w m) where fmap f m = WriterT $ fmap f (unWriterT m) instance Monad m => Applicative (WriterT w m) where pure a = WriterT (pure a) liftA2 f m n = WriterT $ liftA2 f (unWriterT m) (unWriterT n) instance Monad m => Monad (WriterT w m) where m >>= f = WriterT $ unWriterT m >>= unWriterT . f instance MonadTrans (WriterT w) where lift m = WriterT $ lift . lift $ m tell :: (Monad m, Semigroup w) => w -> WriterT w m () tell w = WriterT $ do p <- ask modify' $ p (<> w) pass :: Monad m => WriterT w m (a, w -> w) -> WriterT w m a pass m = WriterT $ do p <- ask (a, ww) <- unWriterT m modify' (p ww) pure a instance (Monoid w, Monad m) => W.MonadWriter w (WriterT w m) where tell = tell listen m = do aw@(_a, w) <- lift $ runWriterT m tell w pure aw pass = pass

Attachments:

attachment.html (text/html — 2.9 KB)

Show replies by date

David Feuer

30 Aug 30 Aug

2:56 a.m.

Here's another version that passes the state-modifier implicitly. Is this better or worse? {-# language RankNTypes, FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-} module WriterT where import qualified Control.Monad.Writer.Class as W import Control.Monad.State.Strict import Control.Applicative class WGS w s where wgs :: (w -> w) -> s -> s instance w ~ s => WGS w s where wgs = id newtype WriterT w m a = WriterT { unWriterT :: forall s. WGS w s => StateT s m a } runWriterT :: Monoid w => WriterT w m a -> m (a, w) runWriterT m = runStateT (unWriterT m) mempty instance Functor m => Functor (WriterT w m) where fmap f m = WriterT $ fmap f (unWriterT m) instance Monad m => Applicative (WriterT w m) where pure a = WriterT (pure a) liftA2 f m n = WriterT $ liftA2 f (unWriterT m) (unWriterT n) instance Monad m => Monad (WriterT w m) where m >>= f = WriterT $ unWriterT m >>= unWriterT . f instance MonadTrans (WriterT w) where lift m = WriterT $ lift $ m tell :: (Monad m, Semigroup w) => w -> WriterT w m () tell w = WriterT $ modify' $ wgs (<> w) listen :: (Monad m, Monoid w) => WriterT w m a -> WriterT w m (a, w) listen m = do aw@(_a, w) <- lift $ runWriterT m tell w pure aw pass :: Monad m => WriterT w m (a, w -> w) -> WriterT w m a pass m = WriterT $ do (a, ww) <- unWriterT m modify' (wgs ww) pure a instance (Monoid w, Monad m) => W.MonadWriter w (WriterT w m) where tell = tell listen = listen pass = pass On Fri, Aug 30, 2019 at 9:11 AM David Feuer wrote:

...

It's widely known that the classic WriterT tends to leak space, and that in some cases this leak can be resolved by using StateT instead. The implementations I've seen of this idea both use the module system to prevent the computation from gaining unauthorized access to the state. I believe I've found a way to avoid this. Does this look right?

{-# language RankNTypes, FlexibleInstances, MultiParamTypeClasses #-}

import qualified Control.Monad.Writer.Class as W import Control.Monad.State.Strict import Control.Monad.Reader import Control.Applicative

-- The key idea is that the computation -- can't inspect the state because it doesn't know the type newtype WriterT w m a = WriterT { unWriterT :: forall s. ReaderT ((w -> w) -> s -> s) (StateT s m) a }

runWriterT :: Monoid w => WriterT w m a -> m (a, w) runWriterT m = runStateT (runReaderT (unWriterT m) id) mempty

instance Functor m => Functor (WriterT w m) where fmap f m = WriterT $ fmap f (unWriterT m)

instance Monad m => Applicative (WriterT w m) where pure a = WriterT (pure a) liftA2 f m n = WriterT $ liftA2 f (unWriterT m) (unWriterT n)

instance Monad m => Monad (WriterT w m) where m >>= f = WriterT $ unWriterT m >>= unWriterT . f

instance MonadTrans (WriterT w) where lift m = WriterT $ lift . lift $ m

tell :: (Monad m, Semigroup w) => w -> WriterT w m () tell w = WriterT $ do p <- ask modify' $ p (<> w)

pass :: Monad m => WriterT w m (a, w -> w) -> WriterT w m a pass m = WriterT $ do p <- ask (a, ww) <- unWriterT m modify' (p ww) pure a

instance (Monoid w, Monad m) => W.MonadWriter w (WriterT w m) where tell = tell

listen m = do aw@(_a, w) <- lift $ runWriterT m tell w pure aw

pass = pass

Li-yao Xia

3:42 a.m.

This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...

to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT? What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right? Li-yao On 8/29/19 10:56 PM, David Feuer wrote:

...

Here's another version that passes the state-modifier implicitly. Is this better or worse?

{-# language RankNTypes, FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-} module WriterT where

import qualified Control.Monad.Writer.Class as W import Control.Monad.State.Strict import Control.Applicative

class WGS w s where wgs :: (w -> w) -> s -> s

instance w ~ s => WGS w s where wgs = id

newtype WriterT w m a = WriterT { unWriterT :: forall s. WGS w s => StateT s m a }

runWriterT :: Monoid w => WriterT w m a -> m (a, w) runWriterT m = runStateT (unWriterT m) mempty

instance Functor m => Functor (WriterT w m) where fmap f m = WriterT $ fmap f (unWriterT m)

instance Monad m => Applicative (WriterT w m) where pure a = WriterT (pure a) liftA2 f m n = WriterT $ liftA2 f (unWriterT m) (unWriterT n)

instance Monad m => Monad (WriterT w m) where m >>= f = WriterT $ unWriterT m >>= unWriterT . f

instance MonadTrans (WriterT w) where lift m = WriterT $ lift $ m

tell :: (Monad m, Semigroup w) => w -> WriterT w m () tell w = WriterT $ modify' $ wgs (<> w)

listen :: (Monad m, Monoid w) => WriterT w m a -> WriterT w m (a, w) listen m = do aw@(_a, w) <- lift $ runWriterT m tell w pure aw

pass :: Monad m => WriterT w m (a, w -> w) -> WriterT w m a pass m = WriterT $ do (a, ww) <- unWriterT m modify' (wgs ww) pure a

instance (Monoid w, Monad m) => W.MonadWriter w (WriterT w m) where tell = tell listen = listen pass = pass

On Fri, Aug 30, 2019 at 9:11 AM David Feuer wrote:

...
It's widely known that the classic WriterT tends to leak space, and that in some cases this leak can be resolved by using StateT instead. The implementations I've seen of this idea both use the module system to prevent the computation from gaining unauthorized access to the state. I believe I've found a way to avoid this. Does this look right?

{-# language RankNTypes, FlexibleInstances, MultiParamTypeClasses #-}

import qualified Control.Monad.Writer.Class as W import Control.Monad.State.Strict import Control.Monad.Reader import Control.Applicative

-- The key idea is that the computation -- can't inspect the state because it doesn't know the type newtype WriterT w m a = WriterT { unWriterT :: forall s. ReaderT ((w -> w) -> s -> s) (StateT s m) a }

runWriterT :: Monoid w => WriterT w m a -> m (a, w) runWriterT m = runStateT (runReaderT (unWriterT m) id) mempty

instance Functor m => Functor (WriterT w m) where fmap f m = WriterT $ fmap f (unWriterT m)

instance Monad m => Applicative (WriterT w m) where pure a = WriterT (pure a) liftA2 f m n = WriterT $ liftA2 f (unWriterT m) (unWriterT n)

instance Monad m => Monad (WriterT w m) where m >>= f = WriterT $ unWriterT m >>= unWriterT . f

instance MonadTrans (WriterT w) where lift m = WriterT $ lift . lift $ m

tell :: (Monad m, Semigroup w) => w -> WriterT w m () tell w = WriterT $ do p <- ask modify' $ p (<> w)

pass :: Monad m => WriterT w m (a, w -> w) -> WriterT w m a pass m = WriterT $ do p <- ask (a, ww) <- unWriterT m modify' (p ww) pure a

instance (Monoid w, Monad m) => W.MonadWriter w (WriterT w m) where tell = tell

listen m = do aw@(_a, w) <- lift $ runWriterT m tell w pure aw

pass = pass

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

David Feuer

4:09 a.m.

On Thu, Aug 29, 2019, 11:42 PM Li-yao Xia wrote:

...

This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...
to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT?

Exactly. They should be isomorphic as sets and "morally" isomorphic as monads. There will of course be distinctions in strictness

...

What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right?

Yes. That's the type I started with, and then I got to `pass` and realized it just wouldn't do the trick.

Zemyla

4:49 a.m.

I wish we could separate listen and pass from the Writer monad, and eventually deprecate them. Doing so would solve so many problems. On Thu, Aug 29, 2019, 23:10 David Feuer wrote:

...

On Thu, Aug 29, 2019, 11:42 PM Li-yao Xia wrote:

...
This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...
to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT?

Exactly. They should be isomorphic as sets and "morally" isomorphic as monads. There will of course be distinctions in strictness

...
What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right?

Yes. That's the type I started with, and then I got to `pass` and realized it just wouldn't do the trick. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

David Feuer

3:46 p.m.

I would definitely like to see `listen` split out, since it adds a sort of introspection that can't be good for CPS-based implementations. `pass` is a rather surprising piece of the API that definitely seems to want its own subclass. Another way to express its idea is edit :: (w -> w) -> WriterT w m () This is equally powerful: edit f = pass $ pure ((), f) pass m = do (a, f) <- m edit f pure a The essence of edit/pass is that it adds the ability to make arbitrary modifications to the "log". That excludes instances for which the log itself is not accessible at all. instance MonadWriter String IO where tell = hPutStr stderr On Fri, Aug 30, 2019, 12:49 AM Zemyla wrote:

...

I wish we could separate listen and pass from the Writer monad, and eventually deprecate them. Doing so would solve so many problems.

On Thu, Aug 29, 2019, 23:10 David Feuer wrote:

...
On Thu, Aug 29, 2019, 11:42 PM Li-yao Xia wrote:

...
This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...
to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT?

Exactly. They should be isomorphic as sets and "morally" isomorphic as monads. There will of course be distinctions in strictness

...
What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right?

Yes. That's the type I started with, and then I got to `pass` and realized it just wouldn't do the trick. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

David Feuer

4:17 p.m.

Hmm... that implementation of `pass` isn't quite right for lazy WriterT. I guess it needs to be pass m = do ~(a, f) <- m edit f pure a On Fri, Aug 30, 2019, 11:46 AM David Feuer wrote:

...

I would definitely like to see `listen` split out, since it adds a sort of introspection that can't be good for CPS-based implementations.

`pass` is a rather surprising piece of the API that definitely seems to want its own subclass. Another way to express its idea is

edit :: (w -> w) -> WriterT w m ()

This is equally powerful:

edit f = pass $ pure ((), f) pass m = do (a, f) <- m edit f pure a

The essence of edit/pass is that it adds the ability to make arbitrary modifications to the "log". That excludes instances for which the log itself is not accessible at all.

instance MonadWriter String IO where tell = hPutStr stderr

On Fri, Aug 30, 2019, 12:49 AM Zemyla wrote:

...
I wish we could separate listen and pass from the Writer monad, and eventually deprecate them. Doing so would solve so many problems.

On Thu, Aug 29, 2019, 23:10 David Feuer wrote:

...
On Thu, Aug 29, 2019, 11:42 PM Li-yao Xia wrote:

...
This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...
to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT?

Exactly. They should be isomorphic as sets and "morally" isomorphic as monads. There will of course be distinctions in strictness

...
What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right?

Yes. That's the type I started with, and then I got to `pass` and realized it just wouldn't do the trick. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

David Feuer

4:40 p.m.

No, that's not quite right either (too lazy this time). The idea is morally right, but I guess it doesn't quite work out for strictness. Anyway, this is all a side track. On Fri, Aug 30, 2019, 12:17 PM David Feuer wrote:

...

Hmm... that implementation of `pass` isn't quite right for lazy WriterT. I guess it needs to be

pass m = do ~(a, f) <- m edit f pure a

On Fri, Aug 30, 2019, 11:46 AM David Feuer wrote:

...
I would definitely like to see `listen` split out, since it adds a sort of introspection that can't be good for CPS-based implementations.

`pass` is a rather surprising piece of the API that definitely seems to want its own subclass. Another way to express its idea is

edit :: (w -> w) -> WriterT w m ()

This is equally powerful:

edit f = pass $ pure ((), f) pass m = do (a, f) <- m edit f pure a

The essence of edit/pass is that it adds the ability to make arbitrary modifications to the "log". That excludes instances for which the log itself is not accessible at all.

instance MonadWriter String IO where tell = hPutStr stderr

On Fri, Aug 30, 2019, 12:49 AM Zemyla wrote:

...
I wish we could separate listen and pass from the Writer monad, and eventually deprecate them. Doing so would solve so many problems.

On Thu, Aug 29, 2019, 23:10 David Feuer wrote:

...
On Thu, Aug 29, 2019, 11:42 PM Li-yao Xia wrote:

...
This looks like an interesting problem, but I'm a little confused about the objective. In what sense is it "faithful"?

...
to prevent the computation from gaining unauthorized access to the state.

Does that property have a formal definition? Are we looking for a one-to-one correspondence between a "better" WriterT and the naive WriterT?

Exactly. They should be isomorphic as sets and "morally" isomorphic as monads. There will of course be distinctions in strictness

...
What about (w -> s -> s) instead of ((w -> w) -> (s -> s))? It seems that `pass` needs the (w -> w), but if we leave `pass` aside, does that still look about right?

Yes. That's the type I started with, and then I got to `pass` and realized it just wouldn't do the trick. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

2137

Age (days ago)

2137

Last active (days ago)

List overview

Download

7 comments

3 participants

participants (3)

David Feuer
Li-yao Xia
Zemyla

A faithful strictly-accumulating writer

tags

participants (3)