Clojure中s表达式列表的递归

Question

为了设置一些上下文,我正在学习Clojure,并且更普遍地学习Lisp.在我的Lisp之路上,我目前正在研究"Little"系列,以巩固功能编程和基于递归的解决方案的基础.在"The Little Schemer"中,我已经完成了许多练习,但是,我正在努力将其中的一些转换为Clojure.更具体地说,我正在努力将它们转换为使用"recur"以便启用TCO.例如,这里是一个基于Clojure的实现,来自"发生*"函数(来自Little Schemer),它计算出在S表达式列表中出现的原子的出现次数:

(defn atom? [l]
  (not (list? l)))

(defn occurs [a lst]
  (cond
   (empty? lst) 0
   (atom? (first lst))
    (cond
     (= a (first lst)) (inc (occurs a (rest lst)))
     true (occurs a (rest lst)))
   true (+ (occurs a (first lst))
           (occurs a (rest lst)))))

基本上,(occurs 'abc '(abc (def abc) (abc (abc def) (def (((((abc)))))))))将评估为5.显而易见的问题是,如果给出一个S表达式列表太深,这个定义会消耗堆栈帧并且会破坏堆栈.

现在,我理解重构递归函数的选项,以使用累加器参数来启用将递归调用放入尾部位置(以允许TCO),但是如果此选项甚至适用于此类情况,我也在苦苦挣扎.

如果我尝试使用"recur"和使用累加器参数来重构这个,那么这里有多远:

(defn recur-occurs [a lst]
  (letfn [(myoccurs [a lst count]
            (cond
             (empty? lst) 0
             (atom? (first lst))
             (cond
              (= a (first lst)) (recur a (rest lst) (inc count))
              true (recur a (rest lst) count))
             true (+ (recur a (first lst) count)
                     (recur a (rest lst) count))))]
    (myoccurs a lst 0)))

所以,我觉得我差不多了,但并不完全.显而易见的问题是我的"else"子句,其中列表的头部不是原子.从概念上讲,我想在列表中的第一个元素上重复结果,并在列表的其余部分重复结果.我正在努力解决这个问题,以便将重复移动到尾部位置.

是否存在"累加器"模式的其他技术,以实现将您的递归调用置于我应该应用的尾部位置,或者,问题是更"基本",并且没有基于Clojure的干净解决方案由于JVM缺乏TCO？如果是后者,一般来说,Clojure程序使用的一般模式应该是什么,需要重复一个S表达式列表？为了它的价值,我已经看到使用了多种方法w/lazy-seq技术(Halloway的"Programming Clojure"的第151页作为参考)"用Laziness替换递归" - 但我不确定如何应用该模式在这个例子中,我没有尝试构建列表,而是计算单个整数值.

提前感谢您对此的任何指导.

Answer 1

首先,我必须建议你不要担心堆栈溢出等实现障碍,因为你通过The Little Schemer.当你在愤怒编程时缺乏尾调优化这样的问题是很好的,但本书的要点是教你递归思考.转换示例累加器传递样式当然是一种很好的做法,但它实际上放弃了递归,转而支持迭代.

但是,我必须在前面加上一个扰流警告,有一种方法可以保持相同的递归算法而不受JVM堆栈的影响.我们可以使用continuation-passing风格以额外的匿名函数参数的形式创建我们自己的堆栈k:

(defn occurs-cps [a lst k]
  (cond
   (empty? lst) (k 0) 
   (atom? (first lst))
   (cond
    (= a (first lst)) (occurs-cps a (rest lst)
                                  (fn [v] (k (inc v))))
    :else (occurs-cps a (rest lst) k))
   :else (occurs-cps a (first lst)
                     (fn [fst]
                       (occurs-cps a (rest lst)
                                   (fn [rst] (k (+ fst rst))))))))

我们的非尾函数调用不是隐式创建堆栈,而是在每次调用之后捆绑"剩下要做的事情" occurs,并将其作为下一个延续传递k.当我们调用它时,我们从一个k代表什么的东西开始,即身份函数:

scratch.core=> (occurs-cps 'abc 
                           '(abc (def abc) (abc (abc def) (def (((((abc)))))))) 
                           (fn [v] v))
5

我将不再详细介绍如何进行CPS,因为这是TLS的后续章节.但是,我会注意到这当然还没有完全奏效:

scratch.core=> (def ls (repeat 20000 'foo))          
#'scratch.core/ls
scratch.core=> (occurs-cps 'foo ls (fn [v] v))       
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

CPS允许我们将所有非平凡的堆栈构建调用移动到尾部位置,但在Clojure中,我们需要采取额外的步骤来替换它们recur:

(defn occurs-cps-recur [a lst k]
  (cond
   (empty? lst) (k 0)
   (atom? (first lst))
   (cond
    (= a (first lst)) (recur a (rest lst)
                             (fn [v] (k (inc v))))
    :else (recur a (rest lst) k))
   :else (recur a (first lst)
                (fn [fst]
                  (recur a (rest lst) ;; Problem
                         (fn [rst] (k (+ fst rst))))))))

唉,这是错的:java.lang.IllegalArgumentException: Mismatched argument count to recur, expected: 1 args, got: 3 (core.clj:39).最后一个recur实际上指的是fn它上面的右边,我们用它来表示我们的延续!我们可以通过将其更改recur为调用来获得良好的行为occurs-cps-recur,但是病态嵌套的输入仍会溢出堆栈:

scratch.core=> (occurs-cps-recur 'foo ls (fn [v] v))
20000
scratch.core=> (def nested (reduce (fn [onion _] (list onion)) 
                                   'foo (range 20000)))
#'scratch.core/nested
scratch.core=> (occurs-cps-recur 'foo nested (fn [v] v))
Java.lang.StackOverflowError (NO_SOURCE_FILE:0)

occurs-*我们可以让它立即返回一个thunk,而不是调用并期望它回复一个答案.当我们调用那个thunk时,它会立即执行一些工作,直到它执行递归调用,这反过来将返回另一个thunk.这是蹦床的风格,"反弹"我们的thunk的功能trampoline.每次我们进行递归调用时返回thunk一次将我们的堆栈大小限制为一次调用,所以我们唯一的限制是堆:

(defn occurs-cps-tramp [a lst k]
  (fn [] 
    (cond
     (empty? lst) (k 0) 
     (atom? (first lst))
     (cond
      (= a (first lst)) (occurs-cps-tramp a (rest lst)
                                          (fn [v] (k (inc v))))
      :else (occurs-cps-tramp a (rest lst) k))
     :else (occurs-cps-tramp a (first lst)
                             (fn [fst]
                               (occurs-cps-tramp a (rest lst)
                                                 (fn [rst] (k (+ fst rst)))))))))

(declare done answer)

(defn my-trampoline [th]
  (if done
    answer
    (recur (th))))

(defn empty-k [v]
  (set! answer v)
  (set! done true))

(defn run []
  (binding [done false answer 'whocares]
    (my-trampoline (occurs-cps-tramp 'foo nested empty-k))))

;; scratch.core=> (run)                             
;; 1

请注意,Clojure具有内置功能trampoline(对返回类型有一些限制).使用它,我们不需要专门的empty-k:

scratch.core=> (trampoline (occurs-cps-tramp 'foo nested (fn [v] v)))
1

蹦床当然是一种很酷的技术,但蹦床程序的先决条件是它必须只包含尾调用; CPS是这里真正的明星.它允许您使用自然递归的清晰度定义算法,并通过保持正确性的转换,在具有单个循环和堆的任何主机上有效地表达它.

Answer 2

使用固定数量的内存不能这样做.你可以使用堆栈或堆; 这是你做出的决定.如果我是用Clojure写这个我会做它用map,并reduce而不是手动递归:

(defn occurs [x coll]
  (if (coll? coll)
    (reduce + (map #(occurs x %) coll))
    (if (= x coll)
      1, 0)))

请注意,如果您使用tree-seq或存在较短的解决方案flatten,但此时大部分问题都已消失,因此无需学习.

编辑

这是一个不使用任何堆栈的版本,而是让它的队列变得越来越大(使用堆栈).

(defn heap-occurs [item coll]
  (loop [count 0, queue coll]
    (if-let [[x & xs] (seq queue)]
      (if (coll? x)
        (recur count (concat x xs))
        (recur (+ (if (= item x) 1, 0)
                  count)
               xs))
      count)))