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

51–60 of 86 posts

Re: Programming and thinking the functional way

#51

Post by lomnakkus »

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.

Re: Programming and thinking the functional way

#52

Post by freyrs3 »

nnq wrote: post #24
cousin_it wrote: post #10

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

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

Re: Programming and thinking the functional way

#53

Post by ridiculous_fish »

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.

Re: Programming and thinking the functional way

#54

Post by alkonaut »

platz wrote: post #32
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…

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

Re: Programming and thinking the functional way

#56

Post by lomnakkus »

CocaKoala wrote: post #36
rdtsc wrote: post #2

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…

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

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.

Re: Programming and thinking the functional way

#57

Post by millstone »

yanatan16 wrote: post #31
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…

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…

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.

Re: Programming and thinking the functional way

#58

Post by chongli »

AnimalMuppet wrote: post #47
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. 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 pr…

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

Re: Programming and thinking the functional way

#59

Post by ridiculous_fish »

cousin_it wrote: post #22
dons wrote: post #16

Earlier quoted context omitted.

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?

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!

Re: Programming and thinking the functional way

#60

Post by nhaehnle »

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.

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