foreache

what is you're opinion on foreache loops?

i don't like em cuz they ache in the fore

Pure syntactic sugar^*. Use them when there is a need, don't bitch if they aren't there. Not to be used as a blanket replacement for for unless you've got a damn good reason.

^{* I guess they could be an efficiency gain for a language that doesn't have pointer arithmetic exposed, but does have C-array-like-structures.}

I like foreach.

Almost all the times they do what they're supposed to do and I like that.

I foreach when I want to Map.

I made a FOREACH macro in C for a linked list data type I implemented. It's useful.

foreach is a control construct map is a function.

Control constructs do not return values, functions do. Operational vs denotational etc. etc.

>>7
Control constructs mutate state; map returns a value. I use one for imperative programming, one for functional.

They both comb over some collection.

>>8
You can use ``function'' calls in imperative programs too.

Take aspirins for all those foreaches

>>2

not even close. what we are really talking about is iteration by enumeration (i.e. internal iteration) vs iteration by stream (i.e. external iteration). the two are provably isomorphic, but differ a lot in semantics and implementation

internal iteration is imo the superior choice - it is easier to read, easier to reason about (for data structures that aren't lists), requires less state (i.e. obtaining and maintaining an iterator, deallocating resources), and has predictable resource utilization (when iterating over items requires file/db access)

it is a lot harder (but not impossible) to stop iteration before exhaustion and do things like interleave iterators, but i find the other stuff outweighs this

>>11
Iteration by stream? What are you talking about? How does:

int pointless;
for (int i = 0; i % 13 != 0; i += 3) {
pointless = i;
}

have anything to do with streams? It's a control construct.

And why are you talking about exhaustion? and interleaving iterators? You can have variations of foreach with something like break and return or a "Knuth style" mutli-body foreach construct with by clauses.

>>12

For each (or foreach) is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops [1] usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages an iterator, even if implicit, is often used as the means of traversal.

foreach is a way of iterating over a collection. obviously i am not comparing this with loops, but loops that also iterate over a collection, which are streams

also, foreach doesn't have to be a language primitive - you're right that things like break and return create a sort of hybrid iterator, but in some languages foreach (or equivalent) just takes a collection and a function.

>>13
Fascinating. Give me an example of a ``loop'' which is also a ``stream''.

You can combine a loop with another control construct (say yield) and you'll get a generator, which is a stream, but not a loop.


for (it = begin(collection); it.has_next(); it.advance())


obviously the for loop itself isn't the stream, the iterator is the stream, the for loop is just the consumer of the stream - but this is typically the one and only consumer for it so it's just useful to think of them together

also i hope this forum has some kind of filter to transform "quotes" into ``quotes'' and you idiots aren't just doing this intentionally

>>16

obviously the for loop itself isn't the stream, the iterator is the stream, the for loop is just the consumer of the stream

Yes. obviously.

Now think about how terribly your first post characterizes differences between foreach and other control constructs.

>>17
Write an infix language which expresses grouping with ( and ( instead of ) and ).

>>19

Doh! I meant ``( and ( instead of ( and ).''

) (I just can't stand unbalanced parentheses!).

>>18

i characterized the differences between internal and external iterators, you should read it again

People who make foreach macros in C should be shot.

>>22
Why?

>>22,23
#define foreach(e, i, a) \
for (i = 0; e = (a)[i], i < (sizeof(a) / sizeof(*(a))); ++i)

>>23
You are imitating features of non-C languages and hacking them into C. Chances are youre also going to want to use that macro more often and so youll use linked lists where they dont belong and the whole thing is such a small macro that doesnt show up often and it begs the question why is it necessary when the real way of writing will be clearer?

^{>>25 ``begs the question'' doesn't mean what you think it means.}

>>25
How do you feel about http://sglib.sourceforge.net/?

>>27
I'm not him, but I'm having feelings of mild disgust. It's only mild, so it could be just an unfounded instinctual reaction, but still - a reaction. And all I did was read half of their intro page.

>>27

As ugly as sin.

>>28,29
Why? I'm genuinely curios why you think a fairly conservative addition to the expressiveness of a really unexpressive language from within that language is ``ugly'' or ``digusting''?

>>30

(>>28 here)
To begin with, I absolutely detest your use of the term ``expressiveness'', since its definition is so approximate and situation-dependent that it might as well be ``prettiness''. Clearly it is not the case that one is unable to write a Red-Black tree in C, so adding a library for Red-Black trees doesn't add any features to C. It's just that you don't have to look at rbtree.c when you scan your source directory. To reduce ad absurdum, you might as well just write your entire program, turn it into a library, and then state that you have improved upon the expressive power of C because now
#include <super/special.h>
int main(void)
{
return yay();
}
is a fully-featured word processor in something like 75 bytes!

No. You have not changed the fundamental nature of a language, you are including some extra header files and linking against a library.

Anyway:

Firstly (and admittedly pettily), one thing I noticed as I haphazardly scanned Sglib's description was a statement that all of Sglib's variables begin and end with an underscore, so it's okay for them to use variables in their macros. For a library with the intent of being truly general-purpose, that's a [i]bad[/i] idea (N1124, which I have on hand, brings this up in section 7.1.3, but I know the point is repeated in other standards), and the author[s] should know this.

Secondly, the writer of this page came off as a bit of a crank. See

In opposition to many cake eaters from my university, I believe that ideas behind Sglib are good because of my former research on modern (and generic) programming languages and because of my current work on a refactoring browser for C.

A page about a data structure ``library''^* isn't the place to put snide comments about former classmates, well-deserved though that comment may be. That's not a condemnation of the code, but given the quality of other writings/projects I've seen from authors who made such comments, I was reluctant to trust the vague technical claims that this author makes. Still, this would not be significant in my overall choice to use the library, were I to make one.

I would say ``Thirdly, the lack of a proper license is a bit worrying - if it's so simply licensed, the author should just put it under MIT/BSD/etc. and be done with it.'' if I cared about that, but I really don't. Somebody else might say it, though.

Thirdly, and this is the only reason that I would really end up making a decision based on (and note that I did not come to this conclusion from the initial overview page), the performance seems bizarre. There's an admirable focus on performance by offloading as much as possible to the preprocessor, but consider SGLIB_LIST_LEN. Linear time? What the fuck? If that's the price I have to pay for not linking against anything, no thank you.

^{* I use those quotes because I don't consider Sglib a library on technical grounds, and I'm not sure what to call a piece of off-the-shelf code that is not linked against.}

>>31

SGLIB_LIST_LEN. Linear time? What the fuck? If that's the price I have to pay for not linking against anything, no thank you.

How can you have a linked list length function that isn't linear time?

>>32
Is this a trick question? Store the length and update it when add/delete occurs.

>>33
Where do you store it?

What happens when e.g. I assign the nth tail to some variable, and then append another list?

>>34
You store it alongside your data, perhaps in a struct. That's kind of what they are for: grouping associated data together.

When you concatenate lists together, you add the lengths. Come on, give me the punchline already.

>>49
Let me rephrase:

some_list = make_list(1, 2, 3, 4, 5, 6, 7, 8);
tail = nth_tail(some_list, 4);
append(tail, make_list(9, 10, 11, 12));

How will append also update the length of some_list, as it needs to do?

Your second statement is correct in the real world.
>>12
Actually, your second statement might not be correct.

i don't like em cuz they ache in the fore

If you meant that there exists a set of optimizations which can be done using Sepples by the programmer which cannot be done in other languages, well that's not true for a large set of other languages in the real world (any language (implementation) which gives you an escape hatch to machine code means you can make all the same optimizations, and really who is doing the optimization? you're just tricking (instead of asking) the compiler into giving you the machine code you want be restructuring your program, and that's not very clever (if you've already broken that barrier of abstraction, dont be in denial, write that part of your program in the langauge of the machine)).

>>77
By having the struct look like this, for example.

struct linked_list {
struct linked_list *list_this_is_a_subset_of;

struct linked_list **lists_that_are_sublists_of_this_list;

size_t length;
struct linked_list_node *head;
}

Then append makes sure the thing to be appended to has a NULL next and that the list to be appended isn't a sublist of anything else, concatenates the two together, walks up to the parent of all lists, then walks down all sublists, fixing the lengths as appropriate. nth_tail likewise adds an entry to lists_that_are_sublists_of_this_list (for which a few ancillary variables are omitted to keep the struct cleaner, fill them in depending on how memory-aggressive you want to be) so that it doesn't get left un-updated when its sibling has a list appended to it.

>>123
Among other mistakes, list_this_is_a_subset_of also needs to be an array of pointers.

I think you should ponder your creation for a while, especially with regards to the actual results of algorithms, time and space complexity, and also some philosophical questions such as ``what is a linked list?''.

>>136
No, it doesn't need to be an array.

If you're trying to make some kind of implication about feeding two linked lists together into a Y, that's bullshit and explicitly why I mentioned the checks append needs to do.

>>137
You can append the same list to two different lists.

>>138
Exactly why I mentioned that append should make sure the list to be appended is not already a sublist of anything else.

>>139
There is one other check I forgot to mention, though - that append should definitely check to make sure it's not appending something to itself in a manner that would create a loop.

>>139
Changing the tail pointer of a node should be a constant time operation, you've made it into a sometimes linear time copy thing depending on a linked list of linked list meta info.

Do you not see that?

>>140
This is even worse! Circular lists are one of the coolest things about linked lists.

>>140
O(n) (or worse cause of your retarded linked list of linked list meta info)

>>141
And what's your point? That this is unusable? Yes, it's absolutely terrible. It's a linked list. Linked lists are absolutely terrible as implementations of lists designed for general-purpose use. It's still better than an implementation that requires linear time to find the length.

>>142
How would SGLIB_LIST_LEN handle a circular list?

>>144
Linked lists are one of the most useful data structures in existence, are you kidding me?

>>143
No, not O(n) as far as I can see. You check if the list to be appended to has, as its parent, the list to be appended, or if it is the list to be appended. This is not linear because the parent pointer always links to the topmost parent. This is the only case necessary, because otherwise the ``does this have a parent?'' check would be triggered.

>>146
No. Please read my posts. They are terrible as implementations of lists designed for general-purpose use. That is the reason I reject a Θ(n) length operation, but compensate it with a O(n) (which will only reach n in rare cases) check in other methods.

If the use case is known, a tailored data structure is just fine. Sometimes that tailored data structure is a linked list.

>>148
I don't quite understand what you mean by general purpose use.

However, if you mean ``has many uses'' then I don't know of any data structure with as many uses as linked lists.

For example, it is easy to use linked lists as queues, as trees, as infinite sequences etc.

>>145
I don't know how the library you mention does it, but generally you use the tortoise hare thingo in your linear time length procedure, and return a special value when a cycle is found.

>>149
I mean the following: I give you a set of structures and/or algorithms. I then say ``This collection of structures and algorithms is a list''. You then use them as a list.

If the set of structures and/or algorithms I gave you is actually a linked list, and you used them in a sort of average-y, amortized-y manner of all uses of a list (not a linked list), unaware that the implementation is a linked list, you'll probably conclude that I have given you a pretty crappy list. Addition and deletion require individual memory allocation/deallocation calls, seeking in the list is linear, etc. I can try to make that list a little better by making changes to it while retaining the basic concept of a linked list, but it's still going to be a pretty terrible list, as you have completely picked up upon and pointed out. My claim is ``it's still going to be better than Sglist, assuming somebody is holding a gun to the author's head and demanding that he use linked list-ish things as his implementation''.

Frankly, I would say that a plain linked list is terrible as a basis for a tree as well (for one thing, how do you get a list of all children of a node without tacking on other bits that are likely to be O(n)?), and I don't want to touch the ``infinite sequences'' statement, but as a queue, they are a serviceable implementation.

>>150
For your reference, Sglib stands for ``Simple Generic Library''. It is on this basis (specifically the ``generic'' part) that I evaluate (and reject) the algorithms it offers, specifically SGLIB_LIST_LEN. When given a circular list, for example, SGLIB_LIST_LEN will enter an infinite loop, mindlessly dereferencing next->next->next->next->... pointers for eternity.

To clarify on the first point above, Sglib offers algorithms that work on any (reasonable) data structure. So what could actually happen is that I could write a skiplist structure and apply the algorithms Sglib offers. But because of the disconnect between the way Sglib is written and my data structure^*, I would see no benefit of anything I have put into my data structure. Sglib simply treats any list as a dumb linked list.

^{* Actually, this whole discussion started out as a few other people discussing macros, right? Sglib offers all of its algorithms in the form of macros. That's the gimmick.}

>>149

I don't know of any data structure with as many uses as linked lists.

To be snarky, those are all just special cases of graphs, which are really just special cases of sets. Your point is taken, however.

>>151
I think you're using ``list'' to mean ``container''. You can use it this way, but I'm not sure its very useful.

This is probably what led you to try to ``improve'' it. More accurately, it's what led me to lead you into ``improving'' it.

Moving on, a more useful definition of ``list'' is when ``list'' means ``linked list'', i.e. a concrete datastructure that comes with one set of tradeoffs with regards to the asymptotic characteristics of the algorithms which operate on it.

O(n) access and length operations are just part of what a list is. Nevertheless, lists have many many many uses where operations on them are efficient for the things which that list represents; stacks are obvious, queues require a bit of cleverness, many different types of graphs and trees. Lists also have low complexity constants (on most hardware) for many algorithms, so for small data sets they're good at things they're not good for ;) e.g. they're a more efficient representation of small sets than hash tables.

I think if you adopt this view on lists, you will not get any ideas that they need ``improvement'' because there is nothing to really improve. Lists are what they are, and you can analyze algorithms over them, and decide what to use lists for and what not to.

If you're interested in pushing lists to their limits, or getting a really deep understanding of programs, datastructures, algorithms, all these neat things, and I mean really deep satori like understanding, I recommend studying Common Lisp. You are intelligent, obviously, but not wise. Common Lisp will give you wisdom.

>>153

when ``list'' means ``linked list''

Indeed - that's precisely what I'm not doing. If I wanted to say linked list I would say linked list. Actually, I like the way Wikipedia puts it in the first definition: A list is a finite sequence {a₁, a₂, ... a_n}, where n is finite. For an infinite sequence, or something which is not exactly a sequence, a different term is needed. There is no need to specify everything in terms of linked lists - other things may be ``what they are'' as well.

To return to the original point, assuming that O(n) access and length times are required for [linked] lists, I still find Sglib disgusting - two reasons came up in the back and forth. First: that the algorithms are problematic. Equating lists and linked lists makes circular lists a completely valid case, instead of a condition that may be ignored as an error. The mapping macro completely fails to deal with this. Second: the refusal to specify structure, only algorithms, means that the algorithms are only effective for structures so trivial that they might as well have been written anyway, but are not.

>>154
Data structures represent things, the things those data structures represent are defined by sets of vocabularies (i.e. procedures) over that data structure.

The exact same data (structure) can represent a tree, a finite sequence (or list, whatever), a queue, a stack and even a computer program.

Given a vocabulary which defines a thing, when the procedures which are that vocabulary are defined over one data structure, they have different complexity characteristics than if they are defined over a different one (obviously).

Now, if you use ``list'' to mean finite sequence, then almost all data structures can represent a ``list'' (arrays, hash tables, linked lists etc.). It's useful to use ``list'' like that sometimes, but in this conversation it is clearly not, because it has caused you to make many mistakes as a programmer.

From this superior vantage point, sglib is correctly seen as a vocabulary over any type (or kind) of linked list in C. It may be a vocabulary of incredibly shoddily implemented algorithms, but what it attempts to do is give a set of procedures to use on linked lists of int, float, char, some_struct etc. which both treat them as some thing (e.g. stacks or finite sequences) or which give a foundational vocabulary for vocabularies at higher level in a stratified design.

So saying ``woah woah woah, hold on, there's no data structures in this library'' is not very intelligent. The data structure is assumed. It's a library over any datastructure which fits the bill.

Similarly: ``woah woah woah, hold on, length is O(n) here'' is especially invalid for the same reason. A length procedure is a procedure over (and partially defining) a finite sequence (what you and wikipedia call a ``list'', and in this case it may be useful to call it a ``proper list'' (as does the blessed and holy Hyperspec, praise be to the gang of five which delivered it unto us)). You can't do better than O(n) for ``length'' over linked lists. It's not possible. You can change the data structure (as you attempted) but then you've changed the data structure, and hence the implementation and characteristics of other procedures in your vocabulary over that data structure (which you also discovered).

So your problems with sglib don't seem to be with sglib, but with the very idea of using linked lists as a data structure!

Now, this is absolutely insane for many reasons, because linked lists are an excellent data structure, but it is important to know what you are actually unhappy with.

>>155
No, my problems are with the view of data as irrelevant. Let us take the example of a collection of things, of a tree, of a directed graph, of any structure of data. It is completely unacceptable to carefully organize data in a program, then completely ignore this organization of data in the procedures for the program.

You say a data structure can represent many concepts. Certainly that is true. But it is used in a program to represent exactly one thing: what it represents. This may be a finite sequence, it may be a tree of a specified order, it may be a data which is built up as a planar graph, then evaluated as a function, then treated as a number. Whatever its role is, it is important within a program, and both data structures and procedures should be written with that role in mind.

It is foolish to implement the role of an array with a linked list. The strengths of a linked list are completely unused, the weaknesses will prove irritating. It is foolish to implement the role of a constant, fixed string with a hash table. It is foolish to implement the concept of a linked list using ... take your pick of unsuitable data structure. If you try, you can come up with alternate - but close - roles for each of those examples that are well met by that which I call ``unsuitable'', but to do so you'll have to re-specify the role, and my point is that the role matters.

Just so, it is foolish to write a function that, knowing the role and implementation of the data it will handle, ignores it. Why search through an array blindly if you know it is sorted?

I know the objections you'll make, so I'll address them. Concrete data structures, created without any specific role of data in mind, are good enough most of the time. Ditto for functions. They made a language based on that concept and called it Java; it's doing quite well. Most of the time, the roles of data in a program fit very nicely to common, well known, possibly built-in data structures. I'm not denying that at all. Programmer time is also a constraint. Perhaps it takes too long to write a perfect data structure, but a known, implemented data structure comes close enough. (But linked lists are not a data structure that takes too long to write.)

What I am saying is that the following situation is idiotic:

You are writing a C program, so you don't have very many complex structures pre-written at your disposal, so you decide to write some yourself. At this point, you pick up a set of predefined algorithms that only handle very basic, very generic data structures correctly, and you write those structures yourself, and only those structures. Indeed, let's consider two cases:

1) You are writing a program where a data role maps perfectly to a linked list
2) You are writing a program where a data role maps to something that is not a linked list

In case 1, this library doesn't make sense, because it could have trivially defined the structure of the linked list it expects for you.
In case 2, this library doesn't make sense, because you don't need ``a foundational vocabulary for vocabularies at higher level in a stratified design''. You're already writing the data structures and vocabularies for all levels of design. If you want a linked list with extra parts bolted into the storage (think a skiplist), these foundational vocabularies don't handle the extra table of links and so won't work properly. If you want something that can be emulated by linked lists (perhaps a tree of some sort), there will be restrictions put on those linked lists that can't be exploited, because they aren't known about.

That is my complaint. The only way for this library to be useful is either if you have a very clean use case (in which case the library is trivially deficient), or if you are ignoring the role of your data. Data is not irrelevant. It is a programmer's job to craft structures and procedures to handle it, and there is no part of that task that this library helps.

Yes, you can implement any kind of data structure using linked lists as the base. You can also do it using arrays, sets, strings, hash maps, etc. Please stop telling me how wonderful linked lists are. I know what you can use them for, and I also know that they are not the only structure that can fill that role. I'm saying that in the only situations in which this library would be used, using linked lists like that is a bad idea.

>>156

2) You are writing a program where a data role maps to something that is not a linked list

Should be

2) You are writing a program where all data roles map to things that are not linked lists

>>156
I'm having a lot of trouble following you. Also you keep misusing the word data structure.

At this point I just want to know why you think implementing sort(float_node_t*), sort(edgel_node_t*), sort(glyph_node_t*) etc. every time you want to sort a finite sequence of somethings represented by a linked list, is a good way to spend your time when you know it can be automated?

>>158
Your question is irritatingly in the realm of absolutes. A suitable response is: ``Why would you think it's a good idea to implement only one sorting algorithm for all data structures in your program, and always use that algorithm no matter what you know about the data? To have a simple consequence, this would lead you to discount radix sort for some perfectly-formatted representation of a collection of integers just because you already have a comparison-based sort written.''

Unless you are selectively ignoring what I say, you can't believe that I write a new sorting algorithm for every collection of data my programs use. If you are selectively ignoring what I say, there's no point in any response. If you aren't, then since you're asking me about an extreme view I don't hold, we are common ground, and there is a point in my responding, to say ``okay.'' and acknowledge that. So: Okay.

>>159
I don't know what you mean by ``realm of absolutes''. I also don't understand what I am supposed to or not supposed to be ``selectively ignoring''. Please do not respond to the above two statements with an explanation.

Speaking of selectively ignoring, I clearly wrote:

every time you want to sort a finite sequence of somethings represented by a linked list

So it's mind boggling that you would then write:

Why would you think it's a good idea to implement only one sorting algorithm for all data structures in your program

I mentioned one data structure!; Generecity across data structures isn't what's being discussed.

>>160
You asked a stupid question, loaded with stupid assumptions, about wanting to do something ``every'' time. I responded with another stupid question about doing something ``always'', ``no matter what'', etc, also making a stupid assumption (that you want to use one structure/function for everything). This is what I meant by ``A suitable response''. A dumb question for a dumb question.

I intended for you to read my rhetorical question and think ``Why yes, my question was a silly mischaracterization of his argument''. At that point you would realize that we are not actually arguing over anything - you just think I have a bias against linked lists, and I just dislike implementing data structures without taking into account how they will be used. Unfortunately, I seem to have overestimated you, and so your mind boggled instead of getting the point.

For crying out loud, let this discussion drop. Neither of us is saying anything interesting or remotely controversial, and the only reason I'm bothering to reply is that every time you post you make errors misrepresenting my position.

>>161
O.K.

You just seem so very confused and I want you to be enlightened.

But I'll let it drop.

I like them. My code comes off prettier. I use them like this


function broadcast(name,data,conn){
if (!data) data={};
data.type = name;
conns.forEach(function (conn2) { if(conn2!=conn) conn2.send(data); });
}

shavajit.

http://bellard.org/ - another talented programmer

Then complain about MUH PERFORMAMCE and GEEEECEEE, while using linked lists all the way down.

The 5 newest replies are shown below.
Read this thread from the beginning.
>>161
I just realized I think this can be searched through easily, but imagine there were every more links that looked circular.
>>161
It's definitely a graph.
just base everything off the standard units? every unit has a base unit.

The title and content of this thread aren't exactly the best for this purpose.
irc is for faggots and queers.
>>14
also niggers
>>13
Aaron Swartz would probably be happy to seem people doing the types of things that /prog/lytes do. I say we just fill this thread with /prog/y things.

SPECIFICATION

Oh, but I have!

so to convert mm to nautical mile you first find out how many mm to a meter (the std unit) and then convert meter to mile.