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

61–70 of 86 posts

Re: Programming and thinking the functional way

#61

Post by platz »

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…

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

Re: Programming and thinking the functional way

#63

Post by the_af »

ww520 wrote: post #23
the_af wrote: post #19

Earlier quoted context omitted.

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.

Re: Programming and thinking the functional way

#64

Post by ww520 »

ridiculous_fish wrote: post #53

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.

Re: Programming and thinking the functional way

#65

Post by nardi »

dragonwriter wrote: post #49
chongli wrote: post #21

Earlier quoted context omitted.

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 (lar…

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

Re: Programming and thinking the functional way

#66

Post by the_af »

Rusky wrote: post #25
the_af wrote: post #17

Earlier quoted context omitted.

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.

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?

Re: Programming and thinking the functional way

#67

Post by alkonaut »

platz wrote: post #61
alkonaut wrote: post #54

Earlier quoted context omitted.

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…

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!

Re: Programming and thinking the functional way

#68

Post by platz »

lomnakkus wrote: post #51
tel wrote: post #3

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…

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

Re: Programming and thinking the functional way

#69

Post by [deleted] »

freyrs3 wrote: post #44
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?

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.

[deleted]

Re: Programming and thinking the functional way

#70

Post by platz »

alkonaut wrote: post #67
platz wrote: post #61

Earlier quoted context omitted.

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.

Post reply on HN