Существует ли встроенная процедура проверки цикличности списка в схеме (R5RS)? И когда список является циклическим (по определению)? Я пытался найти какую-нибудь процедуру, которая проверяет это и то, как она реализована, но мне не удалось ее найти.
Процедура проверки цикличности списка (схема)
Ответы (2)
Список является круговым по определению, если cdr
хвоста (последний элемент) указывает в начало списка. Однако у вас также может быть круговой список, в котором cdr
хвоста указывает на произвольный элемент в списке. Хорошим алгоритмом для обнаружения кругового списка является алгоритм черепахи и зайца. Пример реализации приведен в этой страница.
Код выглядит следующим образом (автор страницы, ссылка на которую приведена выше):
Изменить: я изменил код, поскольку он содержал ошибку, на которую указал Сильвестр.
(define (has-cycle-h slow-ls fast-ls)
(cond
((null? fast-ls) #f)
((null? (cdr fast-ls)) #f)
((eq? slow-ls fast-ls) #t)
(else (has-cycle-h (cdr slow-ls) (cddr fast-ls)))))
(define (has-cycle? ls)
(cond
((null? ls) #f)
(else (has-cycle-h ls (cdr ls)))))
;; Create cyclic list
(define l (cons 1 (cons 2 (cons 3 (cons 4 '())))))
(set-cdr! (cdr (cdr (cdr l))) l)
;; Results in:
;+---+ +---+ +---+ +---+
;| 1 +--->| 2 +-->| 3 +--->| 4 |
;+-+-+ +---+ +---+ +-+-+
; ^ |
; | |
; +-------------------------+
(has-cycle? l) ; Evaluates to #t
;; Create list
(define l (cons 1 (cons 2 (cons 3 (cons 4 '())))))
;; Make it circular by pointing the tail to the second element.
(set-cdr! (cdr (cdr (cdr l))) (cdr l))
;; Results in:
;+---+ +---+ +---+ +---+
;| 1 +--->| 2 +-->| 3 +--->| 4 |
;+---+ +-+-+ +---+ +-+-+
; ^ |
; | |
; +----------------+
(has-cycle? l) ; Evaluatores to #t
; Regular list
(has-cycle? '(1 1 1 1 1 1 1)) ; Evaluates to #f
Не существует BIF для обнаружения кругового списка.
(eq? (car slow-ls) (car fast-ls))
кажется неправильным. Должно быть (eq? slow-ls fast-ls)
. Попробуйте с '(#f #f #f)
- person Sylwester; 25.03.2015
В SRFI 1 есть предикат circular-list?
. Определение циклического списка в SRFI 1: «Циклический список — это такое значение, что для каждого n>=0 cdr^n(x) является парой». Это означает, что нет конца списка. Первая пара кругового списка не обязательно должна быть частью цикла. Достаточно того, что в конце концов, следуя за cdrs, можно достичь цикла.
SRFI 1 имеет это описание в некруговых списках:
(not (circular-list? x)) = (or (proper-list? x) (dotted-list? x))
SRFI 1 как таковой отсутствует в R5RS, но все известные мне реализации поставляются с включенным srfi 1. Обратите внимание, что если srfi1 реализован в среде выполнения, предикат circular-list?
из srfi 1 может быть быстрее, чем реализация алгоритма черепахи и зайца в Scheme. Сравните выбранную вами реализацию, чтобы узнать, как ведет себя ваша реализация.
http://srfi.schemers.org/srfi-1/srfi-1.html#circular-list-p