Composition is better than recursion in functional programming | Hacker News Reader

Composition is better than recursion in functional programming

blog.fogus.me

62 pointsPaulHoule28 comments

Early functional languages were based on two basic constructs:

  *Linked lists (cons-cells) for data structures
  *Recursion (with or without TCO) for control flow

Both of these concepts are fundamentally sequential and not less important very low level. For today's manycore/parallel/distributed world, better fit would be:

  *Nested data-parallel types (like in NESL or Intel ArBB)
  *HOFs, array/dictionary/parallel comprehensions

Exactly what I was trying to say. BTW you should update your formatting a little bit.

Guy Belloch's talk on Parallel Thinking at PPoPP09: http://www.cs.cmu.edu/~guyb/papers/PPoPP09.pdf

Guy Steele's talk on Breaking Sequential Habits of Thought: http://groups.csail.mit.edu/mac/users/gjs/6.945/readings/MIT...

I suspect you're already familiar with these since you cite NESL, but they're worth linking anyway. (Also, I've always had these talks linked in my mind, but I just realized they're both named Guy. Odd.)

Recursion is not fundamentally sequential. It depends on your data structures:

Structural recursion on sequential data structures is sequential. Structural recursion on somewhat-balanced tree-like data structures is more amenable to parallelism.

(And non-structural recursion is too general to talk here.)

Though I agree that using recursion does not scale very well in terms of program complexity. Hide your data flow behind combinators, if you don't want to get a headache.

I highly recommend Guy Steele's talk that's linked in a sibling comment. I am glad I attended ICFP that year.

For me, the important point is that higher-order functions (map, fold, etc.) compose well with other higher-order functions, whereas hand-coded recursion doesn't really compose with itself or anything else. Using recursion in a functional language is a little like using a for loop in an imperative one.

    hand-coded recursion doesn't really compose 
    with itself or anything else

That's not true. If you look at the implementations of the functions composed in the OP, you'll see:

* `partition-by` implemented via recursion

* `comp` implemented via recursion

* `map` implemented via recursion

* `repeat` implemented via recursion

The point is that recursion should be a last resort[1] and something squirreled away in combinators.

[1]: Last resort is a flexible term, but my meaning should not be taken as "never use recursion", just be thoughtful about it.

I think you missed Tim's point. A better analogy might be duplicating code vs writing a function once and reusing it. Hand-written recursion with the operation inlined is not usually very reusable (i.e. composable); however, if you factor out the recursive traversal and parameterize it by the operation to be performed, it composes much better. But at that point you're writing a library routine, rather than logic specific to the task at hand.

(As an aside: in my way of thinking about software design, generic library code is "free" - it doesn't count towards the number of lines of code for the actual task being solved. I try to make as much of the software that I design library-like, and the core of the app not a lot more than composing these pre-fabricated bits, as possible, potentially even to my detriment in short-term productivity. But this approach handles scale much better, in my experience.)

In fairness, the title of this submission should be Composition is better than recursion in functional programming... unless recursion is better.

>> Having said that; their points are valid because in Clojure (and likely most, if not all functional languages) recursion should be seen as a low-level2 operation and avoided if at all possible.

That part was even in bold. Which totally runs counter to what Scheme emphasizes (recursion wherever possible).

    recursion wherever possible

Because in Scheme (R5RS anyway, I have not kept up with 6) recursion is the primary means of iteration.

I'm not 100% certain you got the point, which is that in Clojure (and Haskell and I'm sure others) recursion is used "whenever possible" but given a choice you should use the pre-rolled recursions available in the various combinators, not implement it yourself directly.

fold, map, filter, and a wide variety of other things are all recursive, but the recursion can and should be factored away. A "map" is utterly clear what is going on. The handwritten recursive version of a map requires a bit of analysis to be quite sure there's nothing tricky in the function being mapped, especially as the function being mapped gets large.

Except in this case, it is not better.

His RLE example traverses the sequence twice and creates an intermediate structure. It works find for small examples, but what happens when you are doing 3x the work on your 1,000,000 item sequence?

This could be done just as clearly (possibly more clearly) recursively, traversing the sequence only once, without an intermediate data structure.

I am all for functional composition in programming languages, but composition and recursion should be treated as equally fundamental (what is recursion but composing a function with itself, in a certain way, anyway?)

Here is a (not heavily tested) tail-recursive common lisp version (no recent clojure version installed here currently).

http://paste.lisp.org/display/120383

    > Except in this case, it is not better.

Clojure's sequence functions are lazy. Observe the following:

    (def inf (interleave (cycle [1 1 2]) 
                         (cycle [1 2 2])))

Depending on your REPL settings, if you try to evaluate inf you'll eventually blow your heap. This is clearly an infinite sequence. So by your measure, passing it into rle will be a disaster right?

    (take 5 (rle inf))
    ;;=> ([3 1] [3 2] [3 1] [3 2] [3 1])

The laziness of Clojure guarantees that at no point is the full sequence realized in memory. The sequence is processed once, and only the part of the sequence that we care about is processed.

Yes the sequences are lazy, but that isn't really the point.

The 'pack' function is still consing together unnecessary subsequences. The count function also has to iterate across each of these subsequences (assuming they are lists, which they look to be). This can be done much more cleanly in a recursive fashion.

When I'm counting consecutive equivalent entries in a list, why wouldn't I just count them and return the results?

Sorry fogus, but implementing this in a point free style is horribly inefficient.

    The 'pack' function is still consing 
    together unnecessary subsequences.

No, it's not.

    The count function also has to iterate 
    across each of these subsequences

Only the sequences that it sees.

    This can be done much more cleanly 
    in a recursive fashion.

I suppose we have different definitions of clean.

    implementing this in a point free 
    style is horribly inefficient.

Call me unconvinced.

I wasn't sure if you were just obstinately dismissing my arguments, so I decided to do a benchmark and prove this to you.

http://paste.lisp.org/display/120386

Here is the benchmark. I did two versions in clojure 1.2, the first one uses a transient vector... the second a list. (which it reverses at the end).

As you can see, on my machine, the timings for these benchmarks puts the recursive list version approximately 2x faster than your version.

edit: annotated paste with more generous timings of composition version.

http://paste.lisp.org/display/120386#2

Are you convinced that yours is doing more work now?

edit2: I will note, however that neither of mine are fully lazy. I am not a Clojure expert, so I'm not intimately familiar with the laziness abstractions, how would I make these functions use the laziness abstractions? is it even possible?

I was going to chime in to say that moving from a vector to a recursive reversed list-based implementation for a mere 3x performance gain was a premature optimization at the expense of readability. Then I actually read your code and the two implementations looked nearly identical, so I guess I'll just leave this here.

n.b. - I have actually done a bit of Clojure programming myself but the fine points you and Fogus are discussing here are largely over my head, at least juding by the code sample.

I've upmodded this whole discussion because I think it's the kind of thing I love to see on HN, even though my bias is "do the cleaner thing first, optimize later if necessary."

But, I just wanted to point out that paste.lisp.org's paren matching is beautiful.

I've added a tail-recursive lazy version.

It seems to be about the same amount of a speedup, with the nice addition of less memory use.

http://paste.lisp.org/display/120386#3

I thought the 'better performance' of my other versions were specious because data-structure choice often makes a big difference in these sorts of benchmarks. List vs Array vs Lazy-Seq should make a difference.

I think this is more definitive, as it produces the (program-flow wise) similar computation to the original. (Not just the same results).

You seem to have reframed the discussion from "horribly inefficient" as defined by extraneous operations, to one of raw speed. I'm certain I've never claimed that a tail-recursive implementation couldn't produce faster times. My statement from the beginning has been that recursion is a low-level operation. I stand by that statement. My combinator post provided 3 useful functions that could prove useful in the future. Your `recle4` implementation does one thing only. If any one of the functions in my combination gains speed, then my implementation will likewise gain speed. This leaves room for optimization without having to dive right into creating a convoluted recursive implementation. I'm pretty sure the words "avoided if at all possible" subsumes the need to optimize if every ounce of speed is required. Raw execution speed is not the only unit of speed that we should consider. We shouldn't sacrifice the speed of the developer or the speed of comprehension just to placate our lizard brains.

I have not done any reframing whatsoever. You never framed the conversation to begin with.

You said, point blank, that composition is better than recursion in functional languages. Better. I called BS.

How, exactly, then, do you define 'better'? You didn't give an operational definition of 'better' (which is your responsibility, not mine), so I made up my own.

If you don't like it, then be more careful with your claims. It certainly is not 'better' in all meanings of the word. (at least any of those that are clearly defined or measurable for me. In retrospect I see that you were talking about 'style' but 'style' is pretty impossible to measure as it is entirely subjective).

I wrote a similar function in the same language, and it was twice as fast as yours. Your function, therefore, wastes operations. (At least twice as many, approximately). That isn't a small amount!

I'm not even serious about Clojure and my solution seems pretty straightforward. Unless all recursion is rocket science, it is very simple recursion.

(Granted I had to RTFM to write it and I suppose a proper name might help, but it would help your implementation too).

Why do I need dozens and dozens of ravioli functions that I'm just going to forget that I implemented clutter my name-spaces? Please, for the love of God, at least use a letfn/flet/labels.

What is the next developer going to do when I am dead or have retired to my private island? He'll have to learn, not one, but 3 different functions, and know what they do. None of your composed functions are particularly self explanatory.

In what way do you think you will get a 2x improvement through the improvement of other functions?

I suppose if you write a new compiler for Clojure (perhaps a sufficiently smart one?), it could happen, but you will not get that type of improvement simply by improving the 'pack' function, for example.

The way that you are going about collecting the values is fundamentally opposed to efficiency.

'Creating homogeneous groupings then counting the size of those groups' (what you did) is going to be slower than 'counting consecutive same things' (what I did).

This isn't really about raw efficiency, this is about a fundamentally broken thought process used to describe the algorithm. That broken thought process is a result of attempting to shoehorn the answer into the realm of functional composition.

Anyway, I respectfully disagree.

Next time before you go off on a tirade against my so called claims, go back and check your facts. I did not say "better". Whomever submitted my post did.

You have interesting ways of respectfully disagreeing with people.

Haskell version that is fully lazy, (though not point-free or completely idiomatic).

  import Data.List (group)                                   
  rle = map (\x-> (length x, head x)) . group
  main = print $ rle "aaaabccaadeeee"

You can replace (\x -> (length x, head x)) with (length &&& head) if you import Control.Arrow to make it fully point free

And stream fusion should get rid of intermediate data structures.

Good idea re: Arrows, and we can go all out as long as we're using them. :-)

rle = group >>> map (length &&& head)

Can't agree more! Just think about how code can scale to multi-cores / GPUs. It's all because composition is more _declarative_ than recursion. (Although recursion is still more declarative than C-style imperative programming.)

Why?

Reply on news.ycombinator.com