Hacker News new | comments | show | ask | jobs | submit login
Programming and thinking the functional way (peteratt.com)
66 points by peteratt on May 7, 2014 | hide | past | web | favorite | 80 comments



I still remember the first time I started to grok recursive definitions in a functional language. At the time it was Scheme and I remember going through all the effort to track the various bits of state and operation as they "reboot" and begin again in each recursive call.

It made me think that recursion, no matter how short the code looked, was terrible.

Now I realize that recursion, thought about properly, requires so much less mental overhead. All those lines of code that vanished were really whole concepts and ideas which could vanish as well.

Of late, my style has been refined by working with theorem provers which make the ultimate connection. Recursion is absolutely nothing more than mathematical induction. Each recursive call is just you invoking the inductive hypothesis.

What that connection really drives home is that when writing a recursive definition you need to do so very few things. First, you need to make sure your definition has a good foundation—you must list all of the conditions where it terminates and ensure that they truly found and support the algorithm/proof. Then you must write the inductive engine that will burn away whatever inputs you receive down to the foundation you just made.

The release is in noticing that those inductive engines can be primed on the very tiniest actions—and those tiny actions are all you, the implementer, are responsible for.

When writing your inductive step consider only the things that are novel about this case. If I'm working with an input list and inducting on `cons` then all I must do is consider what happens to the head and tail of the list. Everything else will be handled by the turning of the inductive engine.

Now a good algorithm just feels like someone walked me into a room with a gigantic domino structure. I walk around it slowly and determine the ends and then just flick the single domino which will churn away inevitably the rest of the algorithm.


Interesting! I had the exact same experience where recursion really clicked -- proof by induction === recursion. Obviously (in hindsight)! :)

And, by extension, structural induction === sum & product types + pattern matching destructuring for recursive functions. The fact that the type checker can make sure you've got your base cases covered is just gravy.


Although I think loops and recursion aren't so different: here's a snippet from meijer:

"The goal of recursion and loops is exactly the same, you want to define something in terms of itself.

That's what the loop does; it repeats a computation and something gets smaller...

the loop variable or when you for each over a loop you're picking out the next element..

That's exactly what a recursive definition tries to do, you're trying to define a function, in terms of a smaller version of it's argument."

http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Func...


Loops are generally special cases of recursion. You can always derive an iterator from a recursor by forgetting things, but you need product types or ambient state to go the opposite way.

In Turing complete languages they're both special cases of fixed-point equations, though, so in that sense they both have the same goal.


Another practical functional language is Erlang.

It is at the core of many mobile to internet gateways out there. At the core of WhatsApp. Some databases (Riak, CouchDB) and message queues (RabbitMQ).

Language-wise, besides concurrency constructs, you get pattern matching, immutable data structures (and bindings). Unlike Haskell, all types are dynamic (but strong).

Also a counterpart to Learn You A Haskell For Great Good is Learn You Some Erlang For Great Good:

http://learnyousomeerlang.com/syntax-in-functions#pattern-ma...

For example the quicksort sample would look like:

    sort([Pivot|T]) ->
      sort([ X || X <- T, X < Pivot]) ++
      [Pivot] ++
      sort([ X || X <- T, X >= Pivot]);

    sort([]) -> [].


But it is the large applications that ends up breaking my brain. I am convinced once you learn programming in an imperative or object oriented language you brain just become molded to that model of thinking and it is very hard to adjust (it is nevertheless very useful to try).


I had to audit a web app and the back end code was all written in Erlang. I had never seen the language in use before, so it took me a little while to get the hang of reading it.

Now that I've spent some time playing around with it, I think I like Erlang better than I like Haskell; I used to think I disliked dynamic typing but it turns out I just don't like the way Ruby handles it. Erlang feels really good to write code in, and it feels a bit less finicky than Haskell is.

If anybody wants to try functional programming and feels like they just can't get along with Haskell, I'd definitely recommend you give Erlang a try. It's not great at everything but I'd highly recommend it as something to try.


There's no accounting for taste, but as "jerf" posted in a sibling comment Erlang's not really functional[0]. All that's really happening is that the mutable state is "hiding" in the message passing portion of the application. Just as an example: It's pretty simple to implement a mutable reference cell as an actor which contains only pure functional code. I'm not sure where I first saw it demonstrated, I think it was one of Erik Meijer's talks/videos.

[0] I mean in the "no/minimal mutable state" sense.

EDIT: Removed potentially confusing aside.

EDIT#2: I guess I should elaborate: The idea is that you just have the MutableRef actor accept two messages: Set(X), Get(X). The basic idea was to just have the actor continually send itself Set(X) messages with the current value -- thus exploiting the messaging to keep mutable state.


Of what use is this distinction, especially when zero languages fall within its definition? Honestly.


Hm? Haskell is purely functional. (Alright, you can theoretically use unsafeCoerce and unsafePerformIO, but in practice it doesn't actually happen.)


Can you please point me to any real-world Haskell program that is purely functional? I am interested in seeing what a program without I/O looks like.


All of them. Remember that "IO a" is just a value. :)

It's really the "interpreter" of the IO monadic values which causes all the side effects. I am aware that there are some issues with this interpretation, but if you want to get pragmatic it's really a question of X% pure/(100-X)% impure while keeping X as close to 100% as possible. Haskell can do that for X arbitrarily close to 100% (depending on how much abstraction/effort you're willing to go through).


"But it is the large applications that ends up breaking my brain."

Really? Large Erlang applications can be understood as a collection of objects that happen to be running concurrently, and I explicitly mean that OO intuitions about responsibility, identity, and substitutability can be fairly directly used. In that sense, I don't think Erlang is actually a very functional language in practice. Erlang programs tend to look like one's initial, high-level overview of a how an OO program will look when you first draw a sketch, with each circle in the diagram becoming a process (or more accurately, type of process, e.g., a "connection" process that may be instantiated once per connection).


Plus all that wonderful OTP goodness giving you the "right" structure to your concurrent objects.


It boils down to the choice between these two alternatives:

1) If it's simple to imagine the computer doing something, it should be easy to program.

2) If it's simple to analyze something mathematically, it should be easy to program.

The first path leads to C-style programming with pointers and loops. The second path leads to lazy pure functional programming and beyond.

Personally, I'm in the first camp. Small functional programs are often shorter and more beautiful than their imperative and OO counterparts, but large functional programs quickly accumulate so many abstractions that they become incomprehensible to me, more so than large imperative or OO programs.

Maybe that just says something about my intelligence, or maybe the functional camp hasn't yet figured out how to write large programs in a readable way. Case in point, see the list of operators defined by the popular Lens library in Haskell: http://hackage.haskell.org/package/lens-3.8.5/docs/Control-L...


Maybe that just says something about my intelligence, or maybe the functional camp hasn't yet figured out how to write large programs in a readable way.

Haskell programmers tend not to write large programs, period. Instead, we build lots of libraries until our problem is trivial to solve.

Case in point, see the list of operators defined by the popular Lens library

Not really a fair example. Lens is not a program (large or otherwise), it is a new programming language embedded within Haskell. Viewed within that context, its bevy of operators is somewhat justified. The other thing to note about it is that lens was designed specifically to avoid clashing with variable and operator names defined in other popular libraries so that users could import it unqualified.


> Haskell programmers tend not to write large programs, period. Instead, we build lots of libraries until our problem is trivial to solve.

So, how is that different from any other language since the invention of functional/procedural decomposition? Programmers generally write libraries and then compose them, rather than writing large monolithic programs, irrespective of language.


I think he's saying that Haskell programmers do this more than other programmers. I agree.


> Haskell programmers tend not to write large programs, period. Instead, we build lots of libraries until our problem is trivial to solve.

But if the libraries that you write, taken together, are large, then you are in fact writing a large program. Calling part of it "libraries" doesn't change that. (So far as I can see, that's no different than a C programmer writing lower-level functions, or an assembly language programmer writing subroutines. Everybody does that - at least, everybody sane.)


I wanted to avoid getting into a discussion about the merits of Haskell vs other languages. I was merely making a statement about what I perceive is the common practice of Haskell programmers. Do I believe that Haskell as a language provides features which allow for greater modularity, reusability, composability and generality than most other languages? Yes. However, to explain it all in great detail would take far too long. Besides that, others have already laid much of the groundwork for explaining these advantages in a much better format than I can muster here. Here's one simple example (which happens to describe the advantages of laziness):

http://augustss.blogspot.ca/2011/05/more-points-for-lazy-eva...


> Maybe that just says something about my intelligence, or maybe the functional camp hasn't yet figured out how to write large programs in a readable way.

You make it sound like we've figured out how to write imperative large programs in a readable way.


Well, it's not too bad. I work at Google and spend a significant part of every workday reading other people's code, written in imperative/OO languages. That's not too difficult, if the code uses few abstractions and if you have good tools for reading it, like cross-referencing, version control history and code review history. But the "few abstractions" part is actually important, I can't imagine reading typical Haskell code at the same speed. When you're tracking down a bug or trying to implement a feature that touches several projects, you really need to read fast.


It really comes down to who's code you are reading.


Lens is one guy's pathological abstraction. It's a library, and it's idiosyncratic. It isn't want large Haskell systems "look like".

Cf http://ro-che.info/articles/2014-04-24-lens-unidiomatic.html


I agree that Lens is extreme, that's why I picked it as an example. However, most Haskell code I've seen also has line-noise problems, though not as extreme as Lens. Maybe I just haven't been lucky. Can you point to some good examples of readable Haskell code?


If you work with Java/C/C++ then the way you structure, compose, and think about programs is mostly entirely different from Haskell. Any of the examples I might point to as idiomatic Haskell are going to be "unreadable" ( if that words means anything ) within that worldview, because they come with an entirely different set of constraints and culture than the Java/C++ world.


It would still be nice if you (or somebody else) pointed at those examples. That would open new avenues for learning and communication.


What kind of examples are you interested in?


The most-unreadable Haskell code I've found is from Matrix.Simplex (https://hackage.haskell.org/package/dsp-0.2.2/docs/src/Matri...) :

    addart a = array ((-1,0),(n,m+n)) $ z ++ xsi ++ b ++ art ++ x
        where z = ((-1,0), a!(0,0)) : [ ((-1,j),0) | j <- [1..n] ] ++ [ ((-1,j+n),a!(0,j)) | j <- [1..m] ]
              xsi = ((0,0), -colsum a 0) : [ ((0,j),0) | j <- [1..n] ] ++ [ ((0,j+n), -colsum a j) | j <- [1..m] ]
              b = [ ((i,0), a!(i,0)) | i <- [1..n] ]
              art = [ ((i,j), if i == j then 1 else 0) | i <- [1..n], j <- [1..n] ]
              x = [ ((i,j+n), a!(i,j)) | i <- [1..n], j <- [1..m] ]
              ((_,_),(n,m)) = bounds a
One letter variable names, argh!


reminds me of algos in matlab


Eh, the list of operators is a weird artifact of the design of lens. The fundamental abstractions at the core are fairly simple, although they're exposed in a scary way.

Most of that has to do with optimizing for reuse and proper type inference. It's a cheat to expose the Haskell subtyping relation for more leverage.

A better way to understand lenses should be to consider a package like lens-family-core which keeps to its roots.


Scala had/has an issue with user-defined operators; there was a proposal that all operators should also be able to be called with an english word i.e. provide a named function.

I wouldn't mind if haskell library designers took that practice to heart.


To that end, the lens library exposes named verbs for most of the core operators and both the verbs and operators are chosen with great discretion toward consistency... if not great discretion toward not clobbering related libraries.


Is anyone not freaked out by Lens? Really, that "thing" is scarry... you realize you need something like `^.` from it because it can make life easier, but then you look at the whole jungle of what it really is and your mind explodes.


(^.) is a really simple function actually, I'd argue it's even simpler than fmap. If we look at `lens-family-core` all the machinery to derive everything you need to make lenses is very concise and would fit on a index card.

http://hackage.haskell.org/package/lens-family-core-1.0.0/do...


Writing quicksort non-functionally doesn't HAVE to be unreadable. Not that I disagree with Haskell being great and all, I just think it's important to realize that imperative != ugly code.

  public class QS {
  	public List<T> Quicksort<T>(List<T> l, Comparator<T> comp) {
  		if (l.size() <= 1) {
  			return l;
  		}
  		
  		List<T> lesser = new ArrayList<T>();
  		List<T> greater = new ArrayList<T>();
  		
  		T pivot = l.get(0);
  		
  		for (T t: l) {
  			if (comp.compare(pivot, t) <= 0) {
  				lesser.add(t);
  			} else {
  				greater.add(t);
  			}
  		}
  		
  		List<T> out = new ArrayList<T>();
  		out.addAll(Quicksort(lesser));
  		out.addAll(Quicksort(greater));
  		
  		return out;
  	}
  }


This will recurse forever when sorting the list [1,0]. Which is why you need to take out the pivot to ensure that the lists you recurse on get smaller and smaller...


[deleted]


I think you just described programming.


Agree. Should rephrase it: by having higher-level abstractions and decoupling state from logic functional languages make it harder to make mistakes and write bad code. At least that's what I've discovered when applying its "way of thinking" to my own work.


"Wow. i's and j's all the way, what is this? Why is it so long compared to the Haskell example? This looks like comparing C and assembly 30 years ago! And in some respects, it is the same leap."

I don't think this is a fair comment considering the in-place Haskell implementation isn't incredibly readable either.


Agreed. I think his overall argument still has merit, but the specific example isn't very good, because Java's quicksort implementation is in-place. He isn't comparing equivalent programs.


The criticism seems especially misplaced because of how fond Haskell coders are of one-letter names for values...


I'm not sure if I'm the first to notice, but the Haskell quicksort function is wrong, because it mishandles NaN:

    main = let nan = 0.0 / 0.0 in
            do putStrLn $ show $ quicksort [nan, 1.0, 2.0, 3.0]
               putStrLn $ show $ quicksort [1.0, nan]


    [NaN]
    [1.0]
Sort routines should not return a list of a different length than their input.


Elegance tends to be grinded away when the rubber meets the road.


So a divide-and-conquer algorithm on collections is more elegant functionally than imperatively? Also: water found wet.

Haskell is elegant & Java isn't, but cherry picking examples always comes with a risk of making your argumentation straw-man-ish.

Would be interesting to see some examples where imperative isn't so horrible, and how Haskell compares. The in-place sort the author mentions, for example.


So a divide-and-conquer algorithm on collections is more elegant functionally than imperatively? Also: water found wet.

Even that is only true if you consider the concise and readable nature of the Haskell code to be the most important factor in the elegance of the algorithm.

To me, the elegance of true quicksort is that its in-place nature is memory efficient, and consequently also cache-friendly on modern hardware, resulting in excellent real world performance.

If you consider the underlying nature of the algorithm to be more important to its elegance than superficial presentation details, then the typical 3-line functional implementation is clumsy by comparison, and equating the two is at best an appeal to having a sufficiently smart compiler.

In reality, of course, both the aesthetics and the underlying behaviour matter, so I'm not sure it's particularly helpful to promote any language as being superior on either basis without also considering or at least acknowledging the other.


The Java example builds up a straw man. Never underestimate your readers!


This might be the first time I've seen someone accused of misrepresenting himself.

Actually this programmer is me, right now at the moment of the writing.


Why is it a straw man? It looks reasonable to me and I'm a Java programmer.


For one thing, the Haskell version is a non-inplace inefficient HelloWorld kind of qsort. For another, the Java version is rigged to add more unnecessary fluff.


The Haskell version isn't in-place and therefore not really quicksort, agreed, but that's a separate (though valid) criticism. It doesn't make a "straw man" of the Java version, does it? It would be a straw man if it said "here, look at a reasonable quicksort implementation in Java (absurd, bloated code follows)".

The Java version doesn't really have a lot of unnecessary fluff. What, it's not a static method and has instance variables? So what? That doesn't add a lot of verbosity and is NOT the crux of the author's argument either.


The author was doing a section by section comparison of the two - Look! There's no Haskell needed for the corresponding Java code! He is deliberately showing verbosity in Java with an apple-to-orange strawman comparison. What else is he trying to show?

The instance variable in class is an important strawman the author added to Java. He's trying to show the need of "state" in Java, which is not needed in a sensible Java version of qsort, as all data can be passed in parameters.

He also made the statement that the instance variable is needed for recursion in Java (!) to "substantiate" (make up) the excuse for using instance variable in Java.

And yes, those are called strawman.


Ah, yes, I didn't catch that he explicitly mentions state in the Java program, as part of the comparison. That is indeed a straw man.


Ah, the ole "quicksort in 3 lines" argument. There are a few things I take from this.

The good:

1) The definition of the algorithm is clear. It shows "how quicksort works."

2) It's trivial to see (and prove) that the function will terminate, and almost as trivial to prove that it will result in a sorted list. So, it is easy to show correctness.

3) The polymorphism makes this an easily reusable function right out of the box.

The bad:

1) That implementation is very inefficient. At a glance I think it would be O(n^2) time. (Edit: this is misleading, because it's only O(n^2) in the same way that quicksort is always O(n^2). It is inefficient in terms of memory usage, though. And possibly other ways; for instance, I'm not sure how laziness would affect this. But I don't want to be spreading FUD...)

2) The "efficient" implementation given at the bottom is just as inscrutable as any other quicksort implementation I've seen. More so because of the monadic code, single-letter variables (pr?) and opaque library function calls (unsafePartition?) being made. And I'm not even sure that it would work on a list, although since V.Vector appears to be a type class, perhaps list is an instance of it.

3) Both the efficient and inefficient implementations are concise in large part because of their use of library functions. This is often a good thing: Haskell provides a great way to abstract things because of its parametric and ad-hoc polymorphism, and allows for a lot of reusable code. But it comes at a cost too, which is that the actual instructions you're giving to the machine are very far removed from what the computer is doing. Who knows how much code is actually executed, how deep the rabbit hole goes, to translate those beautiful 4 lines into actual machine instructions? With Java, it's precisely visible what the machine is doing to execute your code. This is much less the case with Haskell.

I suppose you could say (broadly) that functional languages excel at expressing what your program should do, while imperative languages excel at expressing how your program should do it. There are cases when you care more about the former, and cases when you care more about the latter. The reason I take issue with the quicksort example, is that list-sorting is a case where you definitely care more about the how than the what.

-------------------

EDIT, since two people called me out on it: It was an overstatement on my part to say that it's "precisely visible" what your Java code will translate to, but to suggest the two languages have the same degree of abstraction from the CPU is ridiculous. The code translation from Java to bytecode is quite straightforward, because most of the optimization occurs at runtime with JIT. There is a reasonably direct relationship between the code you write, the bytecode it gets translated into, and the instructions executed at runtime. At the end of the day, Java code consists of a series of instructions for the computer to follow, while on the other hand in Haskell, you aren't even technically giving instructions at all -- you're just writing equations. Compiled Haskell code is completely inscrutable.

Also, I should note that I am an enthusiastic Haskell hobbyist, and write it on almost a daily basis. Although I might not come across it here, I am a huge fan of the language; outside of the languages I use at work, by far the one I use most is haskell.


> the actual instructions you're giving to the machine are very far removed from what the computer is doing. Who knows how much code is actually executed, how deep the rabbit hole goes...

The same criticism can apply to Java. But it's not a particularly good criticism. Unless you're interested in quantum physics, you really don't want to know what the machine is "really doing". You want to have useful abstractions that you can rely on.

The rabbit hole goes very deep indeed, and a lot of concepts that programmers treat as concrete are themselves abstractions that hide a lot of complexity.

The difference in level of abstraction between Java and Haskell is much smaller than the difference from either of them to what the actual machine is doing. In both cases you have a compiler, a language runtime, an OS & kernel, and processor microcode in between you and "the metal". Actually Java has one extra step, because javac emits bytecode that needs to run in the JVM, whereas ghc emits binaries that can be run directly by the operating system.

(Your comment about O(n^2) in time is beside the point -- quicksort is always worst case O(n^2), so it wouldn't be quicksort otherwise. All the implementations we're talking about have that same asymptotic behavior. The problem with the naive Haskell implementation isn't the big-O time, it's the big-O memory, which went from O(1) to more like O(n log n).)


quicksort is never O(1) memory but O(log N). On a flip note: Java's JITs are very mature to the point one may know what exactly the generated assembly would be (and display it as well -XX:+PrintAssembly)


Lists in haskell are lazy linked lists. Vector is a library that provides mutable allocated vectors a la Java's Vector. To use it with lists you would have to do (note the period is composition):

listQsort :: Ord a => [a] -> [a] listQsort = V.toList . qsort . V.fromList

Also: > With Java, it's precisely visible what the machine is doing to execute your code. This is much less the case with Haskell.

This is very much a false statement. Java code runs through the JVM and its memory bloat, whereas haskell is compiled to native code along with its runtime. Both involve significant abstractions away from the actual machine instructions. It is more accurate to say that Java makes you think you can see what the machine is doing, but it is also far removed from machine code. One advantage is that with haskell, the compiler can reason about your side-effect-free code and optimize much more than java code.


Your last line refutes your refutation! If Haskell really can "optimize much more," then it's harder to know from code inspection what the program will actually do at runtime. And if you don't know why your program is fast, then you can't know how to keep it fast. Does this seemingly innocuous change defeat an optimization? Hard to say.


The 3-liner qsort is kind of the marketing to lure in the newbies into the language. It becomes a problem when people start to believe the marketing as the real thing. People doing this kind of apple to orange comparison do a disservice to Haskell.


It's worth noting that the reason behind pure functional programming is that ideally lets you reason about your business concerns without needing to worry so much about these things.

The expectation is that pure functional languages gain a lot of benefits from (for instance) referential transparency which allow for optimizations which can not be provided by the compiler in languages which don't provide the same benefits to developers.

It's also true that this is potentially just theoretical. Sure, there's no way to ensure these optimizations exist given your compiler's implementation, but the article actually does mention that this has other issues and it's only for demonstrative purposes.

So, chances are it's a non-issue and if it is an issue then you still have the power to solve the problem later. No need for premature optimization, right?


Not sure how you find this as O(n^2). It's clearly the divide and conquer version with O(n lg n) expected time. The only asymptotic complexity issue of the algorithm is that it doesn't randomly pick p, so it will get O(n^2) perf on an already sorted list. It would be expected that you randomly shuffle a list before using this quicksort alg. When the author says this is not the true quicksort, he's referring to the fact that it needs O(n) auxiliary memory, because it's not swapping values in place (the real cost here is worse caching performance). It's definitely not an O(n^2) algorithm though.


from the "good", 1) and 2) can be helpful before you start working on an efficient implementation.

Basically, bang out a slow but obviously correct implementation, and then iterate to convert it to be efficient, perhaps using things like 'equational reasoning'. However I haven't much experience with this technique yet...

I believe this is the technique used in Pearls of Functional Algorithm Design by Richard Bird (I have yet to read it)


Question is: starting in the idiomatic Haskell implementation that you discover is too slow, what is the next step? How does one iteratively go from that to a slightly faster one, to an even faster one?

You don't, because it's near impossible. In Haskell you have defined quicksort, not instructed your computer how to do it. That's the reason it's beautiful, but also the reason it's hard to iteratively refine your soluion. There is basically only one definition of quicksort: your program, and you can't iteratively "refine the definition"

You can try to make it in-place in Haskell but there is no clear transition from your initial version to the in-place version.

The in-place haskell one looks something like this (and that java code shows no sign of envy now). Answer: like this http://stackoverflow.com/questions/5268156/how-do-you-do-an-...

This is my main problem with functional programming: it makes it very easy to go 90% of the way in a very elegant matter. Once you hit that brick wall though, you come to a point where you'd cut an arm off for a mutable array.

Perhaps the solution isn't to write horrible Haskell but rather either use a less strict functional language OR outsource that 10% of the code to an imperative language, rather than making contrived, complicated code like the in-place Haskell quicksort?


The problem that you are describing occurs when you are trying to optimize a piece of idiomatic functional code that you have already written. Perhaps the solution could be to keep the code you have already written, and write a low-level, highly-optimized replacement alongside it, then have the compiler verify that the low-level code is provably identical in its output to the original function. If the code passes this test, then it is replaced with the optimized version. If you change either piece of code, and they do not match each other, then your code will not compile.


I mentioned Pearls of Functional Algorithm Design because it exactly describes how to do this. It may not lead to a solution in the ST monad, but it does tell you to to iterate to a better solution.

This post explains what I'm talking about: http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...


Sounds like a good read, sold!


I'm kind of on the fence about it - I've hesitated buying it because the post also explains that it's a notoriously difficult book - some of the results of the "swizzling" can lead to some inscrutable final programs.

But I'll probably pick it up at some point in the near future.


> it's a notoriously difficult book

Personally I don't find that to be true, it's perfectly logical mostly. It's definitely worth picking up imho.


A large reason why the naive, imperative quick sort performs well in practice is that it takes advantage of memory locality but the Haskell one doesn't.


After rewriting Collections.sort() just for the fun of it, the claim that "an hour of a developer's time is a lot more expensive than an hour of a high-performance AWS super-duper-cluster instance" isn't all that convincing. If you're going to rewrite sort at all, you should take time to do it right, and the Stream-based version isn't it.


The present version of Collections.sort is actually a Timsort[1] for non-primitives. [1]:http://bugs.python.org/file4451/timsort.txt


Creating an entire class for the Java version is kind of a disingenuous comparison.


Why? In Java you must place your code within a class, and it's not like in this case it adds a lot of verbosity or overhead. I don't think the author's main argument was classes vs no classes. Java's verbosity is caused by something else...


You don't have to pass the arguments through the class's member variables.


Yeah. qsort should be a static function - it should use the class only for scoping, not for holding data.


That's a really minor issue, and to me it's disingenuous to imply it makes a difference for the comparison at hand.

Would it really change the argument if the Java code used a static method and passed all variables as arguments, instead of using instance members?


Yes, it would make a big difference and make one of his central claims go away - stateful requirement for qsort in Java.


You're right, as I replied to you elsewhere. I had missed that the author made the "stateful" argument, and I focused on verbosity and things like i and j instead.


Hi, was wondering if functional language and Java peeps can speak to the performance Java 8's stream(...); curious if the performance of using lambda expressions hold up against say using the old for loops and also whether they do any caching or build internal lookup tables when you do anyMatch(...) or something similar on a subfield of a object.

Also for any C# peeps who already have had experiences using lambda expressions on the awesome .net platform. How was performance there?


No need to switch to an alien language, just opt for C#/F# for a nice middle ground:

http://fsharpforfunandprofit.com/posts/fvsc-quicksort


Yes, I know this is not a "true", in-place quicksort. But those are performance considerations that I don't intend to expose here.

Beware, beware.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: