The Way 2 Inner Peace.

闭包
欧拉项目第65题.

得到Y组合子

Qians posted @ 2012年12月09日 15:15 in scheme with tags Scheme , 2624 阅读

我把Y组合子是什么给忘了.回顾了下手头的东西.发现还是the little schemer里讲的最明白.现整理如下.

有如下可获得list长度的函数length:

(define (length l)
    (cond
      [(null? l) 0]
      [else (add1 (length (cdr l)))]))

可以看到length的定义中调用了自身.如果现在我们没有define,那么我们该怎样得到length呢?

 

  1. 已知.如果一个列表为空.那么它的长度是0.所以毫无疑问.可以得到一个返回空列表长度0的函数(这是一句废话. -_-!).那么就给它取个名字length0.因为它的输入只能是空列表.对于其他的输入.随便给个什么.空值.错误.或者死循环都好.因为我们根本不会用它去求非空列表的长度.

     

    (λ(l)
      (cond
        [(null? l) 0]
        [else (add1 (void (cdr l)))]))

    那么有了length0,就可以得到length1.依次类推可以得到length2,length3....length1如下.

    (λ(l)
      (cond
        [(null? l) 0]
        [else (add1 ((λ(l)
                       (cond
                         [(null? l) 0]
                         [else (add1 (void))]))
                     (cdr l)))]))
    

    length1可以得到空列表或者只含一个元素的列表的长度.

     

  2. 现在再来看length0.可以将void作为参数传入,那么length0又可以写成.

     

    ((λ(length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 (length (cdr l)))])))
     void)

    同理,length1可以写成

    ((λ(length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 (length (cdr l)))])))
     ((λ(length)
        (λ(l)
          (cond
            [(null? l) 0]
            [else (add1 (length (cdr l)))])))
      void))

     

  3. 再抽象一抽.它还是length0

     

    ((λ (mk-length)
       (mk-length void))
     (λ(length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

    length1:

    ((λ (mk-length)
       (mk-length (mk-length void)))
     (λ(length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

     

  4. 既然void是期望中永远都不会用到的东西.那么把mk-length传入它自己也没有什么问题吧.得到下面这样的length0

     

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 (mk-length (cdr l)))]))))

    再调用一次.得到length1:

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 ((mk-length void) (cdr l)))]))))

    (notes:I dont know how to write length2)

     

  5. 让mk-length不停的调用自己.就得到了length:

     

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else (add1 ((mk-length mk-length)(cdr l)))]))))
    

     

  6. 如果将(mk-length mk-length)作为参数.即写为:

     

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       ((λ(length)
          (λ(l)
            (cond
              [(null? l) 0]
              [else 
               (add1 
                (length(cdr l)))])))
        (mk-length mk-length))))

    这样是不行的.这样mk-length 会不停的调用自己.陷入死循环.

     

  7. 因为

     

    (λ(x)
      ((mk-length mk-length)x))

    既是

    (mk-length mk-length)

    所以

    length可以写做:

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else
            (add1 
             ((λ(x)
                ((mk-length mk-length)x))(cdr l)))]))))

    此时.用lambda包装过(mk-length mk-length)的就可以写做参数传入了,即:

    ((λ (mk-length)
       (mk-length mk-length))
     (λ(mk-length)
       ((λ(length)
          (λ(l)
            (cond
              [(null? l) 0]
              [else
               (add1 
                (length
                 (cdr l)))])))
        (λ(x)
          ((mk-length mk-length)x)))))

     

  8. 将最像length的那部分移出来,就得到了应用序的Y组合子.这就是不用define的length:

     

    ((λ(le)
       ((λ (mk-length)
          (mk-length mk-length))
        (λ(mk-length)
          (le
           (λ(x)
             ((mk-length mk-length)x))))))
     (λ(length)
       (λ(l)
         (cond
           [(null? l) 0]
           [else
            (add1 
             (length
              (cdr l)))]))))

    Y组合子就是这样的:

    (λ(le)
       ((λ (f)
          (f f))
        (λ(f)
          (le(λ(x)
               ((f f)x))))))

    改个名字.加个语法糖:

    (lambda (le)
      (let ([g (λ(f)
                 (le(λ(x)
                      ((f f)x))))])
        (g g)))

    试试不用define的fact

    ((lambda (le)
      (let ([f (λ(f)
                 (le(λ(x)
                      ((f f)x))))])
        (f f)))
       (λ(fact)
         (lambda (n)
        (if (< n 2) 1 (* n (fact (- n 1)))))))

 

参考: The Little Schemer

AP 10th Science Mode 说:
2022年9月19日 00:23

AP 10th Class Science Model Paper 2023 Pdf Download may useful to both Telugu Medium, English Medium and Urdu Medium 10th class students of the state board to score better marks in the exams like SA-1, SA-2, FA-1, FA-2, FA-3, FA-4. AP 10th Science Model PaperThese practice model papers not only helped in getting marks but also improve the student’s knowledge of science.AP 10th Science Model Paper 2023 Pdf with answers suggested for all kinds of exams held under BSEAP along with assignments were made with the instructions of Leading educational institutes, Education portals of the state such as Sakshi Education, Eenadu Pratibha.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter