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

31–40 of 86 posts

Re: Programming and thinking the functional way

#31

Post by yanatan16 »

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

Re: Programming and thinking the functional way

#32

Post by platz »

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 have yet to read it)

Re: Programming and thinking the functional way

#33

Post by platz »

tel wrote: post #14
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…

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

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.

Re: Programming and thinking the functional way

#34

Post by wting »

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…

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.

Re: Programming and thinking the functional way

#35

Post by noname123 »

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?

Re: Programming and thinking the functional way

#36

Post by CocaKoala »

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

Re: Programming and thinking the functional way

#37

Post by ef4 »

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…

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

Re: Programming and thinking the functional way

#38

Post by xxs »

skybrian wrote: post #7

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

Re: Programming and thinking the functional way

#39

Post by peteratt »

senorprogrammer wrote: post #9
[deleted] wrote: post #8

Earlier quoted context omitted.

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

Re: Programming and thinking the functional way

#40

Post by tel »

jerf wrote: post #27
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…

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

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