floyd-library/document.md

SR 2022-x: Floyd library

Author

Lassi Kortela

Status

Draft

Abstract

Floyd's "tortoise and hare" is a simple, space-efficient algorithm to detect a circular linked list. This is an exploration of how to package Floyd as a convenient abstraction and how to use it to implement well-known list procedures.

Specification

(floyd-generator lists) -> procedure

Return a generator (in the sense of SRFI 158). Successive calls to the generator yield lists of adjacent elements from lists. All lists are traversed in order.

For example, calls to the generator returned by (floyd-generator '((1 2 3) (a b c))) yield (1 a) then (2 b) then (3 c). An exhausted generator returns an end-of-file object.

If no lists are given, the generator is exhausted immediately.

If one or more non-circular lists are given, the generator stops at the end of the shortest. If both circular and non-circular lists are given, the circular lists are cycled until the end of the shortest non-circular list is reached.

The generator is also exhausted if and when it notices that all lists are circular.

It is acceptable for lists to contain the same list more than once.

It is acceptable for any list in lists to be a tail of another list in lists.

It is acceptable for the caller to mutate any list in lists that the generator will not visit again. Once a given list element has been returned by the generator, the cdr of the pair containing that element may be mutated; the generator remembers the old cdr.

Examples

> (generator->list (floyd-generator '((1 2 3 4) (a b c d) (x y z))))
((1 a x)
 (2 b y)
 (3 c z))

> (generator->list (floyd-generator `((1 2 3 4) ,(circular-list 'odd 'even))))
((1 odd)
 (2 even)
 (3 odd)
 (4 even))