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

Re: Traits, dictionaries



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
predicate.

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.

Solution:

    (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
means.

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.

OK.

>> 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
procedures.

> 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
http://www.szonye.com/bradd