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

```> > 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.
Of course.

> > 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?

The latter.  size indicates the number of values stored in the
collection, which is equivalent to the number of times collection-fold
will call its argument for a finite collection.

>
> 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.
Thats still a finite collection, but whose representation contains a
cycle.

What I need to do is make it clear that an infinite collection is one
which contains a potentially infinite number of values, while a finite
collection contains a non-infinite number, regardless of cycles.  A
circular list with five elements may have an infinite naive walk, but it
still contains a finite number (5) of values.

> 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.
I prefer #2, as it fits the current wording and is "The Right Thing" in
my opinion.  Circular lists are used to have O(1) access to the head and
tail of the list, but they are rarely used to simulate an infinite
number of values.

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

Nor for me, so I'd like to hear a second rationalization for removing
it.  Matthias?

> > 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.
>
> Re: equivalence
> 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?.

Sounds good.

I'll go ahead and make the wording clarifications regarding infinite
collections and add the equivalence function changes.

Scott
```

Attachment: pgp4jGXYr92WK.pgp
Description: PGP signature