On 2020-08-30 23:15 +0200, Marc Nieper-Wißkirchen wrote:
> Am So., 30. Aug. 2020 um 23:08 Uhr schrieb Wolfgang Corcoran-Mathe
> <xxxxxx@sigwinch.xyz>:
> >
> > Additional note: The O(n) space complexity of the "vectorizing"
> > range-map is actually its worst aspect, I think.  This violates the
> > compact nature of ranges, as the entire range must be realized as a
> > vector which is then enclosed in a new range:
> >
> >     (range-map square (numeric-range 0 10000))
> >
> >     ==
> >
> >     (vector->range (vector-map square #(0 ... 9999)))
> >
> > So we can no longer rely on the crucial principle stated near the
> > beginning of SRFI 196: "The size of a range object is independent of
> > the number of elements it contains".
>
> The sentence "The size of a range object is independent of the number
> of elements it contains" has not really a formal meaning (and should
> thus be moved from the specification section into the informal
> rationale). You can always hide whatever space and time complexity in
> the indexer procedure.

Right, agreed.

> Of course, for your example with (range-map square (numeric-range 0
> 10000)), it is hurting but just shows that range-map is not the right
> tool for *this* particular use case. For that we would want to use
>
> (progression-map square (numeric-progression 0 10000))

That makes sense, although it's likely that range-map may seem similar
use.  Unless someone can think of a more space-efficient way to
implement it, though, a warning should probably be included to the
effect that the result of range-map may require "realizing" the entire
range. (i.e. that it may require space linear in the number of elements)

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"The most important computer is the one that rages in our skulls
and ever seeks that satisfactory external emulator." --Alan J. Perlis