首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >在Clojure中,是否有可能将回忆录和尾调用优化结合起来?

在Clojure中,是否有可能将回忆录和尾调用优化结合起来?
EN

Stack Overflow用户
提问于 2012-03-27 21:34:52
回答 4查看 2.4K关注 0票数 15

在clojure中,我想编写一个尾递归函数,该函数将其中间结果回溯到后续调用中。

编辑:这个问题是用gcd代替factorial重写的。

回忆录的gcd (最大的公共除数)可以这样实现:

代码语言:javascript
运行
复制
(def gcd (memoize (fn [a b] 
   (if (zero? b) 
       a 
       (recur b (mod a b)))) 

在此实现中,中间结果不用于后续调用。例如,为了计算gcd(9,6),调用gcd(6,3)作为中间结果。但是,gcd(6,3)没有存储在回忆录函数的缓存中,因为recur的递归点是未回传的匿名函数。

因此,如果在调用gcd(9,6)之后,我们称之为gcd(6,3),那么我们将无法从回忆录中获益。

我能想到的唯一解决方案是使用普通的递归(可以明确地调用gcd而不是recur),但是这样我们就不会从尾调用优化中获益。

底线

是否有办法做到这两点:

  1. 尾叫优化
  2. 对后续调用的中间结果的记忆

备注

  1. 这个问题类似于结合回忆录和尾递归。但所有的答案都与F#有关。在这里,我正在寻找一个clojure的答案。
  2. 这个问题是克洛尔的Joy留给读者的练习(第12.4章)。您可以在http://bit.ly/HkQrio查阅这本书的相关页面。
EN

回答 4

Stack Overflow用户

发布于 2012-03-28 06:45:30

代码语言:javascript
运行
复制
(defmacro memofn
  [name args & body]
  `(let [cache# (atom {})]
     (fn ~name [& args#]
       (let [update-cache!# (fn update-cache!# [state# args#]
                              (if-not (contains? state# args#)
                                (assoc state# args#
                                       (delay
                                         (let [~args args#]
                                           ~@body)))
                                state#))]
         (let [state# (swap! cache# update-cache!# args#)]
           (-> state# (get args#) deref))))))

这将允许递归定义回传函数,该函数还缓存中间结果。用法:

代码语言:javascript
运行
复制
(def fib (memofn fib [n]
           (case n
             1 1
             0 1
             (+ (fib (dec n)) (fib (- n 2))))))
票数 2
EN

Stack Overflow用户

发布于 2012-03-30 10:16:45

代码语言:javascript
运行
复制
(def gcd 
  (let [cache (atom {})]
    (fn [a b]
      @(or (@cache [a b])
         (let [p (promise)]
           (deliver p
             (loop [a a b b]
               (if-let [p2 (@cache [a b])]
                 @p2
                 (do
                   (swap! cache assoc [a b] p)
                   (if (zero? b) 
                     a 
                     (recur b (mod a b))))))))))))

有一些并发问题(双重评估,与回忆录相同的问题,但更糟糕的是,因为承诺),这些问题可以用@kotarak的建议来解决。

将上述代码转换为宏是留给读者的练习。(福格斯的笔记是国际海事组织开玩笑的。)

将其转化为宏实际上是一项简单的宏操作,请注意身体(最后三行)保持不变。

票数 2
EN

Stack Overflow用户

发布于 2012-03-27 21:54:24

使用Clojure的重述,您可以使用没有堆栈增长的累加器编写阶乘,只需回溯:

代码语言:javascript
运行
复制
(defn fact
  ([n]
     (fact n 1))
  ([n acc]
     (if (= 1 n)
       acc
       (recur (dec n)
              (* n acc)))))
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9898069

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档