递归一个 Lambda(Y combinator in Elisp)

已经有名字的函数需要递归时用名字即可,但是对于匿名的 lambda 函数来说,就需要别的方法。看了一个下午 The Y Combinator (Slight Return) - Mike’s World-O-Programming,也没搞清楚怎么回事,但是代码实现起来没什么难度:

;; 是的,需要开启词法作用区域  -*- lexical-binding: t; -*-

;; 定义一个普通的递归函数
(defun len (l)
  "求表的长度."
  (if l
      (+ 1 (len (cdr l)))
    0))

;; 测试
(len '(1 2 nil 4))
     => 4

;; 输入一个非递归函数,输出一个递归函数
(defun Y (f)
  "The strict Y combinator"
  ((lambda (x) (funcall x x))
   (lambda (x) (funcall f (lambda (&rest y) (apply (funcall x x) y))))))

;; 定义递归函数 len2,但 len2 不出现在函数定义中
(fset 'len2
      (Y (lambda (f)
           (lambda (l)
             (if l
                 (+ 1 (funcall f (cdr l)))
               0)))))

;; 测试
(len2 '(1 2 nil 4))
     => 4
1 个赞

文章确实写得…很长😄

所谓匿名,其实就是大家共用一个名字叫做[佚名]