;;;; Lisp

; 用于测试的高阶函数,反正每个人都用这个例子,所以我也用
(defun factn (self)
  #'(lambda (n)
        (if (< n 1)
             1
                 (* n (funcall self (- n 1))))))

    ; Y1 = λf. (λx. f (x x)) (λx. f (x x))
    ; 最初的定义,不适用于传值调用,所以会 stack overflow
    (defun Y2com (f)
       (funcall
            #'(lambda (x)
                      (funcall f (funcall x x)))
            #'(lambda (x)
                      (funcall f (funcall x x)))))

    ; Y2 = λf. (λp. p p) (λx. f (λy. x x y))
    ; 相当于:
    ;     p  = λx. f (λy. x x y)
    ;     Y1 = λf. p p
    ; 所以实际上这个也是 Z 组合子
    (defun Y2com (f)
       (funcall
            #'(lambda (p)
                      (funcall p p))
            #'(lambda (x)
                      (funcall f
                               #'(lambda (&rest y)
                                             (apply (funcall x x) y))))))

    ; Z1 = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
    ; Z 组合子最初的定义
    (defun Z1com (f)
       (funcall
            #'(lambda (x)
                      (funcall f
                               #'(lambda (&rest y)
                                             (apply (funcall x x) y))))
            #'(lambda (x)
                      (funcall f
                               #'(lambda (&rest y)
                                             (apply (funcall x x) y))))))

    ; Z2 = λf. (λx. (λy. f (x x) y)) (λx. (λy. f (x x) y))
    ; 我实现的第一个版本,不过显然地与 Z1 等价
    (defun Z2com (f)
      (funcall
         #'(lambda (x)
                 #'(lambda (&rest y)
                           (apply (funcall f (funcall x x)) y)))
         #'(lambda (x)
                 #'(lambda (&rest y)
                           (apply (funcall f (funcall x x)) y)))))

    ; 柯里化
    (defun curry (fn &rest args)
       #'(lambda (&rest args2)
               (apply fn (append args args2))))

    ; 右参数柯里化
    (defun rcurry (fn &rest args)
       #'(lambda (&rest args2)
               (apply fn (append args2 args))))