replaceFirst, findPieces, and takeExactly

[Andrei Alexandrescu]

On 1/22/11 10:57 PM, spir wrote:
> On 01/23/2011 05:30 AM, Andrei Alexandrescu wrote:
>> On 01/22/2011 10:16 PM, spir wrote:
>>> On 01/22/2011 10:27 PM, Andrei Alexandrescu wrote:
>>>> The first abstraction is the takeExactly() function:
>>>>
>>>> http://d-programming-language.org/cutting-edge/phobos/std_range.html#takeExactly
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> That function allows you to pick a determined number of elements from a
>>>> range, assuming the range is never shorter than that. That sounds a bit
>>>> obscure, but plays a pivotal role in findParts() (which is the name I
>>>> settled on for the equivalent of Python's partition()):
>>>
>>> What is reasoning behind having length set on takeExactly's result
>>> (while if succeeds, you know it, or don't you?), and not on take's
>>> result (which can return a smaller number of elements)? I would expect
>>> the opposite, or both, but maybe it's only me?
>>>
>>> Denis
>>
>> If the ranges involved are forward ranges, not passing around length
>> information essentially throws away information painstakingly acquired
>> (by
>> means of O(n)).
>
> Agreed. But why not on take? (Did not check the code, but) the doc says
> for it:
> "If the range offers random access and length, Take offers them as well."
> Length information is much more valuable info for take, as it may return
> less elements than specified. Or what do I miss? Why not (mixed with
> takeExactly's doc):
> "The result of take(range, n) always defines the length property (and
> initializea it to actual number of elements) even when range itself does
> not define length. If the range offers random access, Take offers them
> as well."
> ?

take(r, n) takes at most n elements from r. It is unable to offer length 
because for an input or forward range that would cost O(n). (For an 
input range, that would also ruin the range.)

takeExactly(r, n) assumes that the range has at least n elements. As 
such, it is able to offer constant-time length.

These are quite different abstractions with different capabilities and 
power. I have been missing for years a complete solution to findPieces() 
because I've always wanted to express its results in terms of take() 
instead of takeExactly(). Only today I figured the puzzle out.


Andrei