Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programming and thinking the functional way

peteratt.com

Post reply on HN
Print view View original

71–80 of 86 posts

Re: Programming and thinking the functional way

#71

Post by ww520 »

the_af wrote: post #63
ww520 wrote: post #23

Earlier quoted context omitted.

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…

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.

Re: Programming and thinking the functional way

#72

Post by platz »

ridiculous_fish wrote: post #59
cousin_it wrote: post #22

Earlier quoted context omitted.

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?

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 One letter variable names, argh!

reminds me of algos in matlab

Re: Programming and thinking the functional way

#73

Post by ww520 »

the_af wrote: post #66
Rusky wrote: post #25

Earlier quoted context omitted.

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

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.

Re: Programming and thinking the functional way

#74

Post by oakwhiz »

alkonaut wrote: post #54
platz wrote: post #32

Earlier quoted context omitted.

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…

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 sol…

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.

Re: Programming and thinking the functional way

#75

Post by freyrs3 »

nhaehnle wrote: post #60
freyrs3 wrote: post #44

Earlier quoted context omitted.

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?

Re: Programming and thinking the functional way

#76

Post by tel »

platz wrote: post #68
lomnakkus wrote: post #51

Earlier quoted context omitted.

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, yo…

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.

Re: Programming and thinking the functional way

#77

Post by the_af »

ww520 wrote: post #71
the_af wrote: post #63

Earlier quoted context omitted.

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…

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 Ja…

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.

Re: Programming and thinking the functional way

#79

Post by monokrome »

thinkpad20 wrote: post #18

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 t…

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?

Re: Programming and thinking the functional way

#80

Post by the_af »

ww520 wrote: post #73
the_af wrote: post #66

Earlier quoted context omitted.

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.
Post reply on HN