Why Strings as Classes?

[superdan]

Robert Fraser Wrote:

> superdan wrote:
> > Christopher Wright Wrote:
> > 
> >> superdan wrote:
> >>>> class LinkedList(T)
> >>>> {
> >>>> 	Node!(T) head;
> >>>>
> >>>> 	/** Gets the ith item of the list. Throws: SIGSEGV if i >= length of 
> >>>> the list. Time complexity: O(N) for a list of length N. This operation 
> >>>> is provided for completeness and not recommended for frequent use in 
> >>>> large lists. */
> >>>> 	T opIndex(int i)
> >>>> 	{
> >>>> 		auto current = head;
> >>>> 		while (i)
> >>>> 		{
> >>>> 			current = current.next;
> >>>> 		}
> >>>> 		return current.value;
> >>>> 	}
> >>>> }
> >>> oopsies. houston we got a problem here. problem is all that pluggable sort business works only if it can count on a constant time opIndex. why? because sort has right in its spec that it takes o(n log n) time. if u pass LinkedList to it you obtain a nonsensical design that compiles but runs afoul of the spec. because with that opIndex sort will run in quadratic time and no amount of commentin' is gonna save it from that.
> >> WRONG!
> >> Those sorting algorithms are correct. Their runtime is now O(n^2 log n) 
> >> for this linked list.
> > 
> > you got the wrong definition of correct. sort became a non-scalable algo from a scalable algo. whacha gonna say next. bubble sort is viable?!?
> 
> No, YOU got the wrong definition of correct. "Correct" and "scalabale" 
> are different words. As are "correct" and "viable". In Java, I've been 
> known to index into linked lists... usually ones with ~5 elements, but 
> I've done it.

yeah. for starters my dictionary fails to list "scalabale".

> >>> this design is a stillborn.
> >>>
> >>> what needs done is to allow different kinds of containers implement different interfaces. in fact a better way to factor things is via iterators, as stl has shown.
> >> You didn't ask for an O(1) opIndex on a linked list. You asked for a 
> >> correct opIndex on a linked list.
> > 
> > the correct opIndex runs in o(1).
> 
> No, the SCALABLE opIndex runs in O(1). The CORRECT opIndex can run in 
> O(n^n) and still be correct.

stepanov has shown that for composable operations the complexity must be part of the specification. otherwise composition easily leads to high-order polynomial that fail to terminate in reasonable time. opIndex is an indexing operator expected to run in constant time, and algorithms rely on that. so no. opIndex running in o(n^n) is incorrect because it fails it spec.

> >> Any sorting algorithm you name that 
> >> would work on an array would also work on this linked list. Admittedly, 
> >> insertion sort would be much faster than qsort, but if your library 
> >> provides that, you, knowing that you are using a linked list, would 
> >> choose the insertion sort algorithm.
> > 
> > no. the initial idea was for a design that allows that cool mixing and matching gig thru interfaces without knowing what is where. but ur design leads to a lot of unworkable mixing and matching.
> 
> Again, WORKABLE, just not SCALABLE. You should wrap your head around 
> this concept, since it's been around for about 30 years now.

guess would do you good to entertain just for a second the idea that i know what i'm talking about and you don't get me.

> > it is a stillborn design.
> 
> Tell that to Java, the world's most used programming language for new 
> projects. Or C#, the world's fastest growing programming language. Or 
> Tango, one of D's standard libraries.

here you hint you don't understand what i'm talking about indeed. neither of java, c#, or tango define a[n] to run in o(n). they define named functions, which i'm perfectly fine with.

> > my point was opIndex should not be written for a list to begin with.
> 
> Yes it should be. Here's a fairly good example: Say you have a GUI 
> control that displays a list and allows the user to insert or remove 
> items from the list. It also allows the user to double-click on an item 
> at a given position. Looking up what position maps to what item is an 
> opIndex. Would this problem be better solved using an array (Vector)? 
> Maybe. Luckily, if you used a List interface throughout your code, you 
> can change one line, and it'll work wither way.

funny you should mention that. window manager in windows 3.1 worked exactly like that. users noticed that the more windows the opened, the longer it took to open a new window. with new systems and more memory people would have many windows. before long this became a big issue. windows 95 fixed that.

never misunderestimate scalability.

> > wrong. you only need to define your abstract types appropriately. e.g. stl defines forward and random iterators. a forward iterators has ++ but no []. random iterator has both. so a random iterator can be substituted for a forward iterator. but not the other way. bottom line, sort won't compile on a forward iterator. your design allowed it to compile. which makes the design wrong.
> 
> STL happens to be one design and one world-view. It's a good one, but 
> it's not the only one. My main problem with the STL is that it takes 
> longer to learn than the Java/.NET standard libraries -- and thus the 
> cost of a programmer who knows it is higher. But there are language 
> considerations in there too, and this is a topic for another day.

cool. don't see how this all relates to the problem at hand.

> > btw my respect for tango improved when i found no opIndex in their list container.
> 
> http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/LinkSeq.d#L176

here you gently provide irrefutable proof you don't get what i'm sayin'. schveiguy did. the page fails to list opIndex. there is a function called 'get'. better yet. the new package lists a function 'nth' suggesting a linear walk to the nth element. good job tango fellas.