标签: monadfix

我正在研究一个涉及绑定大结的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 …

http://hackage.haskell.org/package/free在Control.Monad.Free.Free允许一个获得获得了"自由单子"对于任何给定Functor.但是,它没有MonadFix实例.这是因为这样的实例无法写入,还是只是被遗漏了？

如果不能写这样的实例,为什么不呢？

我正在Haskell写一个brainfuck解释器,我想出了一个我认为对程序非常有趣的描述:

data Program m = Instruction (m ()) (Program m)
               | Control (m (Program m))
               | Halt

但是,将brainfuck程序的文本表示解析为此数据类型是很棘手的.尝试正确解析方括号时会出现问题,因为有一些结点可以使Instruction循环中的最终内容Control再次链接到循环.

更多初步信息.有关所有详细信息,请参阅github repo上的此版本.

type TapeM = StateT Tape IO
type TapeP = Program TapeM
type TapeC = Cont TapeP

branch :: Monad m => m Bool -> Program m -> Program m -> Program m
branch cond trueBranch falseBranch =
  Control ((\b -> if b then trueBranch else falseBranch) `liftM` cond)

loopControl :: TapeP -> TapeP -> …

我一直在说我的东西绊倒猜测是一个错误Data.Map,但也很可能在我的Haskell知识的错误.希望有人能澄清它是什么:)

请参考这个要点.我正在将循环链表结构序列化为字节流.对于任何给定节点,形式如下:

data Node = Node
  { val  :: Word8
  , next :: Node
  }

我希望它被序列化为一对字节:表示第一个字节val,第二个字节表示next可以定位的字节流中的偏移量.例如,我希望:

let n0 = Node 0 n1
    n1 = Node 1 n0

被序列化为[0, 1, 1, 0].没什么大不了.

这里稍微棘手的部分是我正在利用MonadFix实例RWST来"绑定"字节流偏移:我维护一个从节点到偏移的映射,在序列化期间填充映射,但也引用了映射中没有的映射必然存在,直到序列化完成.

当地图实现Data.HashMap.Lazy(来自无序容器)时,这非常有用.但是,当实现是通常的Data.Map(从容器)时,程序堆栈溢出 - 没有双关语意图 - Map尝试无限地比较两个节点使用(==).

所以我的问题是:这是一个错误Data.Map,或者我对这些结构在存在mfix缺陷时应该如何表现的假设？

我们如何证明continuation monad没有有效的实例MonadFix？

问题主要在标题中.似乎mfix可以为任何monadic计算定义,即使它可能有所不同:

mfix :: (a -> m a) -> m a
mfix f = fix (join . liftM f)

这个结构有什么问题？另外,为什么Monad和MonadFixtypeclass分开(即什么类型有一个实例Monad但没有MonadFix？)？

特定

newtype Tree m a = Tree { runTree :: m (Node m a) }
data Node m a = Node
  { nodeValue :: a
  , nodeChildren :: [Tree m a] 
  }

有没有有效的MonadFix实例？

我的尝试是

instance MonadFix m => MonadFix (Tree m) where
  mfix f = Tree $ do
    Node
      <$> mfix (runTree . f . nodeValue) 
      <*> fmap nodeChildren (runTree (mfix f))

然而,当我真正尝试使用它时,这似乎并没有终止.该实例受到MonadFix列表实例的启发.

我想写一个光滑的代码(通过打结来节省我很多时间来实现).它大致是这样的,

n <- myinstr n x

在理论上,myinstr应该运行x以获得一个价值,这将成为n.myinstr在Statemonad 中运行,将n进入状态,但这不会影响x计算.

我尝试过使用DoRec和实现的mfix,

instance Monad  => MonadFix (MyMonad ) where
    mfix f = fix (\mx -> mx >>= f)

事情冻结了.有没有任何方法可以修复我的代码(或者第一次正确设计它的方法),还是应该写一些更直接的东西？

Data.Tree包括unfoldTreeM_BF和unfoldForestM_BF使用monadic动作的结果构造树广度优先的功能.可以使用forest unfolder轻松编写树展开文件,因此我将重点关注后者:

unfoldForestM_BF :: Monad m =>
             (b -> m (a, [b])) -> [b] -> m [Tree a]

从种子列表开始,它为每个种子应用一个函数,生成将产生树根的动作和用于下一级展开的种子.所使用的算法是稍微严格,因此,使用unfoldForestM_BF与该Identity单子是不完全一样使用纯unfoldForest.我一直试图弄清楚是否有办法让它变得懒惰而不牺牲它的O(n)时间限制.如果(正如Edward Kmett向我建议的那样)这是不可能的,我想知道是否有可能采用更具约束力的类型,特别是需要MonadFix而不是Monad.这个概念将(以某种方式)设置指向未来计算结果的指针,同时将这些计算添加到待办事项列表中,因此如果它们在早期计算的效果中是惰性的,则它们将立即可用.

我正在为Ocaml中的类似haskell的符号制作camlp4扩展,并试图找出GHC如何编译递归的do-bindings(使用-XDoRec启用).
我想知道monadic fixpoint combinator是否有可能以严格的语言存在(比如Ocaml/F#/ SML/...)？
如果是的话,它看起来怎么样？它会非常有用吗？