Как отменить список?

Question

Какова функция списка в схеме? Он должен уметь обрабатывать вложенные списки.

Так что если вы сделаете что-то вроде (reverse '(a (b c d) e)), вы получите (e (b c d) a) в качестве вывода.

Как мне подойти к этой проблеме? Я не просто ищу ответ, но что-то, что поможет мне учиться.

Answer 1

(define (my-reverse ls)
  (define (my-reverse-2 ls acc)
    (if (null? ls)
      acc
      (my-reverse-2 (cdr ls) (cons (car ls) acc))))
  (my-reverse-2 ls '()))

При этом используется переменная аккумулятора, чтобы перевернуть список, убрав первый элемент из входящего списка и поместив его в начало аккумулятора. Он скрывает функцию захвата аккумулятора и просто выставляет функцию, которая принимает список, чтобы вызывающему не приходилось передавать пустой список. Вот почему у меня есть мой реверс-2.

(my-reverse-2 '(a (b c d) e) '()); will call
(my-reverse-2 '((b c d) e)  '(a)); which will call
(my-reverse-2 '(e)  '((b c d) a)); which will call
(my-reverse-2 '() '(e (b c d) a)); which will return
'(e (b c d) a)

Поскольку последний вызов функции в my-reverse-2 является вызовом my-reverse-2, и возвращаемое значение передается сразу (возвращаемое значение первого вызова равно возвращаемое значение второго вызова и т. д.) my-reverse-2 * оптимизировано для хвоста *1011*, что означает, что в стеке не останется свободного места. Так что это можно назвать списком так долго, как вам нравится.

Если вы хотите применить его к вложенным спискам, используйте что-то вроде этого:

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc))
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

Это проверяет, является ли элемент списком, прежде чем добавить его в список, и, если это так, сначала переворачивает его. Поскольку он вызывает себя для обращения к внутреннему списку, он может обрабатывать произвольное вложение.

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a) в обратном алфавитном порядке, несмотря на наличие вложенного списка. Оценивается так:

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

Answer 2

(define (reverse1 l)
  (if (null? l)
     nil
     (append (reverse1 (cdr l)) (list (car l)))
  )
)

Пояснение:

Правила:
1. Если список пуст, то обратный список также пуст
2. еще за обратным хвостом списка добавьте первый элемент списка

Посмотрите на этот код так:

reverse1 - имя функции, l - параметр
если список пуст, то реверс тоже пуст иначе вызовите функцию reverse1 с (cdr l), который является хвостом списка, и добавьте его к первому элементу (car l), который вы создаете в виде списка

в вашем примере (псевдо-треска):

1st iteration 
l=>(a (bcd)e)
car l => a
cdr l => (bcd)e
list(car l) =>(a)
------------------
reverse( cdr l)"+"(a)
------------------
2nd iteration
l=>((bcd)e)
car l => (bcd)
cdr l =>e
list(car l)=>(bcd)
--------------------
reverse(cdr l)"+"((bcd))+(a)
-----------------------
3rd iteration
l=>e
car l=> e
cdr l => nil
list (car l) =>(e)
-------------------------
(e (bcd)a)

Answer 3

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

(define (reverse-deep l)
  (map (lambda (x) (if (list? x) (reverse-deep x) x)) (reverse l)))

Объяснение в псевдокоде:
Начните с изменения списка, как обычно
Затем для каждого элемента в обратном списке:
- Если элемент является самим списком: применить процедуру рекурсивно
- Иначе: не трогать элемент

Answer 4

Мое решение:

(define (rvrs ls)
  (if (null? ls)
    empty
    (append (rvrs (cdr ls)) (cons (car ls) empty))))

Answer 5

Это обратная функция в Racket, которая мне нравится намного лучше, чем Scheme.Используется только функция сопоставления с образцом совпадения.

(define/match (rev l)
    [('()) '()]
    [((list a ... b)) (cons b (rev a))])

> (rev '(a (b c d) e))
'(e (b c d) a)

Answer 6

Вы можете просто повернуть элементы в списке, используя foldr:

(foldr (lambda (a r) (append r (list a))) empty lst)

Answer 7

Я использовал код, похожий на вставку sort

(define deep-rev-list
  (lambda (l)
     (cond ((null? l) (quote ()))
           ((atom? (car l))
             (swap-till-end (carl) (deep-rev-list (cdr l))))
           (else
             (swap-till-end (deep-rev-list (car l)) (deep-rev-list (cdr l)))))))


(define swap-till-end
   (lambda (elm lst)
      (cond ((null? lst) (cons elm '()))
            (else
               (cons (car lst) (swap-till-end elm (cdr lst)))))))

(define atom?
  (lambda (x)
    (and (not (null? x)) (not (pair? x)))))

Я воспроизводлю его из памяти.Там могут быть некоторые ошибки.Исправит код, если это так.Но используемая техника похожа на заповеди для вложенных списков, приведенных в Little Schemer :).Я проверил это в DrRacket

(deep-rev-list '((1 2) (3) ((4 5)))) возвращает (((5 4)) (3) (2 1))