On Friday, 20 September 2013 at 09:43:10 UTC, bearophile wrote:
[cut]
>Another thing to notice is that Haskell user defined operators
> sometimes hurt my ability to read code. This is composed with the precedent problem.

++
I remember that reading a tutorial about Elm felt much more easy to read than other text based on Haskell because Elm's author took great care of choosing readable operators..

That said, he made the same mistake as Haskell's authors: currying is a *mathematical detail* which shouldn't obscure function type:
'f: a->b->c' is less readable than 'f: a,b->c'.

renoX

On Friday, 20 September 2013 at 13:00:49 UTC, H. S. Teoh wrote:
> On Fri, Sep 20, 2013 at 09:14:28AM +0200, PauloPinto wrote:
>> On Thursday, 19 September 2013 at 23:50:04 UTC, H. S. Teoh wrote:
> but at least in C, mistakes
> tend to be noticed rather quickly, whereas in C++ you could be coding
> for months, years, before you even notice anything wrong. And by then,
> it's too late to fix it because half the codebase is already written in
> the "wrong" way.

I think that, even more than the hidden code execution (constructors, operators) and unpredictable code paths (exceptions), this is the strongest argument among those Linus made in its rant against C++.

On Fri, Sep 20, 2013 at 05:36:59PM +0400, Dmitry Olshansky wrote:
> 20-Sep-2013 14:55, Szymon Gatner пишет:
> >On Friday, 20 September 2013 at 10:47:52 UTC, Dmitry Olshansky wrote:
> >>20-Sep-2013 14:00, Jacob Carlborg пишет:
> >>>On 2013-09-20 11:37, Szymon Gatner wrote:
> >>>
> >>>>If only std algorithms took containers (by that I mean things that
> >>>>container for accepts too) as arguments (and not iterators)...
> >>>>even in the form of new functions like foreach_all, transform_all
> >>>>etc.
> >>>
> >>>Can't a container be a range as well?

A container should not be confused with a range. That way leads to dragons. :-P  (It's rather unfortunate that built-in arrays conflate the two, it leads to a lot of wrong code that works only with arrays but not with "real" ranges.)


> >>For Christ sake no, no and no. For starters range skips/drops elements when iterating, and thusly iteration has its own state that is useless for a container otherwise.
> >
> >That would be a filtering range which adds additional logic that costs exactly the same as an if() statement inside a for loop when filtering on condition manually.
> >
> Filtering is just an adapter.
> Better examples are traversing e.g. binary-tree depth-first
> in-order, or post-order and that would require state.
> Again it's easy to miss by looking at built-in arrays.

Traversing the tree at all requires state, whether or not you do it with ranges. You either put the state on the runtime stack (recursion), or you put the state on the heap in the range adaptor. Same thing.


> >>TL;DR: Suboptimal, unnatural and error prone are keywords.
> >
> >Why would it be suboptimal?
> 
> If said tree needs to be a range I would be horrified to see how it manges to be at the same time a range that (for the sake of example) traverses said tree depth-first in-order.
> 
> Not even talking about trees having no one "natural" range over them.
[...]

Some trees do, like document trees. But yeah, in general, you don't have a natural ordering to trees.

But then again, the whole point of ranges is *linear* traversal. If you're not doing that, then it's probably the wrong abstraction to use. (FWIW, while SortedRange is a neat hack, I haven't actually found it that useful in practice. Most of the ranges I actually use are for the cases where it's an input/forward range and you don't want to store the whole thing, so random access is impractical. The cases where I actually have random access usually turn out to be plain ole arrays anyway, so the SortedRange abstraction isn't really necessary.)

So for trees, I'd argue that you need a tree-specific iteration abstraction, not ranges, which are linear. It's a clear case of structure conflict. ;-)


T

-- 
Real Programmers use "cat > a.out".

On Friday, 20 September 2013 at 14:49:21 UTC, H. S. Teoh wrote:

snip
> [...]
>
> Some trees do, like document trees. But yeah, in general, you don't have
> a natural ordering to trees.
>
> But then again, the whole point of ranges is *linear* traversal. If
> you're not doing that, then it's probably the wrong abstraction to use.
> (FWIW, while SortedRange is a neat hack, I haven't actually found it
> that useful in practice. Most of the ranges I actually use are for the
> cases where it's an input/forward range and you don't want to store the
> whole thing, so random access is impractical. The cases where I actually
> have random access usually turn out to be plain ole arrays anyway, so
> the SortedRange abstraction isn't really necessary.)
>
> So for trees, I'd argue that you need a tree-specific iteration
> abstraction, not ranges, which are linear. It's a clear case of
> structure conflict. ;-)
>
>
> T

Excuse my lack of knowledge on Ranges, so maybe what I am proposing is infeasible, for a binary tree for example couldn't you have a InOrderRange, PreOrderRange, and PostOrderRange or alternately DepthFirstRange, and BreadFirstRange.  From a consumers view those would be linear operations?

Craig

On Friday, 20 September 2013 at 14:55:41 UTC, Craig Dillabaugh wrote:
clip
>
> Excuse my lack of knowledge on Ranges, so maybe what I am proposing is infeasible, for a binary tree for example couldn't you have a InOrderRange, PreOrderRange, and PostOrderRange or alternately DepthFirstRange, and BreadFirstRange.  From a consumers view those would be linear operations?
>
> Craig

Please also excuse my lack of proper punctuation :o)

20-Sep-2013 18:13, Szymon Gatner пишет:
> On Friday, 20 September 2013 at 14:04:06 UTC, Dmitry Olshansky wrote:

>> >> Can't a container be a range as well?
>> >>
>>
>> >For Christ sake no, no and no.
>>
>> [... Because that would be ...]
>>
>> > TL;DR: Suboptimal, unnatural and error prone are keywords.
>>
>> Then your question - Why would it be suboptimal?
>>
>> Which your second reply seem to clearly explain: extra state placed
>> where it doesn't belong. I can't easily correlate your two answers as
>> they look as if the second one answers questions of the first.
>> Anyhow we are in agreement here.
>
> Mind that "Can't a container be a range as well?" was not from me.

Yup, but it was what I was answering ... when you asked about why would it be suboptimal... A container that is a range at the same time is suboptimal, that's all.

> Still, moving computation over a range from for loop body into the range
> implementation (like filtering) incurs no performance penalty and has
> additional benefits of composability and maintainability. Do you mean
> that is suboptimal?

I made no statement on this I think. It shouldn't be ineffective.
The only problem with it that I foresee is that in order to take advantage of vectorized SIMD in CPU it could be harder to auto-magically vectorize such code for compiler.

For that matter I think e.g. providing explicitly a range of float4 fells like a better way to go.


-- 
Dmitry Olshansky

On 20/09/13 16:48, H. S. Teoh wrote:
> A container should not be confused with a range. That way leads to
> dragons. :-P  (It's rather unfortunate that built-in arrays conflate the
> two, it leads to a lot of wrong code that works only with arrays but not
> with "real" ranges.)

Built-in arrays are not _always_ ranges.  Consider const(int[]) ... as I found out recently, it's _not_ a range, because you can't popFront on a const entity.

On Fri, Sep 20, 2013 at 04:55:40PM +0200, Craig Dillabaugh wrote:
> On Friday, 20 September 2013 at 14:49:21 UTC, H. S. Teoh wrote:
> 
> snip
> >[...]
> >
> >Some trees do, like document trees. But yeah, in general, you don't have a natural ordering to trees.
> >
> >But then again, the whole point of ranges is *linear* traversal.  If you're not doing that, then it's probably the wrong abstraction to use.  (FWIW, while SortedRange is a neat hack, I haven't actually found it that useful in practice. Most of the ranges I actually use are for the cases where it's an input/forward range and you don't want to store the whole thing, so random access is impractical. The cases where I actually have random access usually turn out to be plain ole arrays anyway, so the SortedRange abstraction isn't really necessary.)
> >
> >So for trees, I'd argue that you need a tree-specific iteration abstraction, not ranges, which are linear. It's a clear case of structure conflict. ;-)
> >
> >
> >T
> 
> Excuse my lack of knowledge on Ranges, so maybe what I am proposing is infeasible, for a binary tree for example couldn't you have a InOrderRange, PreOrderRange, and PostOrderRange or alternately DepthFirstRange, and BreadFirstRange.  From a consumers view those would be linear operations?
[...]

Well, of course you can have these ranges. But they have to be separate from the container. And they won't be able to take advantage of the tree structure, for example, prune the children of the current node from the iteration. To do that with a range you'd have to skip over all the descendent nodes manually, which is tedious and also a waste of time.

Incidentally, I did recently write a PreorderRange API for my own code, which provides an additional method called pruneFront() that efficiently skips over descendent nodes. In retrospect, though, I'm questioning the value of doing this, since that makes assumptions about the range that require too much knowledge about the underlying container, which makes the abstraction nothing more than mere formality. I might as well come out and say "this is a tree" and work with a full-fledged tree abstraction rather than try to shoehorn it into a linear range API.


T

-- 
Why is it that all of the instruments seeking intelligent life in the universe are pointed away from Earth? -- Michael Beibl

20-Sep-2013 18:48, H. S. Teoh пишет:
> On Fri, Sep 20, 2013 at 05:36:59PM +0400, Dmitry Olshansky wrote:
>> 20-Sep-2013 14:55, Szymon Gatner пишет:
>>> On Friday, 20 September 2013 at 10:47:52 UTC, Dmitry Olshansky wrote:
>>>> 20-Sep-2013 14:00, Jacob Carlborg пишет:
>>>>> On 2013-09-20 11:37, Szymon Gatner wrote:
>>>>>
>>>>>> If only std algorithms took containers (by that I mean things that
>>>>>> container for accepts too) as arguments (and not iterators)...
>>>>>> even in the form of new functions like foreach_all, transform_all
>>>>>> etc.
>>>>>
>>>>> Can't a container be a range as well?
>
> A container should not be confused with a range. That way leads to
> dragons. :-P  (It's rather unfortunate that built-in arrays conflate the
> two, it leads to a lot of wrong code that works only with arrays but not
> with "real" ranges.)
>
>
>>>> For Christ sake no, no and no. For starters range skips/drops
>>>> elements when iterating, and thusly iteration has its own state that
>>>> is useless for a container otherwise.
>>>
>>> That would be a filtering range which adds additional logic that
>>> costs exactly the same as an if() statement inside a for loop when
>>> filtering on condition manually.
>>>
>> Filtering is just an adapter.
>> Better examples are traversing e.g. binary-tree depth-first
>> in-order, or post-order and that would require state.
>> Again it's easy to miss by looking at built-in arrays.
>
> Traversing the tree at all requires state, whether or not you do it with
> ranges. You either put the state on the runtime stack (recursion), or
> you put the state on the heap in the range adaptor. Same thing.
>
>
>>>> TL;DR: Suboptimal, unnatural and error prone are keywords.
>>>
>>> Why would it be suboptimal?
>>
>> If said tree needs to be a range I would be horrified to see how it
>> manges to be at the same time a range that (for the sake of example)
>> traverses said tree depth-first in-order.
>>
>> Not even talking about trees having no one "natural" range over them.
> [...]
>
> Some trees do, like document trees. But yeah, in general, you don't have
> a natural ordering to trees.

>
> But then again, the whole point of ranges is *linear* traversal. If
> you're not doing that, then it's probably the wrong abstraction to use.

Then traversing all files in directory in specific order is not interesting to you? I hardly find that logical. Abstraction is wrong only where it doesn't make sense and here it does. There is something linear about tree and that is every sane path taken through it is linear  (after all there are no cycles).

BTW I see nothing problematic in seeking a minimal set of primitives that would allow working on tree-like topology. It won't be the same range but never the less useful.

> (FWIW, while SortedRange is a neat hack, I haven't actually found it
> that useful in practice. Most of the ranges I actually use are for the
> cases where it's an input/forward range and you don't want to store the
> whole thing, so random access is impractical.

Sorted forward range is actually fine. You may do interesting things with them like O(N+M) merging, subtracting and whatnot. Set operations for the win (they are not defined in Phobos yet).

> The cases where I actually
> have random access usually turn out to be plain ole arrays anyway, so
> the SortedRange abstraction isn't really necessary.)
>
> So for trees, I'd argue that you need a tree-specific iteration
> abstraction, not ranges, which are linear. It's a clear case of
> structure conflict. ;-)
>
>
> T
>


-- 
Dmitry Olshansky

Am 20.09.2013 16:24, schrieb renoX:
> On Friday, 20 September 2013 at 09:43:10 UTC, bearophile wrote:
> [cut]
>> Another thing to notice is that Haskell user defined operators
>> sometimes hurt my ability to read code. This is composed with the
>> precedent problem.
>
> ++
> I remember that reading a tutorial about Elm felt much more easy to read
> than other text based on Haskell because Elm's author took great care of
> choosing readable operators..
>
> That said, he made the same mistake as Haskell's authors: currying is a
> *mathematical detail* which shouldn't obscure function type:
> 'f: a->b->c' is less readable than 'f: a,b->c'.
>
> renoX

That is standard in all languages of the ML family, not only Haskell.