gpt4 book ai didi

haskell - 在无状态世界中保持状态

转载 作者:行者123 更新时间:2023-12-02 18:24:04 26 4
gpt4 key购买 nike

我正在将上下文无关语法转换为 Greibach 范式 (GNF)。主要转换(来自 Hopcroft 和 Ullman)是对语法索引变量的一系列迭代。它本质上是“无状态的”。我已将其实现为适当索引上的一系列折叠(实现相当简单):

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
where step1 rl' k = foldl step2 rl' [1..k - 1]
where step2 rl'' j = noLR k (subst rl'' k j)

maxIndex rl返回一组规则中的最大变量索引; subst rl k jk 索引规则替换为右侧以 j 索引变量开头的规则。执行gnf后,我需要以相反的顺序对语法执行最后一次传递。

问题是noLR,它用左递归k索引规则转换语法。这是一个“有状态”函数,因为必须为应用 noLR 的每个规则(或 k 索引规则)生成唯一变量。所以我写了一个有状态的函数

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
let rl' = ... remove left recursion rl n ...
in return rl'

我可以将 noLR 排序在一起,以更新 noLR 作为参数的 n。不过,我不确定如何在上述函数的step2内执行noLR。我似乎无法使用 let ... in 模式,因为有状态计算嵌入在几个递归函数中。

我想要做的是让n成为某种类型的全局变量,类似于n的显式线程,我可以在内部调用和更新它步骤2,这就是为什么我最初将函数编写为带有eta-expansion(对于n)的折叠。有谁知道我如何在状态单子(monad)内构造 gnf 来实现这种效果?除了折叠中的最后一个计算之外,没有其他东西是“有状态的”,并且我只习惯将状态单子(monad)与“琐碎”的示例一起使用。我有点迷失了。

最佳答案

为了将 noLR 与您给定的类型一起使用,您必须按照以下几行重写 gnf 函数:

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
where step1 rl' k = foldM step2 rl' [1..k - 1]
where step2 rl'' j = noLR k (subst rl'' k j)

您的状态变量在整个计算过程中都存在,并且必须在代码中明确这一事实。

如果您需要的是新生成的变量名称不会相互冲突,那么您可以通过从索引 k 和 j 生成新的符号名称来使 noLR 纯粹 - 就像 k = 的“foo_42_16” = 42 和 j == 16。但是,如果输入语法已经包含此类符号名称,您可能会遇到麻烦。

如果您需要符号在语法中是唯一的,那么为什么不直接这么说呢?

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

但这绝对不是高效的,除非您用不同的类型替换 Set(规则 a),从而允许您更有效地实现 newSymbol 操作。

关于haskell - 在无状态世界中保持状态,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4259800/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com