Перевернуть список в схеме

Я пытаюсь изменить список в схеме, и я пришел к следующему решению:

(define l (list 1 2 3 4))

(define (reverse lista)
    (car (cons (reverse (cdr (cons 0 lista))) 0)))

(display (reverse l))

Хотя это работает, я действительно не понимаю, почему это работает.

В моей голове это будет оцениваться как серия вложенных минусов до минусов () (который является cdr списка с одним элементом).

Думаю, я не понимаю модель замещения, может кто-нибудь объяснить мне, почему она работает?

Наблюдения:

  • Предполагается работать только в невложенных списках.

  • Взято из SICP, упражнение 2.18.

  • Я знаю, что есть много подобных вопросов, но, насколько я видел, ни один из них не представил это решение.

Спасибо


recursion reverse scheme sicp mit-scheme
person Eduardo Hashimoto    schedule 13.07.2016    source источник
comment
вы уверены? код, который вы показываете, явно не работает, и по уважительной причине - (cdr (cons 0 lista)) оценивается как lista, поэтому он бесконечно зацикливается. рекурсивное определение должно иметь базовый вариант, проверяя его на каждом шаге. в вашей процедуре его нет, он всегда повторяется. единственный способ, которым я вижу, что эта вещь может работать, - это вместо этого вызывать встроенный реверс, так что, может быть, у вас была опечатка при ее определении?   -  person dercz    schedule 13.07.2016
comment
Спасибо, не знал про встроенный реверс. Я использую его вместо определенной процедуры, когда я меняю имя, это действительно не работает. Извините за этот вопрос.   -  person Eduardo Hashimoto    schedule 13.07.2016
comment
Без проблем! Все, кого я знаю при изучении lisp, совершали подобные ошибки (включая меня). Я все же решил написать ответ. Удачи и удачного взлома, надеюсь, вам понравится интриговать!   -  person dercz    schedule 13.07.2016

Ответы (3)


arrow_upward
1
arrow_downward

[Поскольку это происходит довольно часто, я все равно пишу ответ]

Реализации схемы имеют свои встроенные версии реверса, сопоставления, добавления и т. д., как они указаны в RxRS (например, https://www.cs.indiana.edu/scheme-repository/R4RS/r4rs_8.html).

В процессе изучения схемы (да и вообще любого диалекта lisp) в любом случае очень полезно их реализовать. Опасность в том, что одно определение может столкнуться со встроенным (хотя, например, определение схемы или метка lisp должны их затенять). Поэтому всегда стоит называть эту самодельную реализацию каким-то другим именем, например, "my-reverse", "my-append" и т. д. Таким образом вы избавите себя от путаницы, как в следующем:

(let ([append
        (lambda (xs ys)
          (if (null? xs)
              ys
              (cons (car xs) (append (cdr xs) ys))))])
 (append '(hello) '(there!)))

-- это похоже работает, создавая ложное впечатление, что "let" работает так же, как "letrec". Но просто измените имя на «my-append», и оно сломается, потому что в момент вычисления лямбда-формы символ «my-append» еще ни к чему не привязан (в отличие от «append», который был определен как встроенная процедура ).

Конечно, такая форма let будет работать в языке с динамической областью видимости, но схема лексическая (за исключением «define»), и причина в ссылочной прозрачности (но это настолько далеко от темы, что я могу отослать заинтересованного читателя только к одному лямбда-документов http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf).

person dercz    schedule 13.07.2016

arrow_upward
1
arrow_downward

Это читается почти так же, как решения на других языках:

  • если список пуст, вернуть пустой список. Иначе ...
  • отрубить первый элемент (CAR)
  • инвертировать остаток списка (CDR)
  • добавить (CONS) первый элемент к этому развороту
  • вернуть результат

Теперь ... учитывая мое понимание со времен LISP, код будет выглядеть примерно так:

(append (reverse (cdr lista)) (list (car lista)))

... что соответствует моему описанию выше.

person Prune    schedule 13.07.2016
comment
CAR = взять головной элемент; CDR = взять остальную часть списка; ПРОТИВ = добавить; 0 = НОЛЬ. - person Prune; 13.07.2016
comment
Спасибо. Я это понимаю, но как насчет (define (reverse l) (cons (reverse (cdr l)) 0)). Там нет машины, и он по-прежнему возвращает обратный список (за вычетом первого элемента). Если бы вместо 0 у меня была (автомобиль l), то, согласно вашим словам, все было бы в порядке. Но я не представляю, как это происходит без машины. - person Eduardo Hashimoto; 13.07.2016
comment
По правде говоря, я не совсем понимаю, как работает ваш код; Я говорю на LISP, а не на Scheme. Насколько я знаю, cons (0 x) возвращает просто x, поэтому мое чтение говорит, что это приведет к бесконечной рекурсии. - person Prune; 13.07.2016
comment
Извините, мой код вообще не работает. Я использовал встроенный реверс и запутался в результатах. Теперь это решено. Спасибо и извините. - person Eduardo Hashimoto; 13.07.2016
comment
@Prune это неверно, cons создает пару (поэтому предполагается, что x равно, например, 42, (cons 0 x) оценивается как (0 . 42), а не само 42), и то, что вы хотите в случае вашего фрагмента кода, это добавить, который объединяет список, поэтому (добавить (обратный (список cdr)) (список (список автомобилей))). Также будьте осторожны с обозначениями: открывающая скобка идет перед операндом, а не после. - person dercz; 13.07.2016
comment
@dercz Спасибо; исправил код. Теперь, если вы хотите опубликовать правильный ответ и включить мой ответ, который вы хотели бы использовать, мы можем отдать должное вам и удалить этот ответ. - person Prune; 13.07.2016
comment
@Prune Думаю, моего ответа достаточно (вопрос был в том, почему это работает). И ваш ответ - очень хороший совет для тех, кто пытается реализовать обратную рекурсию без хвостовой рекурсии. Я бы оставил все как есть... - person dercz; 13.07.2016
comment
А... Я не обновлял страницу, видимо, и похоже, что мой ответ был единственным. Да, пусть они оба стоят. - person Prune; 13.07.2016

arrow_upward
0
arrow_downward

Есть несколько способов сделать это. Вот еще:

(define my-reverse
  (lambda (lst)
    (define helper
      (lambda (lst result)
        (if (null? lst)
            result
            (helper (cdr lst) (cons (car lst) result)))))
    (helper lst '())))
person Michael Vehrs    schedule 14.07.2016