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

Question

Примечание: это своего рода домашняя работа, а не какая-то - конечная цель - иметь функцию, которая производит набор параметров для набора чисел, передаваемого этой функции в виде списка чисел. Я являюсь рекурсивной версией функции, но теперь мне нужно найти несколько способов заменить каждую неявно рекурсивную функцию в моем решении (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-комбинатора перед ним - у меня, очевидно, есть некоторые проблемы с передачей соответствующих параметров функциям внутри - есть идеи?

Answer 1

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

(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", и вы обязательно должны это проверить.

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

Answer 2

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

((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))