mer*_*ict 40 haskell monadfix tying-the-knot
我正在研究一个涉及绑定大结的Haskell项目:我正在解析图的序列化表示,其中每个节点都在文件的某个偏移处,并且可以通过其偏移引用另一个节点.所以我需要在解析时建立从偏移到节点的映射,我可以在一个do rec块中反馈给自己.
我有这个工作,有点合理地抽象成一个StateT-esque monad变换器:
{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}
import qualified Control.Monad.State as S
data Knot s = Knot { past :: s, future :: s }
newtype RecStateT s m a = RecStateT (S.StateT (Knot s) m a) deriving
( Alternative
, Applicative
, Functor
, Monad
, MonadCont
, MonadError e
, MonadFix
, MonadIO
, MonadPlus
, MonadReader r
, MonadTrans
, MonadWriter w )
runRecStateT :: RecStateT s m a -> Knot s -> m (a, Knot s)
runRecStateT (RecStateT st) = S.runStateT st
tie :: MonadFix m => RecStateT s m a -> s -> m (a, s)
tie m s = do
rec (a, Knot s' _) <- runRecStateT m (Knot s s')
return (a, s')
get :: Monad m => RecStateT s m (Knot s)
get = RecStateT S.get
put :: Monad m => s -> RecStateT s m ()
put s = RecStateT $ S.modify $ \ ~(Knot _ s') -> Knot s s'
这个tie函数是魔术发生的地方:runRecStateT产生一个值和一个状态的调用,我把它作为自己的未来.请注意,get允许您从过去和未来状态中读取,但put只允许您修改"当前".
问题1:这看起来像是一种体面的方式来实现这种打结模式吗？或者更好的是,有人实施了一个通用的解决方案,在窥探Hackage时我忽略了吗？我对着Contmonad打了一会儿,因为它看起来可能更优雅(见Dan Burton的类似帖子),但我无法解决这个问题.
完全主观问题2:我对调用代码最终看起来的方式并不十分兴奋:
do
Knot past future <- get
let {- ... -} = past
{- ... -} = future
node = {- ... -}
put $ {- ... -}
return node
实现细节此处省略,显然,重要的一点是,我必须得到past和future状态,模式匹配他们一个让内部结合(或明确地使先前的模式懒惰)提取不管我在乎,然后建立自己的节点,更新我的状态,最后返回节点.看起来不必要地冗长,我特别不喜欢意外地制作提取past和future严格的模式是多么容易.那么,任何人都可以想到更好的界面吗？
我在题为Assembly:Circular Programming with Recursive do的文章中写了一篇关于这个主题的文章,其中我描述了两种使用结打结构建汇编程序的方法.与您的问题一样,汇编程序必须能够解析文件中稍后可能出现的标签地址.
关于实施,我将把它作为一个读者monad(未来)和一个状态monad(过去/现在)的组合.原因是你只设置了一次(in tie)然后不改变它.
{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}
import Control.Monad.State
import Control.Monad.Reader
import Control.Applicative
newtype RecStateT s m a = RecStateT (StateT s (ReaderT s m) a) deriving
( Alternative
, Applicative
, Functor
, Monad
, MonadPlus
)
tie :: MonadFix m => RecStateT s m a -> s -> m (a, s)
tie (RecStateT m) s = do
rec (a, s') <- flip runReaderT s' $ flip runStateT s m
return (a, s')
getPast :: Monad m => RecStateT s m s
getPast = RecStateT get
getFuture :: Monad m => RecStateT s m s
getFuture = RecStateT ask
putPresent :: Monad m => s -> RecStateT s m ()
putPresent = RecStateT . put
关于你的第二个问题,它有助于了解你的数据流(即有一个最小的代码示例).严格的模式总是导致循环,这是不正确的.确实,您需要小心,以免创建非生产循环,但确切的限制取决于您正在构建的内容和方式.
我一直在玩弄东西,我想我已经想出了一些东西......很有意思.我把它称为"Seer"monad,它提供了(除了Monad操作)两个原始操作:
see :: Monoid s => Seer s s
send :: Monoid s => s -> Seer s ()
和运行操作:
runSeer :: Monoid s => Seer s a -> a
这个monad的工作方式是see允许先知看到一切,并send允许先见者向所有其他先知"发送"信息供他们查看.每当任何先见者执行see操作时,他们都能够看到已发送的所有信息以及将要发送的所有信息.换句话说,在给定的运行中,see无论何时何地调用它,都将始终产生相同的结果.另一种说法就是see你如何得到"捆绑"结的工作参考.
这实际上非常类似于使用fix,除了所有子部分以递增和隐式方式添加,而不是显式添加.显然,先知在悖论的存在下无法正常工作,并且需要足够的懒惰.例如,see >>= send可能会导致信息爆炸,将您陷入时间循环.
一个愚蠢的例子:
import Control.Seer
import qualified Data.Map as M
import Data.Map (Map, (!))
bar :: Seer (Map Int Char) String
bar = do
m <- see
send (M.singleton 1 $ succ (m ! 2))
send (M.singleton 2 'c')
return [m ! 1, m ! 2]
正如我所说的那样,我一直在玩弄,所以我不知道这是否比你所拥有的要好,或者它是否有任何好处!但它很漂亮,相关,如果你的"结"状态是Monoid,那么它可能对你有用.公平警告:我Seer是用一个建造的Tardis.
https://github.com/DanBurton/tardis/blob/master/Control/Seer.hs