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))
```