News for hackers. Stuff that matters.
Re:Functional Languages 101: What’s All the Fuss About? by reycharles on Saturday May 05, 2012 @05:49AM (#3931780)
You should read the introduction to Chris Okasaki's "Purely Functional Data Structures". It says there may be higher lower bounds for some problems in functional programming languages, although it's often possible to come up with something that is as fast. I interpret that as it can require a lot of ingenuity to come up with efficient data structures in functional programming languages.

It's not harder to reason about time complexity with strict evaluation. I think it's a bit harder with lazy evaluation, though. Okasaki uses both strict and lazy evaluation to achieve fast data structures.

Re:Functional Languages 101: What’s All the Fuss About? by pohl on Saturday May 05, 2012 @05:30PM (#3933343)
Thank you for the pointer! I grabbed this pdf, and (by random chance) my eyes fell upon this somewhat-related gem (on page 129):

"Ironically, pattern matching — one of the most popular features in functional programming languages — is also one of the biggest obstacles to the widespread use of efficient functional data structures. The problem is that pattern matching can only be performed on data structures whose representation is known, yet the basic software-engineering principle of abstraction tells us that the representation of non-trivial data structures should be hidden. The seductive allure of pattern matching leads many functional programmers to abandon sophisticated data structures in favor of simple, known representations such as lists, even when doing so causes an otherwise linear algorithm to explode to quadratic or even exponential time."

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Re:Functional Languages 101: What’s All the Fuss About? by pohl on Monday May 14, 2012 @02:13PM (#3972350)
A copy of Okasaki's book arrived last night. This is exactly what I needed. Thank you again.