64 lines
1.7 KiB
Markdown
64 lines
1.7 KiB
Markdown
# 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))
|
|
```
|