Я очень сомневаюсь, что ваш профессор просит вас создать или использовать Y-Combinator для решения этой проблемы, но если вы хотите попробовать сделать это таким образом, вот некоторый код, который может помочь.С точки зрения непрофессионалов, y-комбинатор - это способ создания функции без необходимости что-либо определять, используя мощь лямбда-исчисления.Если у вас есть рабочее определение (которое вы упомянули, что вы делаете), то преобразовать его в лямбда-выражения не так уж сложно.Я пройдусь по шагам и постараюсь объяснить это ниже, но это очень сложная концепция и одна из самых «умопомрачительных» идей в функциональном программировании.
Обычно это следующееопределенная функция, которая будет возвращать длину данного списка:
;; mylength : [listof Any] -> Number
;; returns the length of xs
(define (mylength xs)
(if (empty? xs)
0
(+ 1 (mylength (rest xs)))))
Теперь, чтобы начать выходить из стандартной области определений и явной рекурсии, давайте сделаем mylength лямбда-выражение, которое для данной функциикоторый способен определить длину списка, возвращает длину данного списка, ys.
;; ys is a [Listof Any]
;; mylength is a function that returns the length of a list
(λ (ys)
(cond [(empty? ys) 0]
[else (+ 1 (mylength (rest ys)))]))
Проблема с этим кодом в том, что мы не хотим иметь mylength в нашем коде вообще.Чтобы правильно мыслить, помните, что весь смысл этой лямбда-функции - возвращать длину заданного списка .Пока это будет выглядеть загадочным сообщением, но вы поймете, что я имею в виду, в нескольких строках.
В любом случае, следующий шаг в выражении этого определения с использованием только лямбда-выражений состоит в том, чтобы сделать функцию длины аргументом лямбда-функции, например так:
;; ys is a [Listof Any]
(λ (len ys)
;; if ys is empty, return 0.
(if (empty? ys) 0
;; otherwise, call len again, passing len itself as it's 1st argument.
(+ 1 (len len (rest ys)))))
Вероятно, сбивать эту строку с толкуконец кода там: (+ 1 (len len (rest ys))))) В конце концов, len - это функция, которая просто берет список и возвращает его длину, верно? НЕПРАВИЛЬНО. У нас нет функции, которая принимает список и возвращает его длину - мы не можем использовать функцию, подобную первой mylength функции, упомянутой здесь.Нам нужна другая функция, цель которой - вернуть длину списка.Если вы помните, что я «загадочно» сказал несколько строчек вверх,
помните, что весь смысл этой лямбда-функции состоит в том, чтобы возвращать длину заданного списка
Итак, если эта лямбда-функция у нас возвращает длину заданного списка, а функция, которая нам нужна, возвращает длину заданного списка ... воу.Вы думаете, что я думаю?
((λ (len ys) (if (empty? ys) 0
(+ 1 (len len (rest ys)))))
(λ (len xs) (if (empty? xs) 0
(+ 1 (len len (rest xs))))) '(your list here))
"Что !?"Вы, вероятно, думаете: «Вы можете сделать это !?»
Ответ, друг мой, да.Да, ты можешь.Если вы заблудились, внимательно, внимательно, внимательно посмотрите на приведенный выше код.Давайте назовем внешнюю лямбда-функцию func 1, а внутреннюю лямбда-функцию func 2.func 1 - это та же функция, которую мы писали ранее.Эта часть имеет смысл, верно?func 1 принимает некоторую другую функцию len и список ys и пытается вернуть длину ys.Поскольку цель len в func 1 является той же самой целью , которую имеет func 1, мы можем передать то, что по сути func 1, в качестве аргумента len внешней лямбды.
Чтобы понять это немного лучше, давайте перейдем в список '(1) к нашему новому, странному лямбда-монстру:
Первый шаг:
(empty? '(1)) -> FALSE
внешняя лямбда определяет, что '(1) не пусто, поэтому он оценивает следующий шаг.
`(+ 1 (len len (rest '(1))))
(rest '(1)) оценивается как empty:
(+ 1 (len len empty))
, а len равно
(λ (len xs) (if (empty? xs) 0
(+ 1 (len len (rest xs))))), поэтому приведенное выше значение расширяется до:
((λ (len ys) (if (empty? ys) 0
(+ 1 (len len (rest ys)))))
(λ (len xs) (if (empty? xs) 0
(+ 1 (len len xs)))) empty)
, а затем empty проталкивается через внешнюю лямбду как ys, и первый условный оператор оценивается:
(empty? ys)
(empty? empty) -> TRUE
Таким образом, вызов (len len empty) возвращает 0.Теперь он переходит к следующему шагу:
(+ 1 0)', which evaluates to 1 , which is the length of the list '(1) `.
Это очень сложная для понимания концепция, и я не думаю, что проделал очень хорошую работу по объяснению этой концепции, поскольку помог вам пройти через все шаги, необходимые для ее идентификации. Если вы поймете, что понимаете, как работает Y-Combinator, я буду достаточно впечатлен - как вашей способностью понимать мои проблемы, так и моей способностью объяснить такую запутанную концепцию.
1. (empty? '(1)) -> FALSE
2. (+ 1 (len len (rest ys)))
((λ (len ys) (if (empty? '(1)) 0
(+ 1 (len len (rest ys)))))
(λ (len xs) (if (empty? xs) 0
(+ 1 (len len (rest xs))))) '(your list here))