在使用可以消耗任意数量元素的函数将长序列转换为较短序列时避免循环递归

Question

假设有一个标记列表和一个函数，该函数使用任意数量的标记，returns 一个语句和每次调用的剩余标记。提取所有语句直到所有标记都用完可以使用循环递归完成，如下所示：

(defn parse
  [code]
  (loop [tokens (lex code)
         statements []]
    (if (empty? tokens)
      statements
      (let [{:keys [remaining-toks statement]} (parse-statement tokens)]
        (recur remaining-toks (conj statements statement))))))

有没有不用循环递归的方法来完成这个？

Answer 1

没有 loop ... recurse 的句法将是：

(defn parse-tokens [tokens & {:keys [statements] :or {statements []}}]
  (if (empty? tokens)
      statements
      (let [{:keys [remaining-toks statement]} (parse-statement tokens)]
        (parse-tokens remaining-toks (conj statements statement)))))

(defn parse [code] (parse-tokens (lex code)))

Answer 2

使用lazy-seq延迟输出尾部的计算。

(defn- parse-tokens [tokens]
  (when (not-empty tokens)
    (let [{:keys [remaining-toks statement]} (parse-statement tokens)]
      (cons statement
            (lazy-seq (parse-tokens remaining-toks))))))

(defn parse [code]
  (parse-tokens (lex code)))

或者 iterate（假设 parse-statement returns nil 为空输入）：

(defn parse [code]
  (->> {:remaining-toks (lex code)}
       (iterate (comp parse-statement :remaining-toks))
       (next)
       (take-while some?)
       (map :statement)))

Answer 3

design notes on lazy-seq建议将cons放在里面，这使得序列中的所有项目都延迟实现，而不仅仅是尾部项目：

(defn- parse-tokens [tokens]
  (lazy-seq
    (when (seq tokens)
      (let [{:keys [remaining-toks statement]} (parse-statement tokens)]
        (cons statement (parse-tokens remaining-toks))))))

(defn parse [code]
  (parse-tokens (lex code)))

在使用可以消耗任意数量元素的函数将长序列转换为较短序列时避免循环递归

Avoid loop-recur while transforming a long sequence to a shorter one using a function that could consume an arbitrary number of elements

clojure