Функция нерекурсивного списка с Y Combinator - PullRequest
Новая
       65

Функция нерекурсивного списка с Y Combinator

2 голосов
/ 24 ноября 2011

Примечание: это своего рода домашняя работа, а не - конечная цель - иметь функцию, которая производит набор мощности из набора чисел, предоставляемых функции в виде списка чисел. Я являюсь рекурсивной версией функции, но теперь мне нужно найти несколько способов замены каждой неявно рекурсивной функции в моем решении (append, mapm и т. Д.) Эквивалентным лямбда-выражением. Таким образом, я начинаю с более мелких проблем и надеюсь объединить их все, чтобы написать полную функцию. Мне удалось придумать нерекурсивную факториальную функцию с использованием pure-lambda (y-comb), но сейчас я пытаюсь придумать красивую функцию, которая возводит в квадрат каждое число в списке - пытаясь решить более мелкие проблемы, прежде чем прыгать до многократно рекурсивной функции. 

(define (sqrlist numlist)
  (((lambda (f)
   ((lambda (x) (x x))
    (lambda (g)
     (f (lambda (x) ((g g) x))))))
  (lambda (f)
   (lambda (x)
    (cons (sqr (first x)) (rest x)))))numlist))

Приведенный выше код не повторяется, несмотря на наличие перед ним y-комбинатора - у меня, очевидно, есть некоторые проблемы с передачей соответствующих параметров функциям внутри - есть идеи?

Ответы [ 2 ]

4 голосов
/ 01 декабря 2011

Если у вас есть рабочая процедура, преобразование в анонимные процедуры является относительно простым и механическим. Дайте каждой лямбде дополнительный аргумент, который является «собой», и продублируйте процедуру. Так 

(define (add-list list) 
  (if (empty? list) 
      0 
      (+ (first list) (add-list (rest list)))))

Становится 

(λ(list) (if (empty? list) 0 (+ (first list) (add-list (rest list)))))

Это, конечно, проблема, потому что add-list не определено. Таким образом, мы должны быть уверены, что каждый раз обходим себя. 

(λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))

Но где мы можем получить себя в первую очередь? Ну, мы копируем и вставляем (и приводим аргумент) 

((λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 (λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 '(1 2 3 4))

Абстракция этого «копирования и вставки» к y-комбинатору великолепно разработана в «Почему из Y», и вам обязательно стоит это проверить.

Но помните, что первым шагом было «заставить его работать». Сделайте это, прежде чем абстрагироваться define s.

0 голосов
/ 24 ноября 2011

Вот возможный ответ, я знаю, что вы уже решили это, но было бы полезно иметь второе мнение:) 

((lambda (X)
    ((lambda (proc)
       (proc proc))
     (lambda (proc)
       (X (lambda (arg)
            ((proc proc) arg))))))
  (lambda (sqrlist)
    (lambda (lst)
      (if (null? lst)
          '()
          (cons (* (car lst) (car lst))
                (sqrlist (cdr lst)))))))

Это «только лямбда», так как написано исключительно с точки зренияанонимные функции, он даже не использует define.Вот как это назвать: 

(((lambda (X)
     ((lambda (proc)
        (proc proc))
      (lambda (proc)
        (X (lambda (arg)
             ((proc proc) arg))))))
   (lambda (sqrlist)
     (lambda (lst)
       (if (null? lst)
           '()
           (cons (* (car lst) (car lst))
                 (sqrlist (cdr lst)))))))
 '(1 2 3 4 5))
...