标签: 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 …

我正在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缺陷时应该如何表现的假设？

几年前我参加了算法课程,我们给出了以下问题(或类似的问题):

有一个n楼层的楼层,电梯一次只能上2层楼,一次只能下3层楼.使用动态编程编写一个函数,该函数将计算电梯从一层i到另一层所需的步数j.

使用有状态方法显然很容易,你创建一个数组n个元素,并用值填充它.你甚至可以使用一种技术上非有状态的方法,它涉及累积结果递归传递它.我的问题是如何通过使用延迟评估和打结来以非有状态的方式执行此操作.

我想我已经设计了正确的数学公式:

where i+2和i-3是否在允许的值范围内.

不幸的是我不能让它终止.如果我i+2首先放置案例然后选择一个偶数楼层,我可以让它来评估目标等级以下的均匀楼层,但就是这样.我怀疑它直接射向最高的平坦地板,其他一切,下降3级,然后重复,永远在最顶层的几层之间振荡.

所以它可能以深度优先的方式探索无限空间(或有限但有环).我无法想象如何以广泛的方式探索这个空间而不使用其间有效模仿状态方法的大量数据结构.

虽然这个简单的问题令人失望,但我怀疑在一维中看到了一个解决方案,我可能能够使它适用于问题的二维变化.

编辑:许多答案试图以不同的方式解决问题.问题本身对我来说并不感兴趣,问题在于使用的方法.Chaosmatter创建一个minimal可以比较潜在无限数字的函数的方法可能是朝着正确方向迈出的一步.不幸的是,如果我尝试创建一个表示100层楼的列表,结果计算时间太长,因为子问题的解决方案不会被重用.

我尝试使用自引用数据结构,但它没有终止,存在某种无限循环.我会发布我的代码,这样你就可以理解我的目标.如果有人能够在自引用数据结构上使用动态编程实际解决问题,我会改变接受的答案,使用懒惰来避免多次计算事物.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

您可以看到如何1 + levels !! i尝试引用先前计算的结果以及如何filter (\n -> n >= …

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

n <- myinstr n x

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

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

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

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

我有一个问题,我不知道如何推理.我只是想问一下是否有人可以帮助我解决具体问题,但我突然意识到我可以提出一个更普遍的问题,希望能得到一个更好的一般性理解.希望.所以这里:

当你的程序太懒,通常很明显,因为你最终会遇到像空间泄漏这样的明显问题.我有相反的问题:我的程序太严格了.我想扎 结,并发现某些事情,我试图这样做会以某种方式打败我需要的懒惰.所以我的一般问题是,如何调试不必要的严格性？

为了完整起见,这是我的具体情况:我在RWS,编写器组件填充地图,阅读器组件观察该地图的最终状态.在我完成填充之前,我不能对这张地图做任何严格的事情.在地图中查找值似乎没有问题,例如:

do
  m <- ask
  val <- m ! key
  doSomething val -- etc.

但是(!)没有使用error,我更愿意使用我的monad失败fail.所以我想做类似以下的事情:

do
  m <- ask
  maybe
    (fail "oh noes")
    (doSomething)
    (lookup key m)

这导致我的程序<<loop>>,我不明白.在我看来,这不应该比使用更严格(!),但显然我错了......

假设我有一个像这样的愚蠢的小案例类:

case class Foo(name: String, other: Foo)

我如何定义a和b不可改变这样a.other的b,而且b.other是a？scala是否提供了"打结"的方法？我想做这样的事情:

val (a, b): (Foo, Foo) = (Foo("a", b), Foo("b", a)) // Doesn't work.

可能性

在Haskell中,我会这样做:

data Foo = Foo { name :: String, other :: Foo }

a = Foo "a" b
b = Foo "b" a

绑定到a和b包含在同一let表达式中或顶层的绑定.

或者,在不滥用Haskell的自动化letrec功能的情况下:

(a, b) = fix (\ ~(a', b') -> Foo "a" b', Foo "b" …

(注意:这篇文章是一个literate-haskell文件.你可以将它复制粘贴到文本缓冲区中,保存为someFile.lhs,然后使用ghc运行它.)

问题描述:我想要创建一个具有两个不同节点类型的图形,这些节点类型相互引用.以下示例非常简化.这两个数据类型 A和B,实际上是相同的位置,但有一个原因,他们在原来的程序不同.

我们会把枯燥的东西拿走.

> {-# LANGUAGE RecursiveDo, UnicodeSyntax #-}
> 
> import qualified Data.HashMap.Lazy as M
> import Data.HashMap.Lazy (HashMap)
> import Control.Applicative ((<*>),(<$>),pure)
> import Data.Maybe (fromJust,catMaybes)

数据类型定义本身是微不足道的:

> data A = A String B
> data B = B String A

为了象征两者之间的差异,我们将给它们一个不同的 Show实例.

> instance Show A where
>   show (A a (B b _)) = a ++ ":" ++ b
> 
> instance Show B where
>   show …

正如我在上一个问题中所解释的那样,如果您的节点上没有某种独特的标签,则不可能将使用结点策略制作的两个图表区分开来.使用双刃图作为示例:

data Node = Node Int Node Node

square = a where
    a = Node 0 b c
    b = Node 1 a d
    c = Node 2 a d
    d = Node 3 b c

square由于需要手动编写标签,因此以这种方式编写有点不方便并且容易出错.这种模式通常需要monad:

square = do
    a <- Node b c
    b <- Node a d
    c <- Node a d
    d <- Node b c
    return a

但由于monads是连续的,所以也无法做到这一点.有没有方便的方法来编写结图？