与国家monad绑结

我正在开发一个Haskell项目，涉及到一个大结：我parsing一个graphics的序列化表示，其中每个节点在文件中有一些偏移量，并且可以通过偏移量引用另一个节点。 所以我需要在parsing的时候build立一个从偏移到节点的映射，我可以在do rec块中反馈给自己。

我有这个工作，而且有点不合理地抽象成一个StateT monque转换器： 

 {-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-} import qualified Control.Monad.State as S data Knot s = Knot { past :: s, future :: s } newtype RecStateT sma = RecStateT (S.StateT (Knot s) ma) deriving ( Alternative , Applicative , Functor , Monad , MonadCont , MonadError e , MonadFix , MonadIO , MonadPlus , MonadReader r , MonadTrans , MonadWriter w ) runRecStateT :: RecStateT sma -> Knot s -> m (a, Knot s) runRecStateT (RecStateT st) = S.runStateT st tie :: MonadFix m => RecStateT sma -> s -> m (a, s) tie ms = do rec (a, Knot s' _) <- runRecStateT m (Knot s s') return (a, s') get :: Monad m => RecStateT sm (Knot s) get = RecStateT S.get put :: Monad m => s -> RecStateT sm () put s = RecStateT $ S.modify $ \ ~(Knot _ s') -> Knot ss'

tie函数是魔术发生的地方：对runRecStateT的调用产生一个值和一个状态，我将它作为自己的将来。 请注意get可以让你阅读过去和未来的状态，但只允许你修改“present”。

问题1 ：这似乎是一个体面的方式来实现这个一般的结合模式？ 或者更好的是，有人实施了一个通用的解决scheme，我忽略了通过Hackage窥探？ 我对Cont monad打了一会儿头，因为它看起来可能更优雅（见Dan Burton的类似post ），但是我不能解决这个问题。

完全主观的问题2 ：我并不完全激动我的调用代码结束的方式： 

 do Knot past future <- get let {- ... -} = past {- ... -} = future node = {- ... -} put $ {- ... -} return node

实现的细节在这里省略了，显然，重要的一点是我必须得到past和future状态，模式匹配它们在一个let绑定 （或明确地使以前的模式懒惰）中提取我所关心的任何东西，然后构build我的节点，更新我的状态，最后返回节点。 似乎不必要的冗长，我特别不喜欢这是多么容易的意外，使模式，提取past和future国家严格。 那么，谁能想到一个更好的界面呢？

我一直在玩东西，我想我已经想出了一些有趣的东西。 我把它称为“先知”monad，它提供了（除了Monad操作）两个原始操作： 

 see :: Monoid s => Seer ss send :: Monoid s => s -> Seer s ()

和一个运行操作： 

 runSeer :: Monoid s => Seer sa -> a

这个monad的作品的方式是see允许一个先知看到的一切 ，并send允许一个先知“发送”信息给所有其他先知，让他们看到。 只要有任何先见者执行了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 ，那么它可能对你有用。 公平的警告：我使用Tardisbuild造了Seer 。

https://github.com/DanBurton/tardis/blob/master/Control/Seer.hs

我写了一篇关于这个题目的文章，名为Assembly：Circularrecursion循环编程，在这里我描述了使用打结来构build汇编程序的两种方法。 像你的问题一样，汇编程序必须能够parsing文件中稍后可能出现的标签地址。

关于实施，我会把它作为一个读者monad（对未来）和一个国家monad（对于过去/现在）的组成。 原因是你只设定了一次（ tie ），然后不改变它。 

 {-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-} import Control.Monad.State import Control.Monad.Reader import Control.Applicative newtype RecStateT sma = RecStateT (StateT s (ReaderT sm) a) deriving ( Alternative , Applicative , Functor , Monad , MonadPlus ) tie :: MonadFix m => RecStateT sma -> s -> m (a, s) tie (RecStateT m) s = do rec (a, s') <- flip runReaderT s' $ flip runStateT sm return (a, s') getPast :: Monad m => RecStateT sms getPast = RecStateT get getFuture :: Monad m => RecStateT sms getFuture = RecStateT ask putPresent :: Monad m => s -> RecStateT sm () putPresent = RecStateT . put

关于你的第二个问题，这将有助于了解你的数据stream（即有一个你的代码的最小例子）。 严格的模式总是会导致循环，这是不正确的。 确实，你需要小心，以免造成不生产循环，但确切的限制取决于你build立的是什么和如何。

我有点不知所措的Monad使用量。 我可能不了解过去/将来的事情，但我想你只是想expression懒惰+固定点绑定。 （纠正我，如果我错了） RWS Monad用法与R = W是有趣的，但你不需要State和loop ，当你可以做同样的fmap 。 如果他们不使事情变得简单，使用Monad是毫无意义的。 （无论如何，只有很less的Monad代表时间顺序。）

我打结的一般解决scheme：

  1. 我将所有内容parsing为一个节点列表，
  2. 将该列表转换为Data.Vector以便O（1）访问装箱（=懒惰）值，
  3. 将该结果绑定到使用let或fix或mfix函数的名称，
  4. 并在分析器中访问名为Vector的内容。 （ 见 1）

在你的博客 ，你写的东西的example解决scheme。 喜欢这个： 

 data Node = Node { value :: Int, next :: Node } deriving Show … tie = … parse = … data ParserState = … … example :: Node example = let (_, _, m) = tie parse $ ParserState 0 [(0, 1), (1, 2), (2, 0)] in (m Map.! 0)

我会这样写： 

 {-# LANGUAGE ViewPatterns, NamedFieldPuns #-} import Data.Vector as Vector example :: Node example = let node :: Int -> Node node = (Vector.!) $ Vector.fromList $ [ Node{value,next} | (value,node->next) <- [(0, 1), (1, 2), (2, 0)] ] in (node 0)

或更短： 

 {-# LANGUAGE ViewPatterns, NamedFieldPuns #-} import Data.Vector as Vector example :: Node example = (\node->(Vector.fromList[ Node{value,next} | (value,node->next) <- [(0, 1), (1, 2), (2, 0)] ] Vector.!)) `fix` 0

我最近有类似的问题，但我select了一个不同的方法。 recursion数据结构可以表示为数据types函子的types定点。 加载数据可以分为两部分：

  • 将数据加载到仅通过某种标识符引用其他节点的结构中。 在这个例子中，它是Loader Int (NodeF Int) ，它构造了NodeF Int Inttypes的值的映射。
  • 通过用实际数据replace标识符来创build一个recursion数据结构来连接结。 在这个例子中，生成的数据结构具有typesFix (NodeF Int) ，为了方便起见，它们稍后转换为Node Int 。

这是缺乏适当的error handling等，但这个想法应该是明确的。 

 -- Public Domain import Control.Monad import Data.Map (Map) import qualified Data.Map as Map import Data.Maybe (fromJust) -- Fixed point operator on types and catamohism/anamorphism methods -- for constructing/deconstructing them: newtype Fix f = Fix { unfix :: f (Fix f) } catam :: Functor f => (fa -> a) -> (Fix f -> a) catam f = f . fmap (catam f) . unfix anam :: Functor f => (a -> fa) -> (a -> Fix f) anam f = Fix . fmap (anam f) . f anam' :: Functor f => (a -> fa) -> (fa -> Fix f) anam' f = Fix . fmap (anam f) -- The loader itself -- A representation of a loader. Type parameter 'k' represents the keys by -- which the nodes are represented. Type parameter 'v' represents a functor -- data type representing the values. data Loader kv = Loader (Map k (vk)) -- | Creates an empty loader. empty :: Loader kv empty = Loader $ Map.empty -- | Adds a new node into a loader. update :: (Ord k) => k -> vk -> Loader kv -> Loader kv update kv = update' k (const v) -- | Modifies a node in a loader. update' :: (Ord k) => k -> (Maybe (vk) -> (vk)) -> Loader kv -> Loader kv update' kf (Loader m) = Loader $ Map.insertWith (const (f . Just)) k (f Nothing) $ m -- | Does the actual knot-tying. Creates a new data structure -- where the references to nodes are replaced by the actual data. tie :: (Ord k, Functor v) => Loader kv -> Map k (Fix v) tie (Loader m) = Map.map (anam' $ \k -> fromJust (Map.lookup km)) m -- ----------------------------------------------------------------- -- Usage example: data NodeF nt = NodeF n [t] instance Functor (NodeF n) where fmap f (NodeF n xs) = NodeF n (map f xs) -- A data structure isomorphic to Fix (NodeF n), but easier to work with. data Node n = Node n [Node n] deriving Show -- The isomorphism that does the conversion. nodeunfix :: Fix (NodeF n) -> Node n nodeunfix = catam (\(NodeF n ts) -> Node n ts) main :: IO () main = do -- Each node description consist of an integer ID and a list of other nodes -- it references. let lss = [ (1, [4]) , (2, [1]) , (3, [2, 1]) , (4, [3, 2, 1]) , (5, [5]) ] print lss -- Fill a new loader with the data: let loader = foldr f empty lss f (label, dependsOn) = update label (NodeF label dependsOn) -- Tie the knot: let tied' = tie loader -- And convert Fix (NodeF n) into Node n: let tied = Map.map nodeunfix tied' -- For each node print the label of the first node it references -- and the count of all referenced nodes. print $ Map.map (\(Node n ls@((Node n1 _) : _)) -> (n1, length ls)) tied
    Interesting Posts

    “打结”解释