Программирование на LISP - интересно узнать, что делает этот код - PullRequest
Новая
       63

Программирование на LISP - интересно узнать, что делает этот код

0 голосов
/ 18 апреля 2020 
(defun interleave (x y)
  (cond ((and (null x)(null y)) nil)
        (t (cons (car x) (cons (car y) (interleave (cdr x) (cdr y)))))

Хотите знать, что делает приведенный выше код?

1 Ответ

5 голосов
/ 18 апреля 2020

Определяет функцию, которая чередует два списка. Например, вызов его следующим образом: 

(interleave '(a b c) '(d e f))

даст список (a d b e c f).

Редактировать

Вот объяснение:

  • (defun interleave (x y) .. объявляет функцию interleave, которая принимает 2 аргумента (или списки)
  • (cond ((and (null x)(null y) nil) ...) сообщает, что если оба x и y являются nil, возвращаются nil. nil - пустой список, а функция null проверяет, является ли список пустым или нет. Здесь условие действует как завершение для рекурсивного вызова функции interleave.
  • (t ...) указывает действие по умолчанию, если указанное выше условие не выполняется
  • (cons ...) создает новый список, указав заголовок (первый аргумент) и хвост (второй аргумент) списка. Например: (cons a '(b c)) даст (a b c). Обратите внимание, что заголовок должен быть одним элементом, а хвост - списком элементов. Вот одно полезное свойство cons: (cons a nil) => (a).
  • (car x) извлекает заголовок списка x. Например: (car '(a b c)) вернет a. Вот одно полезное свойство car: (car nil) => nil.
  • (cdr x) извлечение хвоста списка x. Например: (cdr '(a b c)) вернет (b c). Полезные свойства ie из cdr здесь:
    • хвост списка одного элемента равен nil: (cdr (a)) => nil
    • хвост nil равен nil: (cdr nil) => nil.
  • (interleave (cdr x) (cdr y)) рекурсивно вызывает функцию interleave с tail обоих x и y в качестве аргументов.

Итак, для вызова (interleave '(a b c) '(d e f)) рекурсия может быть представлена ​​следующим образом: 

(interleave '(a b c) '(d e f))
(cons a (cons d (interleave (b c) (e f)))
(cons a (cons d (cons b (cons e (interleave (c) (f))))))
(cons a (cons d (cons b (cons e (cons c (cons f (interleave nil nil)))))))
(cons a (cons d (cons b (cons e (cons c (cons f nil))))))
(cons a (cons d (cons b (cons e (cons c (f))))))
(cons a (cons d (cons b (cons e (c f)))))
(cons a (cons d (cons b (e c f))))
(cons a (cons d (b e c f)))
(cons a (d b e c f))
(a d b e c f)

Для случая, когда длина двух списков не равна, мы имеем, например: 

(interleave '(a b c) '(1 0))
(cons a (cons 1 (interleave (b c) (0))))
(cons a (cons 1 (cons b (cons 0 interleave (c) nil))))
(cons a (cons 1 (cons b (cons 0 (cons c (cons nil (interleave nil nil)))))))
(cons a (cons 1 (cons b (cons 0 (cons c (cons nil nil))))))
(cons a (cons 1 (cons b (cons 0 (cons c (nil))))))
(cons a (cons 1 (cons b (cons 0 (c nil)))))
(cons a (cons 1 (cons b (0 c nil))))
(cons a (cons 1 (b 0 c nil)))
(cons a (1 b 0 c nil))
(a 1 b 0 c nil)
...