9

为了学习Clojure，我正在解决4clojure的问题。我目前正在对问题164咬牙切齿，您将在其中列举（部分）DFA接受的语言。一个有趣的条件是语言可能是无限的，所以解决方案必须是惰性的（在这种情况下，解决方案的测试用例(take 2000 ....

我有一个可以在我的机器上运行的解决方案，但是当我在网站上提交它时，它会炸毁堆栈（如果我将要确定的可接受字符串的数量从 2000 增加到 20000，我也会在本地炸毁堆栈，所以这是一个我的解决方案的缺陷）。

我的解决方案[1] 是：

(fn [dfa]
  (let [start-state (dfa :start)
        accept-states (dfa :accepts)
        transitions (dfa :transitions)]
    (letfn [
      (accept-state? [state] (contains? accept-states state))

      (follow-transitions-from [state prefix]
          (lazy-seq (mapcat 
            (fn [pair] (enumerate-language (val pair) (str prefix (key pair))))
            (transitions state))))

      (enumerate-language [state prefix]
        (if (accept-state? state) 
          (cons prefix (follow-transitions-from state prefix))
          (follow-transitions-from state prefix)))
      ]   
      (enumerate-language start-state ""))
  )
)

它接受 DFA

'{:states #{q0 q1 q2 q3}
              :alphabet #{a b c}
              :start q0
              :accepts #{q1 q2 q3}
              :transitions {q0 {a q1}
                            q1 {b q2}
                            q2 {c q3}}}

并返回 DFA 接受的语言 ( #{a ab abc})。但是，在确定 DFA 的前 2000 个接受的字符串时

(take 2000 (f '{:states #{q0 q1} 
                           :alphabet #{0 1}
                           :start q0
                           :accepts #{q0}
                           :transitions {q0 {0 q0, 1 q1} 
                                         q1 {0 q1, 1 q0}}}))

它炸毁了堆栈。显然我应该将解决方案重组为尾递归，但我不明白这是怎么可能的。特别是，我看不到如何将惰性与尾递归结合起来（通过recuror 或trampoline）。该lazy-seq函数创建了一个闭包，因此使用recurinsidelazy-seq将使用闭包作为递归点。当使用lazy-seqinsiderecur时，lazy-seq总是会评估，因为recur发出一个需要评估其参数的函数调用。

使用时trampoline，我看不到如何迭代地构造一个可以懒惰地评估其元素的列表。正如我使用它并看到它使用的那样，trampoline它只能在它最终完成时返回一个值（即其中一个蹦床函数不返回函数）。

其他解决方案被认为超出范围

我认为这个 4Clojure 问题的另一种解决方案超出了这个问题的范围。我目前正在使用 解决方案iterate，其中每个步骤仅计算“下一步”（从当前状态转换之后）接受的字符串，因此它根本不会递归。然后，您只需跟踪当前状态和使您进入该状态的字符串（它们是下一个状态的前缀）。在这种情况下，困难在于检测何时接受有限语言的 DFA 将不再返回任何结果。我还没有为take-while周围环境设计一个适当的停止标准iterate，但我很确定我会设法让这个解决方案发挥作用。对于这个问题，我对基本问题感兴趣：可以将惰性和尾递归结合起来还是根本不可能？

[1] 请注意，该站点存在一些限制，例如无法使用defand defn，这可能解释了我的代码的一些特殊性。

4

2 回答 2

7

使用时lazy-seq只需进行常规函数调用而不是使用recur. recur惰性避免了否则使用的递归堆栈消耗。

例如，简化版本repeat：

（定义重复 [x]
  （惰性序列（cons x（重复 x））））
于 2012-07-16T01:14:23.507 回答
2

问题是您正在构建的东西看起来像：

(mapcat f (mapcat f (mapcat f ...)))

原则上这很好，但是这个列表最右边的元素很长时间没有被实现，当你真正意识到它们时，它们有一大堆惰性序列需要强制按顺序排列得到一个元素。

如果你不介意剧透，你可以在https://gist.github.com/3124087看到我的解决方案。我做的两件事与你不同，两者都很重要：

  1. 遍历树的广度优先。如果这是一个不接受的状态，你不想在从 q0 到 q0 的循环中“卡住”。由于转换传递给您的顺序，对于您失败的特定测试用例来说，这看起来不是问题，但是在此之后的下一个测试用例确实具有该特征。
  2. 用来doall强制我正在懒惰地构建一个序列。因为我知道很多concats会构建一个非常大的堆栈，而且我也知道序列永远不会是无限的，所以我在构建它时强制整个事情，以防止延迟序列的分层导致堆栈溢出。

编辑：一般来说，你不能将惰性序列与尾递归结合起来。您可以拥有一个同时使用它们的函数，当在添加单个元素之前有更多工作要做时可能会重复出现，并且在有新元素时会延迟重复出现，但大多数时候它们的目标相反并试图组合他们不小心只会导致痛苦，并没有特别的改善。

于 2012-07-16T18:16:44.953 回答