parsing - 如何根据输出消耗的数据量使该解析代码变得懒惰？

Question

有人知道如何使代码变得惰性和非严格，以便在解析输入数据时生成 AST 树吗？目前使用的列表输入是从左到右读取的，但是是反向构造的。因此我不得不在两个地方使用“reverse”。

type Program = [Instruction]
data Instruction = Next | Prev | Plus | Minus | Print | Loop [Instruction] deriving Show

parse :: String -> Program
parse ys = reverse exps where
        (exps, _) = parse' ys []
        parse' [] is     = (is, [])
        parse' (x:xs) is = case x of
                            '>' -> parse' xs (Next:is)
                            '<' -> parse' xs (Prev:is)
                            '+' -> parse' xs (Plus:is)
                            '-' -> parse' xs (Minus:is)
                            '.' -> parse' xs (Print:is)
                            '[' -> parse' after $ Loop (reverse inside):is where (inside, after) = parse' xs []
                            ']' -> (is, xs)
                            _   -> parse' xs is

Answer 1

如果您希望它是惰性的，那么您的函数需要返回如下所示的值:

instr1 : instr2 : ... : <thunk>

哪里<thunk>是其余的计算。对我来说，这表明您的函数应该如下所示:

parse [] = []
parse (x:xs) = instr : parse xs
  where instr = ...

不知道你是故意的还是无意的，但是那个辅助parse'带有额外参数的函数(在其中累积结果)正是您用来从严格语言中获得性能的模式(如果它支持尾部调用消除)。尾递归实际上是这里的敌人!

带有累加器的尾递归函数几乎必然是非惰性的，因为直到您达到基本情况并决定如何处理最终累加器值时，才能知道输出的第一个“部分”。因此，在处理整个输入时，要求输出的消费者必须等待，并且整个输出必须缓冲在内存中。

惰性递归代码最明显的秘诀是让您的函数返回应用于某些字段的数据构造函数(在本例中为 : )，其中您的递归调用存储在一个(或多个)田野。这允许使用者在要求递归调用的输出之前检查构造函数和您生成的任何其他字段。

这也意味着，如果您正在编写一个生成递归数据类型的递归函数，并且希望它是惰性的，那么您通常最终会在返回类型的结构之后构建函数 - 这正是递归使用者通常镜像的方式它们的输入类型的结构。例如。原型(prototype)列表生成器需要一个返回 [] 的案例。和一个返回 something : recursiveCall 的案例.