Digrasp
Previously
I said that dotted graphs seem to be second class objects and John asked me to elaborate.
How are dotted graphs second class?
A number of combiners in the spec accept cyclic but not dotted lists. These are:
- All the type predicates
- map and for-each
- list-neighbors
- append and append!
- filter
- reduce
- "Constructably circular" combiners like $sequence
So they accept any undotted graph, but not general dotted graphs. This occurs often enough that to make dotted graphs seem second-class.
Could it be otherwise?
The "no way" cases
For some combiners I think there is no sane alternative, like `pair?' and the appends.
The "too painful" cases
For others, like filter or list-neighbors, the dotted end could have been treated like an item, but it seems klugey and irregular, and they can't do anything sane with a "unary dotted list", ie a non-list.
$sequence etc seem to belong here.
map and for-each
For map and for-each, dotted lists at the top level have the same problem as above, but ISTM "secondary" dotted lists and lists of varying length could work.
Those could be accomodated by passing another combiner argument
(proc2) that, when any list runs out, is given the remaining tails
isomorphically to Args, and its return is used as the tail of the
return list. In other words, map over a "rectangle" of list-of-list
and let proc2 work on the irregular overrun.
The existing behavior could be recaptured by passing a proc2 that, if it gets all nils, returns nil, and otherwise raises error. Other useful behaviors seem possible, such as continuing with default arguments or governing the length of the result by the shortest list.
Reduce
Reduce puzzles me. A cyclic list's cycle after it is collapsed to a single item resembles a dotted tail, and is legal. Does that imply that a dotted list should be able to shortcut to that stage?
Thank you for elaborating.
ReplyDeleteOn the face of it, I don't agree; I'll partly qualify that in a moment. I understand you to be speaking of what the Kernel Report calls improper lists. Any data type has operations that are specific to that data type, and cannot be performed on things that don't belong to that data type; this does not compromise the first-class status of objects that don't belong to that type. Just because you can't do arithmetic on non-numbers, that doesn't prevent non-numbers from being first-class objects. Just because a list operation cannot be performed on non-lists, that doesn't make non-lists less than first-class.
My qualification is that, especially under the DIGRASP banner, you're clearly looking at operations on digraphs. I would think one would want a different toolkit of simple operations for manipulating digraphs, and I doubt (subject to being convinced otherwise) it would make sense to try to overload the list operations for that purpose.
OK, thank you. I agree with much that you said. If you would rather that the lesser position of dotted graphs be called something other than "second-class", I'm certainly willing to.
DeleteOne difference between numbers and graphs is that "numberness" is shallow. If I had a number, then unless I make a shallow change ($set! or similar), I always have a number. "Dottedness" is deep. Whether I constructed a dotted or undotted graph can depend on non-local code. And then it can change without obvious operations on the root pair.
True, numbers are atoms, while lists are data structures (in the sense of Kernel Report section 3.9). Speaking of which,
DeleteI'm not clear how you have in mind to represent digraphs using pairs. A list is naturally understood as a directed path (which may be cyclic or acyclic). Then there is a tree; in its most general sense, a start object together with all other objects that can be reached from it by following only the car and cdr links of pairs. How, then, would one prefer to represent a digraph?
"I'm not clear how you have in mind to represent digraphs using
Deletepairs."
It's not surprising that it's unclear, since I'm deliberately leaving it open which of several possible approaches is "right". I'll spell out the possibilities that I see in the next post.