floyd-library/document.md

64 lines
1.7 KiB
Markdown
Raw Permalink Normal View History

2022-12-07 09:12:29 -05:00
# 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
```
2022-12-07 09:27:35 -05:00
> (generator->list (floyd-generator '((1 2 3 4) (a b c d) (x y z))))
2022-12-07 09:12:29 -05:00
((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))
```