Lazy caching map()?

[H. S. Teoh]

On Fri, Mar 09, 2018 at 12:47:14PM -0700, Jonathan M Davis via Digitalmars-d wrote:
> On Friday, March 09, 2018 11:41:46 H. S. Teoh via Digitalmars-d wrote:
> > [...]  More precisely, given an array `T[] src` of source data and a
> > function func(T) that's pretty expensive to compute, return an
> > object `result` such that:
> >
> > - result[i] == func(src[i]), for 0 ≤ i < src.length.
> >
> > - If result[j] is never actually used, func(src[j]) is never invoked
> >   (lazy).
> >
> > - If result[j] is referenced multiple times, a cached value is returned
> >   after the first time, i.e., the result of func(src[j]) is cached, and
> >   func(src[j]) is never invoked more than once.
[...]
> > Can this be done using current Phobos primitives?
> 
> Wasn't that what std.algorithm.iteration.cache was supposed to solve?
> I've never used it, so I don't know how well it fits what you need,
> but IIRC, using it with map was basically the use that it was invented
> for.
[...]

The problem with cache() is that it does not return a random-access
range, and for my use case random-access is mandatory, because I cannot
predict ahead of time which indices will be used.  Worse yet, cache()
eagerly evaluates .front and .back, which is a no-no in my case (it
should not compute elements that are not asked for).

These two limitations defeats the entire purpose, since no RA means I
have to iterate to find the elements I want, and eager evaluation means
func() will be computed as I iterate, even if I never call .front. So
basically the entire result array will be computed.

It's also not trivial to extend cache() to handle random access, because
that means it has to allocate in order to store cached elements, whereas
the current implementation statically allocates space in the returned
range to store cached .front and .back elements.


T

-- 
An imaginary friend squared is a real enemy.