[m-rev.] for review: folding over a range of dates

[Julien Fischer]

Hi Peter,

On Wed, Jan 30, 2013 at 10:52 AM, Peter Moulder
<peter.moulder at monash.edu> wrote:
> On Tue, Jan 29, 2013 at 11:33:12AM +1100, Julien Fischer wrote:
>
>> library/calendar.m:
>>    Add the new predicates: [foldl_days/5], foldl2_days/7 and
>>    foldl3_days/9.
>
> The corresponding int folding preds are called fold_up, fold_up2 etc.
> (with fold_down for descending);
> the corresponding set and hash_table folding preds are just called fold;

I see fold as being reserved for situations where either no ordering
on the traversal is required or no order on the traversal is efficiently
possible.

In the case of sets, recent versions of the set module already have
foldl as a synonym for fold.  In a sense the operation really is foldl
anyway, since the traversal of the set is done from the least to
the greatest element (using normal Mercury term comparison).

In the case of hash tables, I don't think you can efficiently define
a traversal based on key order -- you would have to extract all
the keys, sort them and then look up the items again.  Ugh!
For hash tables, I think fold is the right name for the operation.

> whereas map, bimap and *_bitset are foldl;
> dir is foldl even though the order is explicitly unspecified.

Implementation-dependant rather than unspecified, the order depends
on the order in which the OS gives you the directory entries.

> There's less consistency here than one might like,
> but dates do seem closest to the int case in my thinking.
> foldl meaning ascending dates makes sense for our calendars,
> but might seem backwards when thinking of an Arabic calendar.
> I've no strong objection to the existing names, though.

It's a fair point, although I find the names fold_up_days etc
a bit awkward looking.   Given you are folding over a range
of dates, foldl (and foldr) make sense to me.  (And do so,
for ranges of ints as well.)

I was briefly tempted by fold_future and fold_past, but on reflection
perhaps not ;-)

> Incidentally, bimap.m foldl preds don't mention what order is used.

In-order traversal of the forward map.

> It would be good to add at least a short phrase like "in key order"
> (if that is indeed the order used).

Agreed, I'll add something along those lines.

> map.m uses the word "inorder" in some cases, but foldl_values should probably
> say "in key order", as should at least one of {map_foldl, map_values_foldl}.
>
> Anyone care to add these short phrases to the docs?

Shall do.

Cheers,
Julien.
_______________________________________________
reviews mailing list
reviews at lists.mercurylang.org
http://lists.mercurylang.org/listinfo/reviews