Haskell的逆向性:从Tardis到RevState

Question

以下程序使用由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]

如何用反向状态 monad 替换Tardis monad？根据我的以下提议,main永远循环而不是[False,False,True,False,True,True,True,True]像上面的程序一样打印 .

{-# 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]

Answer 1

现在我已经下载了两者的来源Tardis和RevState,我开始对他们的黑客攻击,直到他们几乎是相同的:

• 我忽略了Trans.{Tarids,RevState}模块之外的所有内容,因此我不必费心去处理类型类
• 我删除了前向传播状态 Tardis
• 我改名Tardis为State

在对代码进行了一些重新排序之后,我最终遇到了这样一种情况,即你的Tardis例子仍然RevState有用,而你的例子仍然不起作用,而且他们的差别很小.

你问的最小差异是什么？不出所料,MonadFix实例.Tardis有这个:

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

而RevState有这个:

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

虽然它们看起来很相似,但最大的区别在于RevState元组构造函数中的一个是严格的,而Tardis一个是懒惰的.(参见例如GHC文档RecursiveDo,看看那个人Tardis在传递给lambda的时候去了一个无可辩驳的模式匹配mfix).

事实上,改变的实施RevState,使

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

修复你原来RevState使用的程序.