[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Traits, dictionaries

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.

On Mon, Oct 20, 2003 at 01:57:04PM -0500, scgmille@xxxxxxxxxxxxxxxxxx wrote:
>> I think the SRFI is only missing two important feature traits:
>>     reversible-collection?      supports collection-reverse-fold
>>     finite-collection?          collection-fold will halt on its own

> I've added the reversible collection attribute to the SRFI and updated 
> at http://sgmiller.org/code/srfi-44.html.  

Great, thanks!

> finite-collection? is arguably the same as (not (collection-size 
> collection)).

Hey, good catch! Except that you got it backwards. Finite-collection? is
usually the same as (collection-size c), except that the latter returns
a useful value.

> Others are permitted to do so if they cannot determine their own size
> efficiently.

I don't think that'll cause problems in practice.

> Circular lists and simliar collections can be created using the
> negative index trick hinted at by the SRFI, but I'm unsure whether
> folds should proceed indefinitely over finite collections.  Other
> thoughts?

I'm a little more worried about these. Consider a circular list with 10
nodes. What should it report as its size, 10 or #f? More specifically,
which value should collection-size report:

1. The number of nodes, or
2. The number of times collection-fold will call its argument?

If the latter, then finite-collection? is effectively identical to
collection-size. If the former, then I still see a need for the

Consider me mostly convinced. Either way, we may not *need* the finite
predicate. However, I would like to see *-size clarified slightly for
cases like the circular list. Specifically, the spec should clearly
state one of the following:

1. Infinite collections should always report #f.
2. Infinite collections should report the "decycled" size, if possible.
3. Either #1 or #2 is OK so long as you document it.
4. It's unspecified, and users should beware.

I personally prefer #1. A circular list might provide its own method for
determining the cycle length (i.e., (clist-cycle-size L)), but it should
report #f for clist-size.

Note: I think the SRFI already requires this, but I'm not certain.

Regarding ! and !!:

> The !/!! distinction is to aid in the readability of code primarily
> .... Imagine this following piece of code occurs in a program:
> (define (add-two collection a b)
>   (bag-add! collection a)
>   (bag-add! collection b))
> If ! is the same as !!, this code may break in a bizarre way if the 
> input collection is changed at some point from a mutable to non-mutable
> collection.


    (define (add-two collection a b)
      (assert mutable-collection? collection)
      (bag-add! collection a)
      (bag-add! collection b))

I think that's the right way to do it. *! and *!! are equivalent for an
otherwise purely-functional program; impure programs can rely on the
mutable shortcut but *only* if they check first. It simplifies the
namespace and does a better job of expressing what the code really

This isn't a deal-breaker for me, but I would like to see the change.

>> 2. The bidirectional-collection? and random-access-collection?
>>    performance traits would be HELPFUL for generic programming.

> I'd prefer that be left to another SRFI.


>> For unordered dictionaries, key-eqv? and val-eqv? both default to
>> eqv?. Ordered dictionaries are similar, except that they can derive
>> key-eqv? from less?, as long as it's a strict weak order (which
>> includes < but not partial orders like <=).

> I almost agree.  I'd prefer the value equivalence function be the
> default, as it fits with the rest of the SRFI that values, not keys,
> are the default visible element of a dictionary when used ignorantly.

Definitely agreed!

>> ... the equivalence function is supposed to "return true if they
>> should be considered equivalent for the purposes of contains?, value
>> insertion, removal, and key lookup."

> I prefer making *-equivalence-function return the value equivalence
> function as above, but change the wording of the above sentence to
> match.

Works for me! Actually, I like this much better than my earlier
suggestion. It's also more "orthogonal" with the fold and fold-keys

> I argue [*-equivalence-function] should return the value comparator,
> *-key-equivalence-function returns the key comparator ...

Yes, definitely.

> and specifying only one equivalence function causes both key and value
> to use said function.

Hm, I'll have to think on this one. At first glance, it sounds OK.
Really, it should be up to the collection, with a recommendation that:

1. Ordered dictionaries derive key-eqv? from the ordering function.
2. Other dictionaries default key-eqv? to value-eqv?.
Bradd W. Szonye