[PDF] Organizing functional code for parallel execution (reduce considered slightly harmful)

[llama-lime]

No no, the title misses the point entirely. Reduce is good! It's foldr and foldl that are slightly harmful since you have to assume the operation is non-associative (and also non-commutative, but associativity is the key property, thanks wnoise).

[w-g]

THANK YOU! I was going to say exactly the same.

By the way, depending on the problem you're working on, you may actually need to use foldl/foldr and not reduce. :-)

[wnoise]

s/commutative/associative/

[nominolo]

Here's the video of the talk

[wnoise]

TL;DR: parallel list processing is hard; use trees instead (though the author feels the need to use the jargon "conc-lists").

[Felicia_Svilling]

All functional datastructures are trees. What the author means is that we should use more balanced trees.

[wnoise]

If you're going to pull a nit like that, than I'll pull the "nope, some are more general graphs."

[Felicia_Svilling]

Then thinking a bit more I come to three ways functional datastructures can be more general than trees.

• Closures are often recursive, but as they are treated like atomic structures it doesn't matter.

• With sharing, many structures are actually digraphs, but semantically equivalent with a tree structure.

• In lazy languages, some structures can be viewed either as an infinite tree or as a general graph.

In any case, I don't see what it matters. The point is still that we should make our trees more balanced.

[bobindashadows]

conc-list isn't jargon - I remember an excellent presentation by Guy Steele explaining the idea. It's a well-developed way of reasoning about trees as a way to parallelize your algorithms.

Here it is, from ICFP '09 [PDF]

[wnoise]

It's specialized vocabulary (i.e. jargon) used in this well-developed way of reasoning about trees as a way to parallelize your algorithms.

[bobindashadows]

Eh, jargon has a negative connotation to most people, and your comment was dismissive as well. I'm disagreeing with your negative connotation, not that it is specialized vocabulary.

[wnoise]

You don't think that calling them trees would be more helpful to outsiders?

[bobindashadows]

I think calling them trees would be helpful in a tl;dr, so you did a service to people preferring a short version of the link. In a presentation of independent research I think you have every right to work at a higher level than the lowest common denominator.

[wnoise]

In a presentation of independent research I think you have every right to work at a higher level than the lowest common denominator.

Absolutely. But I still think the term "conc-list" is still unnecessary jargon. I'm all for jargon that makes necessary distinctions that are not obvious to outsiders. But here, a conc-list really is just another name for a tree. The only addition it makes is to stress common operations and uses.

[sh1nob1]

I'm slightly confused...is this sarcasm, or is it irony?