Рекурсивное добавление в список с использованием схемы

Question

Я новичок в функциональном программировании и относительно новый в программировании в целом.Так что я довольно растерялся, пытаясь понять синтаксис Схемы.Но это довольно простой вопрос.Я пытаюсь создать функцию, которая рекурсивно заполняет и печатает список из чисел от х до у.Между рекурсией и тем, что это новый язык для меня, я застрял.

 (define (gen-list x y)

  (if (> start end)

      '()

      (append '() (gen-list ((+ 1 x) y)) ) ))

Если бы я вошел (gen-list 1 5), я бы ожидал, что результат будет 1 2 3 45. Это в настоящее время дает мне ошибку «приложение: не процедура», когда он пытается вызвать себя снова.Я обошел ошибку, но не смог напечатать что-нибудь удаленно, как мне бы хотелось.Любая помощь приветствуется.

Answer 1

У вас есть пара ошибок:

• Параметры называются x и y, но вы называете их start и end (я бы предложилвместо этого используйте start и end, они упрощают понимание кода.)
• В последней строке у вас больше скобок, чем необходимо.Это очень важный и бесконечный источник путаницы для начинающих.Не окружайте все выражения () , если только вы не хотите вызывать процедуру.
• Мы рекурсивно строим новые списки с помощью cons, append для объединения существующих списков.
• На самом деле вы не используете start, который является текущим элементом в рекурсии, для создания нового списка - вы просто append используете пустые списки.
• Список - это элемент cons, преобразованный в другой список, или пустой список '().Вот почему мы возвращаем '() в базовом случае.Например, вот как выглядит двухэлементный список: (cons 1 (cons 2 '())).

После всего сказанного и выполненного, это правильный способ построения нашего списка:

(define (gen-list start end)
  (if (> start end)
      '()
      (cons start
            (gen-list (+ start 1) end))))

В заключение: указанная выше процедура уже существует в Racket, вам не нужно ее переписывать.Читайте о range в документации .

Answer 2

Просто добавление рекурсивной версии хвостового вызова

(define (gen-list start end (acc '()) #:step (step 1))
  (cond ((> start end) (reverse acc))
        (else (gen-list (+ start step) end (cons start acc)))))

Лично я люблю cond, потому что у вас есть все условия, а затем ниже друг друга (или else) - это стиль The little Schemerочень хорошая книга для изучения рекурсивного мышления.

Answer 3

Одна из проблем с «очевидным» ответом на этот вопрос заключается в том, что он не очень хорошо работает.Подумайте об этом:

(define (gen-list start end)
  (if (> start end)
      '()
      (cons start
            (gen-list (+ start 1) end))))

Что ж, если start намного меньше, чем end, в стеке будет огромное количество рекурсивных вызовов, потому что это правильно рекурсивная функция: рекурсивнаявызов gen-list является реальным вызовом и должен быть возвращен до того, как может произойти вызов cons (который является хвостовым вызовом).

Чтобы справиться с этим, нужно повернуть шаблоны, которые выглядят как (cons x (<recursive-call> ...)) в паттерны, которые выглядят как (<tail-call> ... (cons x ...)): вам нужна функция с дополнительным аргументом, аккумулятор .Это означает, что вызовы, которые ранее были рекурсивными, теперь являются хвостовыми вызовами, и поэтому все хорошо: процесс теперь итеративный.

Проблема в том, что списки выходят задом наперед (вам нужно подумать, почему это так., но это очевидно после недолгих раздумий).Таким образом, вам нужно полностью изменить результат.К счастью, изменение списка также является итеративным процессом, и это нормально.

Но в этом случае, ну, вы можете просто считать в обратном направлении!Таким образом, простой подход выглядит следующим образом, используя локально определенную вспомогательную функцию (это можно определить как функцию верхнего уровня, но зачем?):

(define (gen-list low high)
  (define (gla i result)
    (if (< i low)
        result
        (gla (- i 1) (cons i result))))
  (gla high '()))

Вы видите, что это подсчетв обратном направлении: начальный вызов gla начинается с high и затем создает список в обратном направлении.Итак, теперь:

> (gen-list 1 3)
'(1 2 3)

Как мы хотим.

Это такой общий шаблон в Scheme, что для него существует специальная конструкция: named let.Таким образом, мы можем перефразировать вышеупомянутое более идиоматическим образом:

(define (gen-list low high)
  (let gla ([i high] [result '()])
    (if (< i low)
        result
        (gla (- i 1) (cons i result)))))

Это в точности то же самое, что и предыдущий ответ: он просто перемещает начальный вызов наверх и объединяет его с локальным определением gla.Вероятно, это идиоматический способ Схемы сделать что-то подобное (хотя люди, которые пишут больше Схем, чем я, могут отличаться: я действительно человек CL и у меня неизбежно плохой вкус).

---

Вот гдеистория должна закончиться, но я не могу удержаться, добавив следующее.В старые добрые времена comp.lang.lisp люди обычно задавали очевидные домашние вопросы, и, поскольку не было системы кармы, один из подходов заключался в том, чтобы дать ответ, который решил проблему ... будучи абсурдно непрозрачным.

Итак, прежде всего мы можем превратить gla в функцию, которая передается через продолжение вызова, а не зная, что она должна вызывать сама себя:

(define (gen-list low high)
  (let ([gla (λ (cont i result)
               (if (< i low)
                   result
                   (cont cont (- i 1) (cons i result))))])
    (gla gla high '())))

И затем, конечно, мы можем превратить (let ([x y]) ...) в((λ (x) ...) y):

(define (gen-list low high)
  ((λ (gla)
     (gla gla high '()))
   (λ (cont i result)
     (if (< i low)
         result
         (cont cont (- i 1) (cons i result))))))

И это хороший, чистый ответ ... который ни один студент не придумает.

Альтернативный подход, который является еще более злым, заключается просто в явномконечно, используйте комбинатор Y.

Answer 4

Вам нужно больше, чем просто (> конец конца) базовый случай, вам также нужен (= конец конца) базовый случай, в котором вы возвращаете (начало списка)