7 ms·

Programming and thinking the functional way

66 points by peteratt 12y ago

rdtsc 12y ago
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-matching 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).
- jerf 12y ago
  "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).
  - tel 12y ago
    Plus all that wonderful OTP goodness giving you the "right" structure to your concurrent objects.
- CocaKoala 12y ago
  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.
  - lomnakkus 12y ago
    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.
    - felixgallo 12y ago
      Of what use is this distinction, especially when zero languages fall within its definition? Honestly.
      - lomnakkus 12y ago
        Hm? Haskell is purely functional. (Alright, you can theoretically use unsafeCoerce and unsafePerformIO, but in practice it doesn't actually happen.)
tel 12y ago
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.
- lomnakkus 12y ago
  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.
  - platz 12y ago
    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-Functional-Programming-Fundamentals/C9-Lectures-Dr-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-6-of-13 http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Func...
keeg 12y ago
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; } }
- deleted 12y ago
  [deleted]
  - senorprogrammer 12y ago
    I think you just described programming.
    - peteratt 12y ago
      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.
- tromp 12y ago
  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...
ExpiredLink 12y ago
The Java example builds up a straw man. Never underestimate your readers!
- the_af 12y ago
  Why is it a straw man? It looks reasonable to me and I'm a Java programmer.
  - ww520 12y ago
    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_af 12y ago
      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.
      - ww520 12y ago
        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.
eoconnell 12y ago
"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.
- the_af 12y ago
  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.
- AnimalMuppet 12y ago
  The criticism seems especially misplaced because of how fond Haskell coders are of one-letter names for values...
skybrian 12y ago
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.
- xxs 12y ago
  The present version of Collections.sort is actually a Timsort[1] for non-primitives. [1]:http://bugs.python.org/file4451/timsort.txt http://bugs.python.org/file4451/timsort.txt
cousin_it 12y ago
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-Lens-Operators.html http://hackage.haskell.org/package/lens-3.8.5/docs/Control-L...
- deleted 12y ago
  [deleted]
- tel 12y ago
  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.
  - platz 12y ago
    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.
    - tel 12y ago
      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.
elwell 12y ago
Creating an entire class for the Java version is kind of a disingenuous comparison.
- the_af 12y ago
  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...
  - Rusky 12y ago
    You don't have to pass the arguments through the class's member variables.
    - AnimalMuppet 12y ago
      Yeah. qsort should be a static function - it should use the class only for scoping, not for holding data.
    - the_af 12y ago
      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?
      - ww520 12y ago
        Yes, it would make a big difference and make one of his central claims go away - stateful requirement for qsort in Java.
        the_af 12y ago
        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.
thinkpad20 12y ago
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.
noname123 12y ago
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?
alkonaut 12y ago
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.
- Silhouette 12y ago
  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.
ridiculous_fish 12y ago
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.
- ww520 12y ago
  Elegance tends to be grinded away when the rubber meets the road.
_random_ 12y ago
No need to switch to an alien language, just opt for C#/F# for a nice middle ground: http://fsharpforfunandprofit.com/posts/fvsc-quicksort http://fsharpforfunandprofit.com/posts/fvsc-quicksort
badman_ting 12y ago
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.

66 points by peteratt 12y ago

rdtsc 12y ago

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-matching 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).

jerf 12y ago
"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).
- tel 12y ago
  Plus all that wonderful OTP goodness giving you the "right" structure to your concurrent objects.
CocaKoala 12y ago
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.
- lomnakkus 12y ago
  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.
  - felixgallo 12y ago
    Of what use is this distinction, especially when zero languages fall within its definition? Honestly.
    - lomnakkus 12y ago
      Hm? Haskell is purely functional. (Alright, you can theoretically use unsafeCoerce and unsafePerformIO, but in practice it doesn't actually happen.)

tel 12y ago

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.

lomnakkus 12y ago
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.
- platz 12y ago
  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-Functional-Programming-Fundamentals/C9-Lectures-Dr-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-6-of-13 http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Func...

keeg 12y ago

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; } }

deleted 12y ago
[deleted]
- senorprogrammer 12y ago
  I think you just described programming.
  - peteratt 12y ago
    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.
tromp 12y ago
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...

ExpiredLink 12y ago

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

the_af 12y ago
Why is it a straw man? It looks reasonable to me and I'm a Java programmer.
- ww520 12y ago
  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_af 12y ago
    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.
    - ww520 12y ago
      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.

eoconnell 12y ago

"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.

the_af 12y ago
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.
AnimalMuppet 12y ago
The criticism seems especially misplaced because of how fond Haskell coders are of one-letter names for values...

skybrian 12y ago

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.

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

cousin_it 12y ago

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-Lens-Operators.html http://hackage.haskell.org/package/lens-3.8.5/docs/Control-L...

deleted 12y ago
[deleted]
tel 12y ago
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.
- platz 12y ago
  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.
  - tel 12y ago
    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.

elwell 12y ago

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

the_af 12y ago
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...
- Rusky 12y ago
  You don't have to pass the arguments through the class's member variables.
  - AnimalMuppet 12y ago
    Yeah. qsort should be a static function - it should use the class only for scoping, not for holding data.
  - the_af 12y ago
    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?
    - ww520 12y ago
      Yes, it would make a big difference and make one of his central claims go away - stateful requirement for qsort in Java.
      - the_af 12y ago
        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.

thinkpad20 12y ago

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.

noname123 12y ago

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?

alkonaut 12y ago

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.

Silhouette 12y ago
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.

ridiculous_fish 12y ago

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.

ww520 12y ago
Elegance tends to be grinded away when the rubber meets the road.

_random_ 12y ago

No need to switch to an alien language, just opt for C#/F# for a nice middle ground: http://fsharpforfunandprofit.com/posts/fvsc-quicksort http://fsharpforfunandprofit.com/posts/fvsc-quicksort

badman_ting 12y ago

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.