www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - couple of really noob questions (ranges, toString)

reply Michael Woods <alienhunter3 gmail.com> writes:
Hi.  To describe my background really quickly, I'm a CS student with experience
mostly in Java and Python.  (I've done some C++ work, but not a lot.)
Basically, I have two really newbish questions that I haven't been able to
figure out from the library and language references, and I'm sure the answers
are perfectly obvious, so apologies in advance.

I'm writing a few collections classes in D (just to get the feel for the
language; I realize that there are probably much better implementations
available
from the dsource community, or w/e) and right now, I'm writing a linked list
template class.  ( 'linkedList(E)' )

First question:  toString().  is this handled exactly the way that it is in
Java?  I've written a toString method for my class, I'll post it below.  I can
call this method, and it works perfectly, if called specifically.

linkedList!(int) list = new linkedList!(int)();
writeln(list.toString());  //this works perfectly (if I add elements to the
list, the results are the same)

writeln(list);  //this fails(at compile time) with a godawfully long error:

"/usr/local/include/d/phobos2/std/format.d(1455): Error: template
std.format.formatValue(Writer,T,Char) if (is(const(T) == const(void[])))
formatValue(Writer,T,Char) if (is(const(T) == const(void[]))) matches more than
one template declaration,
/usr/local/include/d/phobos2/std/format.d(1126):formatValue(Writer,T,Char) if
(isInputRange!(T) && !isSomeChar!(ElementType!(T))) and
/usr/local/include/d/phobos2/std/format.d(1297):formatValue(Writer,T,Char) if
(is(T == class))"

Anyway, my toString method is as follows:

public string toString(){


        if (head !is null){
            char[] outString = "[".dup;
            llNode cursor = head;  //llNode is a private node class
            while(cursor.next !is  null){
                outString = outString ~ text(cursor.datum) ~", ";
                cursor = cursor.next;
            }
            outString = outString ~ text(cursor.datum) ~ "]";
            return outString.idup;
        }
        else{
            return "[]";
        }


    }

I guess that I'm asking if write() calls an object's toString method, or if
there's some other behavior going on that I'm ignorant of.


Question 2:

This is more a broad request for clarification, than a specific question.  I'm
trying to understand the range interfaces.  I'm trying to make this
linkedList class implement the InputRange interface (among others).  I'm pretty
sure that I've got opApply, opIndex, and opSlice figured out, but I can't
for the life of me figure out exactly what front(), popFront(), and empty() are
supposed to be doing.  (I realize that the opX functions aren't part of the
InputRange interface.)  Is popFront supposed to delete the actual front element
from the list?  Or is it supposed to represent some kind of internal
pointer that is there solely for the purpose of range functionality?  If the
latter, how should the pointer get reset after it has gotten to the end once?
Should the pointer even need to be reset, or is popFront supposed to only cycle
through once during the entire lifetime of the range object?

I really have tried to answer this question for myself, but I guess that I need
more experience to actually be able to understand all of the documentation
the way that it is currently written.  Also, I've attached the d source files
in question. One is the linkedList class, one is the test executable that I'm
trying to test it with.  linkedList.d should be in a directory mwcollections
(since i'm trying to set up mwcollections as a module).  I'd have just sent an
archive file with this directory structure already in place, but I wouldn't
want anyone to think that I was slipping them a virus.  :)  (though 4KB is a
little small to be a virus.)  Feel free to crack jokes at my poor coding style,
I'm not really much more than an amateur at this.  I don't know if this is
relevant or not, but I'm using the digitalmars dmd compiler version 2.050, on a
gentoo linux system.

Thanks in advance.

Mike W
Nov 01 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Michael Woods:

 First question:  toString().  is this handled exactly the way that it is in
Java?  I've written a toString method for my class, I'll post it below.  I can
 call this method, and it works perfectly, if called specifically.
 
 linkedList!(int) list = new linkedList!(int)();
 writeln(list.toString());  //this works perfectly (if I add elements to the
list, the results are the same)
 
 writeln(list);  //this fails(at compile time) with a godawfully long error:

Welcome here. A reduced test case: import std.stdio: writeln; import std.range: InputRange; class LinkedList(T) : InputRange!T { T front() { return T.init; } T moveFront() { return T.init; } void popFront() {} bool empty() { return true; } int opApply(int delegate(ref T) dg) { return 0; } int opApply(int delegate(ref size_t, ref T) dg) { return 0; } override string toString() { return "foo"; } } void main() { LinkedList!(int) list = new LinkedList!int; writeln(list); //writeln(list.toString()); } Bye, bearophile
Nov 01 2010
prev sibling next sibling parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
Hello and welcome.

The toString does work the same as it does in Java,  I suggest using override.

override string toString();

Your error actually indicates a bug in Phobos. It has a special print function
for classes and for an input range. These are conflicting with each other and
has nothing to do with your toString. Luckily once your container is properly
created, you won't have this issue. So I will file the bug sometime.

The first thing to note is that you are creating a container[1] and not an
InputRange[2]. The distinction here is that a Range is consumed, you don't
iterate over them multiple times. A container on the other hand has different
access requirements. (Documentation on Containers is a little messed up.)

Generally opApply is not used if you are building a Range, but does have its
uses and I believe has priority in a foreach statement.

To build on the example from bearophile You would have something like this with
your selection of Container functions:

import std.stdio: writeln;

class LinkedList(T) {
   override string toString() { return "foo"; }

   struct Range(T) {
      T front() { return T.init; }
      T moveFront() { return T.init; }
      void popFront() {}
      bool empty() { return true; }
   }

   Range!T opSlice() {
      Range!T r;
      return r;
   }
}
void main() {
    LinkedList!(int) list = new LinkedList!int;
    writeln(list);
    //writeln(list.toString());
}


1. http://digitalmars.com/d/2.0/phobos/std_container.html
2. http://digitalmars.com/d/2.0/phobos/std_range.html
Nov 01 2010
parent reply Michael Woods <alienhunter3 gmail.com> writes:
Thanks for your replies, bearophile and Jesse Phillips.  :)

Jesse, that makes a lot more sense, now.  Thanks a lot for clearing
that up for me.

Mike W
Nov 01 2010
parent Jesse Phillips <jessekphillips+D gmail.com> writes:
Michael Woods Wrote:

 Thanks for your replies, bearophile and Jesse Phillips.  :)
 
 Jesse, that makes a lot more sense, now.  Thanks a lot for clearing
 that up for me.
 
 Mike W

I kept making the mistake of trying to use containers as a range too (end up creating a reset function to bring it back to the beginning). Also note that the usage for getting a range will look like: foreach(item; myData[]) ... And if you want to track it http://d.puremagic.com/issues/show_bug.cgi?id=5154
Nov 01 2010
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On Mon, 1 Nov 2010 20:02:14 +0000 (UTC)
Michael Woods <alienhunter3 gmail.com> wrote:


 I guess that I'm asking if write() calls an object's toString method

Exactly.
 Question 2:
=20
 This is more a broad request for clarification, than a specific question.=

 linkedList class implement the InputRange interface (among others).  I'm =

can't
 for the life of me figure out exactly what front(), popFront(), and empty=

of the
 InputRange interface.)  Is popFront supposed to delete the actual front e=

 pointer that is there solely for the purpose of range functionality?  If =

once?
 Should the pointer even need to be reset, or is popFront supposed to only=

I'm not 100% sure because I'm also a D noob, rather projecting knowledge fr= om other PLs -- so take my words with precaution. [Please, D gurus, tell if= what follows is ok.] If I'm right, the point of ranges is to offer kinds of particular views on = all, a part, or an aspect of a collection; without having to create a separ= ate collection just for that. Typical use is for traversal (iteration). Sin= ce you know python, its iterators (and generators) are kinds of ranges. Eg = you can write an iterator to traverse a list in reverse order, or every thi= rd element -- without creating new lists for that. You can also make an ite= rator or generator on a "virtual list", eg generating squares of ints in a = given range. front(), popFront(), and empty() together form a way to implement a sequent= ial iterator on a collection. [But I must admit it really does not fit my P= OV on the topic -- this trio strongly smells functional :-) and actually ba= sically models a linked list -- I'm certain its designer has a heavy Lisp b= aggage! I would rather have a hasNext() and next() duo.] Now, their working is simply to allow moving across elements, so no popFron= t() does not pop. Examples: routine dynarray list popFront inc(ptr) current =3D current.next front() *ptr current.element (possibly dereferenced) empty() length =3D=3D 0 length =3D=3D 0 (maintained as field) On a "true" linked list where every node implements the properties & method= s of a list, then popFront is returning the second node, meaning the head o= f the rest: l =3D l.next. Hope most of this is correct (critics welcome). Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Nov 01 2010
parent Jesse Phillips <jessekphillips+D gmail.com> writes:
spir Wrote:

 I'm certain its designer has a heavy Lisp baggage! I would rather have a
hasNext() and next() duo.]

To build on what Jonathon wrote. There are three benefits that I have enjoyed having front and popFront instead of the next and hasNext. The first is simply that if I want to make use of the element multiple times I don't need to find storage for it, I can just call front every time I need it. The second is when building a range you don't need to look ahead to find out if another element is available. This means I don't have to store the next value along with the current value. For example std.algorithm has a function filter. You provide it with a Range and ask it to only return values that meet some criteria. Since the elements that will be returned aren't going to be the number in the original Range it can't just take its length. And with that you don't end up with unneeded calculations if the next element isn't needed. The one annoying thing with this has been the need to initialize the Range (calling popFront after creating the range). Since the first item may not be an item that meets the criteria, or that there are any items, the range needs to be advanced so that it finds the correct element.
Nov 01 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 01 November 2010 18:05:19 spir wrote:
 On Mon, 1 Nov 2010 20:02:14 +0000 (UTC)
 
 Michael Woods <alienhunter3 gmail.com> wrote:
 I guess that I'm asking if write() calls an object's toString method

Exactly.
 Question 2:
 
 This is more a broad request for clarification, than a specific question.
  I'm trying to understand the range interfaces.  I'm trying to make this
 linkedList class implement the InputRange interface (among others).  I'm
 pretty sure that I've got opApply, opIndex, and opSlice figured out, but
 I can't for the life of me figure out exactly what front(), popFront(),
 and empty() are supposed to be doing.  (I realize that the opX functions
 aren't part of the InputRange interface.)  Is popFront supposed to
 delete the actual front element from the list?  Or is it supposed to
 represent some kind of internal pointer that is there solely for the
 purpose of range functionality?  If the latter, how should the pointer
 get reset after it has gotten to the end once? Should the pointer even
 need to be reset, or is popFront supposed to only cycle through once
 during the entire lifetime of the range object?

I'm not 100% sure because I'm also a D noob, rather projecting knowledge from other PLs -- so take my words with precaution. [Please, D gurus, tell if what follows is ok.] If I'm right, the point of ranges is to offer kinds of particular views on all, a part, or an aspect of a collection; without having to create a separate collection just for that. Typical use is for traversal (iteration). Since you know python, its iterators (and generators) are kinds of ranges. Eg you can write an iterator to traverse a list in reverse order, or every third element -- without creating new lists for that. You can also make an iterator or generator on a "virtual list", eg generating squares of ints in a given range. front(), popFront(), and empty() together form a way to implement a sequential iterator on a collection. [But I must admit it really does not fit my POV on the topic -- this trio strongly smells functional :-) and actually basically models a linked list -- I'm certain its designer has a heavy Lisp baggage! I would rather have a hasNext() and next() duo.] Now, their working is simply to allow moving across elements, so no popFront() does not pop. Examples: routine dynarray list popFront inc(ptr) current = current.next front() *ptr current.element (possibly dereferenced) empty() length == 0 length == 0 (maintained as field) On a "true" linked list where every node implements the properties & methods of a list, then popFront is returning the second node, meaning the head of the rest: l = l.next. Hope most of this is correct (critics welcome).

The best place to start learning about ranges is probably here: http://www.informit.com/articles/article.aspx?p=1407357 front, popFront(), and empty make perfect sense as they are and work quite well. hasNext() and next() have the serious drawback of mixing iterating through the range and getting an element in it. It's one of the serious flaws in Java's iterators. It's far better to have getting the current or front element be separate from moving or popping the next one. In any case, you can use ranges in a manner similar to lisp's slists, but they're definitely more flexible than that, since they're an abstraction rather than a container. And ultimately, there isn't really anything functional about them. They just allow for you to use them in a manner similar to slists which are heavily used in functional languages. Ranges are extremely powerful and generally are _way_ better than iterators (though there are a few cases where they become more awkward than iterators). - Jonathan M Davis
Nov 01 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Mon, 1 Nov 2010 18:47:38 -0700
Jonathan M Davis <jmdavisProg gmx.com> wrote:

 The best place to start learning about ranges is probably here:=20
 http://www.informit.com/articles/article.aspx?p=3D1407357
=20
 front, popFront(), and empty make perfect sense as they are and work quit=

 hasNext() and next() have the serious drawback of mixing iterating throug=

 range and getting an element in it. It's one of the serious flaws in Java=

 iterators. It's far better to have getting the current or front element b=

 separate from moving or  popping the next one.

Thank for the pointer. Note That I know exactly nothing of Java. In fact, I used this scheme and t= hose names spontaneously to implement traversal of custom structs in Oberon= (that has no such notion). There's a point I don't understand in your argument: "...the serious drawba= ck of mixing iterating through the range and getting an element in it". Isn= 't this precisely what popFront() does, stepping and returning an element? = Or is "pop" in "popFront" misleading? (I've followed your pointer, but the = site is so designed that the article is spread over 15 pages!) To move forward without popping, you'd need a kind of step() method that ju= st follows the next pointer; really complementary to front(). Or is there s= omething I misunderstand? But since typical use is iteration, does it make = sense to separate stepping and reading? I now realise that my previous comment on the method trio vs my point of vi= ew is wrong; the functionality is the same, done the same way, only naming = reveals a different pov: next() is popFront() seen differently, hasNext() i= s !empty(). Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Nov 01 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 01 November 2010 19:21:27 spir wrote:
 On Mon, 1 Nov 2010 18:47:38 -0700
 
 Jonathan M Davis <jmdavisProg gmx.com> wrote:
 The best place to start learning about ranges is probably here:
 http://www.informit.com/articles/article.aspx?p=1407357
 
 front, popFront(), and empty make perfect sense as they are and work
 quite well. hasNext() and next() have the serious drawback of mixing
 iterating through the range and getting an element in it. It's one of
 the serious flaws in Java's iterators. It's far better to have getting
 the current or front element be separate from moving or  popping the
 next one.

Thank for the pointer. Note That I know exactly nothing of Java. In fact, I used this scheme and those names spontaneously to implement traversal of custom structs in Oberon (that has no such notion). There's a point I don't understand in your argument: "...the serious drawback of mixing iterating through the range and getting an element in it". Isn't this precisely what popFront() does, stepping and returning an element? Or is "pop" in "popFront" misleading? (I've followed your pointer, but the site is so designed that the article is spread over 15 pages!) To move forward without popping, you'd need a kind of step() method that just follows the next pointer; really complementary to front(). Or is there something I misunderstand? But since typical use is iteration, does it make sense to separate stepping and reading? I now realise that my previous comment on the method trio vs my point of view is wrong; the functionality is the same, done the same way, only naming reveals a different pov: next() is popFront() seen differently, hasNext() is !empty().

In C++, iterators are effectively pointers. ++ increments, -- decrements, and * dereferences the element that it currently points to. The same goes for C#, except that they didn't overload * to get the current element but rather used a property function (Current IIRC, but I haven't used C# in a while). In both cases, accessing the current element does not move the iterator. Moving the iterator is completely separate from accessing what it points to. In Java, on the other hand, they have hasNext(), hasPrev(), next(), and previous(), and the iterator doesn't point _at_ a particular element but rather _between_ them. So, hasNext() and hasPrevious() return a bool telling you whether there is a next or previous element respectively. next() returns the next element and moves the iterator whereas previous() returns the previous iterator and moves the iterator backwards. It means that you have to save the element every time that you access the next one rather than being able to use the iterator to get it again. It also makes it essentially impossible (or extremely ugly) to try and designate a range of any kind with iterators, since they don't actually point _at_ elements at using iterators alters them. Of course, Java didn't end up using iterators in a fashion that algorithms could be used for them (like C++ did), but it would be a pain even if you tried due to the lack of separation between moving an iterator and accessing what it refers to. D uses ranges, which are at their most basic a pair of iterators but which are far more flexible than that, since you don't have to actually use iterators for their implementation. Things like infinite ranges become possible, which aren't really doable in the same way with iterators. They also completely avoid the issues related to passing iterators in the wrong order or which point to different containers. There are various types of ranges, each with a set of functions that they must have, but the most basic is an InputIterator which has front, popFront(), and empty. front gives the first element in the range without altering the range. popFront() pops the first element from the range, making the next elment (if any) the first element in the range. popFront() is void and does not return what it pops. empty indicates whether there are any more elements left in the range. Using front when a range is empty will generally result in an exception being thrown, because there is no first element in the range. The term "pop" does _not_ mean that an element is returned but that it is removed from the range. This is true for pretty much anything that uses a pop function in any language - stacks, lists, etc. It _is_ true that many implementations choose to have pop return the element which is popped, but that's an implementation detail. The term pop merely indicates that an element is removed from an end of a range or container. - Jonathan M Davis
Nov 01 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Mon, 1 Nov 2010 20:40:30 -0700
Jonathan M Davis <jmdavisProg gmx.com> wrote:

 The term "pop" does _not_ mean that an element is returned but that it is=

 removed from the range. This is true for pretty much anything that uses a=

 function in any language - stacks, lists, etc. It _is_ true that many=20
 implementations choose to have pop return the element which is popped, bu=

 that's an implementation detail. The term pop merely indicates that an el=

 is removed from an end of a range or container.

All right, that's where I went wrong. Thank you for the clear explanation. = (Now, I will continue with the article by Andrei Alexandrescu, 10 pages lef= t :-) [But I do not know of any pop not returning the removed value in any lang o= r library; instead, pop is the favorite example of people arguing against t= he distinction between actual functions (result, but no effect) and actions= (effect, but no result): naughty pop does both. Maybe call it here remove()? Even if "pop"'s sense was defined by an all-mi= ghty authority, we could hardly avoid people having different expectations = born from previous experience, esp when it's so widespread: the two pop exa= mples at http://en.wikipedia.org/wiki/Stack_%28data_structure%29 return the= element.] I would also find current() much clearer than front(), since from the clien= t's perspective it looks like shrinking the collection (or view) instead of= traversing it; see the confusion expressed by the OP's original question; = but well... Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Nov 02 2010
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, November 02, 2010 04:16:58 spir wrote:
 On Mon, 1 Nov 2010 20:40:30 -0700
 
 Jonathan M Davis <jmdavisProg gmx.com> wrote:
 The term "pop" does _not_ mean that an element is returned but that it is
 removed from the range. This is true for pretty much anything that uses a
 pop function in any language - stacks, lists, etc. It _is_ true that
 many implementations choose to have pop return the element which is
 popped, but that's an implementation detail. The term pop merely
 indicates that an element is removed from an end of a range or
 container.

All right, that's where I went wrong. Thank you for the clear explanation. (Now, I will continue with the article by Andrei Alexandrescu, 10 pages left :-) [But I do not know of any pop not returning the removed value in any lang or library; instead, pop is the favorite example of people arguing against the distinction between actual functions (result, but no effect) and actions (effect, but no result): naughty pop does both. Maybe call it here remove()? Even if "pop"'s sense was defined by an all-mighty authority, we could hardly avoid people having different expectations born from previous experience, esp when it's so widespread: the two pop examples at http://en.wikipedia.org/wiki/Stack_%28data_structure%29 return the element.]

C++'s pop functions don't return anything either, but it is true that many libraries in many languages choose to have pop functions return the value which is being popped. Having popFront() return a value in addition to having front look at the first value in the range wouldn't necessarily be a problem, but it isn't strictly speaking necessary. In some languages (certainly C++, though I'm not sure about D), returning a value which isn't used can mean a wasted copy or object construction which can be inefficient (particularly when dealing with large objects on the stack). Whether a pop function returns anything tends to depend on how much an efficiency concern the library writer thinks that it is and how likely they think that it is that the popped value is going to be wanted. If it's expected that someone will always want the popped value, then it can be quite nice to have the pop function return it, but if there's a good chance that they won't, then it could be an unwanted inefficiency. It all depends on the goals and concerns of the library writer. In this case, D chose to not have popFront() return anything.
 I would also find current() much clearer than front(), since from the
 client's perspective it looks like shrinking the collection (or view)
 instead of traversing it; see the confusion expressed by the OP's original
 question; but well...

Except that unlike an iterator (which indicates a single element), a range indicates a range of elements, so it can have both a front and a back (similar to having two iterators indicate a range of elements), so current() would be highly confusing once you went beyond input or forward ranges. For instance, bi- directional ranges have back and popBack(), and random-access ranges have the subscript/slicing operator which can access an element or range of elements in the range, so current() would become highly confusing. What you have is a range of elements which has a clear first element (and assuming it isn't infinite or of indefinite length) a clear last element. So, front and back access them and popFront() and popBack() pop them. It is indeed generally a view of a collection of elements, but there is a definite order to them, whereas current() does not indicate order. - Jonathan M Davis
Nov 02 2010
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
Jonathan M Davis wrote:

 In some languages (certainly C++, though I'm
 not sure about D), returning a value which isn't used can mean a 

 object construction which can be inefficient (particularly when 

 objects on the stack). Whether a pop function returns anything tends 

 on how much an efficiency concern the library writer thinks that it 

 likely they think that it is that the popped value is going to be wanted.

The stronger reason why pop() doesn't return the object in C++ is about exception safety. To me this topic is one of the most fascinating stories in C++'s history. Very briefly, Tom Cargill noted that exception safety gave a false sense of security and invited the C++ community to write an "exception-correct version of Stack": http://ptgmedia.pearsoncmg.com/images/020163371x/supplements/Exception_Handling_Article.html It took the community years to come up with an understanding of C++ exception safety. Herb Sutter posted the following "guru of the week" puzzle: http://www.gotw.ca/gotw/008.htm which eventually ended up being in his later book "Exceptional C++", which turned out to be the biggest eye opener for me. Especially the exception safety section must be understood by any C++ programmer. The solution for Tom Cargill's challenge turned out to be "cohesion", where pop() should not return the value; that should be provided by top(). The efficiency that came from having top() was a bonus. Ali
Nov 03 2010