clojure - 使用lazy-seq无需删除堆栈: is it possible to combine laziness with tail recursion?

Question

要学习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}}}))

它炸毁了堆栈。显然，我应该将解决方案重组为尾递归，但是我不知道这是怎么可能的。特别是，我什至看不到如何将懒惰与尾递归结合在一起(通过recur或trampoline)。 lazy-seq函数创建一个闭包，因此在recur中使用lazy-seq会将闭包用作递归点。在lazy-seq中使用recur时，始终会评估lazy-seq，因为recur会发出需要评估其参数的函数调用。

当使用trampoline时，我看不到如何迭代构造一个列表，该列表的元素可以被惰性计算。正如我所使用并看到的那样，trampoline仅在最终完成时才返回一个值(即一个蹦床函数不返回函数)。

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

我认为这个问题不在4Clojure问题的另一种解决方案内。我目前正在使用iterate解决方案，其中每个步骤仅计算“下一步”(跟随从当前statew进行的转换)接受的字符串，因此它根本不会递归。然后，您只需跟踪当前状态和使您进入该状态的字符串(这是下一个状态的前缀)。在那种情况下，证明困难的是检测何时接受有限语言的DFA不再返回任何结果。我尚未针对take-while周围的iterate设计适当的停止条件，但是我敢肯定，我将设法使该解决方案生效。对于这个问题，我对以下基本问题感兴趣:可以将懒惰和尾递归结合起来，还是从根本上说不可能？

[1]请注意，网站上有一些限制，例如无法使用def和defn，这可能解释了我的代码的某些特殊性。

Answer 1

问题是您正在构建类似以下内容的东西:

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

原则上讲这很好，但是此列表最右边的元素不会被长时间实现，并且当您意识到它们时，它们具有大量的惰性序列，需要按顺序进行强制执行得到一个元素。

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

遍历树的宽度优先。如果这是一种 Not Acceptable 状态，则您不想陷入从q0到q0的循环中。对于您失败的特定测试用例来说，这似乎不是问题，因为转换被传递给您的顺序很大，但是此后的下一个测试用例确实具有该特性。

使用doall强制延迟构建的序列。因为我知道许多concat会构建一个非常大的堆栈，并且我也知道该序列永远不会是无限的，所以我在构建它时会强制执行整个过程，以防止导致堆栈溢出的惰性序列分层。

编辑:通常，您不能将延迟序列与尾递归结合在一起。您可以使用一个函数同时使用这两个函数，也许在添加单个元素之前需要做更多工作时重复出现，而在有新元素出现时则懒惰重复出现，但是大多数情况下它们的目标是相反的并试图合并他们不谨慎地只会导致痛苦，而没有特别的改善。