16

The following program uses a backwards-traveling state as provided by the Tardis monad.

{-# LANGUAGE RecursiveDo #-}

import Control.Monad.Tardis

lastOccurrence :: Int -> Tardis [Int] () Bool
lastOccurrence x = mdo
  sendPast (x : xs)
  xs <- getFuture
  return (not (elem x xs))

lastOccurrences :: [Int] -> Tardis [Int] () [Bool]
lastOccurrences xs = mapM lastOccurrence xs

main :: IO ()
main =
  print $ flip evalTardis ([], ()) $ lastOccurrences [3,4,6,7,4,3,5,7]

How can I replace the Tardis monad with the reverse State monad? With my following proposal, main loops forever instead of printing [False,False,True,False,True,True,True,True] as with the above program.

{-# LANGUAGE RecursiveDo #-}

import Control.Monad.RevState

lastOccurrence :: Int -> State [Int] Bool
lastOccurrence x = mdo
  put (x : xs)
  xs <- get
  return (not (elem x xs))

lastOccurrences :: [Int] -> State [Int] [Bool]
lastOccurrences xs = mapM lastOccurrence xs

main :: IO ()
main =
  print $ flip evalState [] $ lastOccurrences [3,4,6,7,4,3,5,7]
1
  • 1
    If your question isn't getting enough attention on SO, feel free to ping package authors such as myself! Issue trackers and maintainer contact info can usually be found on hackage, e.g. hackage.haskell.org/package/rev-state
    – Dan Burton
    Commented Dec 15, 2015 at 18:31

1 Answer 1

17
+25

I have now downloaded the source of both Tardis and RevState, and I started hacking on them until they are almost the same:

  • I ignored everything outside the Trans.{Tarids,RevState} modules, so that I don't have to bother with the typeclasses
  • I removed the forward-propagating state of Tardis
  • I renamed Tardis to State

After a bit of reordering of code, I ended up in a situation where your Tardis-using example still works and your RevState-using example still doesn't work, and their difference is minimal.

What is that minimal difference, you ask? Unsurprisingly, the MonadFix instance. Tardis has this:

instance MonadFix m => MonadFix (TardisT bw fw m) where
  mfix f = TardisT $ \s -> do
    rec (x, s') <- runTardisT (f x) s
    return (x, s')

whereas RevState has this:

instance MonadFix m => MonadFix (StateT s m) where
  mfix f = StateT $ \s ->
    mfix (\(x, _) -> runStateT (f x) s)

While they seem similar, the big difference is that the RevState one is strict in the tuple constructor, whereas the Tardis one is lazy. (see e.g. the GHC documentation on RecursiveDo to see that the Tardis one desugars into an irrefutable pattern match in the lambda passed to mfix).

Indeed, changing the implementation of RevState so that

instance MonadFix m => MonadFix (StateT s m) where
  mfix f = StateT $ \s -> do
    mfix (\ ~(x, _) -> runStateT (f x) s)

fixes your original RevState-using program.

2
  • 2
    I've reported this as a bug to upstream: github.com/DanBurton/rev-state/issues/2
    – Cactus
    Commented Dec 15, 2015 at 11:05
  • 10
    Author of Tardis and rev-state here. Can confirm, this was a bug. I just uploaded rev-state-0.1.1 with Cactus's suggested fix, and turned this example into a test case. Thanks for looking into that!
    – Dan Burton
    Commented Dec 15, 2015 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.