read


read
or learn more

Recursion is a low-level operation

Mar 9, 2011

Yesterday I demonstrated how to transform a mundane recursive function into a tail recursive function. However, I received some flak for that post because there are better ways to implement run-length encoding with Clojure. While certainly true, I think some of my critics1 missed the point of the exercise. ;-)

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. The better path is to take a survey of the available higher-order functions and plug them together to create new functions. We go through great pains to stress this in Joy of Clojure, so I will not retrace well-trodden ground. Instead, observe the following:

(def S '[a a a a b c c a a d e e e e])

(def pack (partial partition-by identity))

(pack S)
;;=> ((a a a a) (b) (c c) (a a) (d) (e e e e))

(def rle (comp (partial map (juxt count first)) pack))

(rle S)
;=> ([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])

(def rld (partial mapcat (partial apply repeat)))

(-> S rle rld)
;;=> (a a a a b c c a a d e e e e)

As a nice bonus, the definitions3 above are point-free.

:f


  1. Critic is probably not a fair statement. A better term would be kritik. 

  2. Low in respect to levels of abstraction and also in much the same sense as hedonism is low. 

  3. Much thanks to Christophe Grand, Alan Malloy, and Alan Dipert for the ideas motivating4 this post. 

  4. That is, I stole their ideas and made them point-free. cough. cough. 

12 Comments, Comment or Ping

  1. compose and curry ar by far better names for partial and comp

  2. While you clarified low level, could I seek your view on “avoidable” ?

    Avoidable as in if there’s a non-recursive way to do something avoid recursion altogether ? OR Avoidable as in seek out higher order functions which are internally recursive thus requiring simpler non recursive functions to be passed in.

    I suspect it is the latter, but am not sure. If it is the former would like to hear more on the topic.

  3. compose and curry ar by far better names for partial and comp

    Clojure’s partial does not perform currying. For that matter, nothing in Clojure’s core performs currying.

  4. could I seek your view on “avoidable” ?

    Like everything, choosing one path over another is something that should be weighed appropriately. There are matters of existence (i.e. an appropriate HOF does not exist), speed (an existing HOF is slow), stability (an existing HOF is buggy), and expression (a solution can be better expressed via recursion) to take into account.

  5. david karapetyan

    Only a functional programmer would consider recursion a low level abstraction and composition of higher order functions as the “proper way” to express a recursive algorithm. I wonder when bananas and lenses will become the proper way of accomplishing things.

  6. I wonder when bananas and lenses will become the proper way of accomplishing things.

    The sooner the better!

  7. Michael

    Although I completely agree that using existing functions that abstract recursion into higher-level operations is a good thing, I’m not so sure I’d be so quick to push recursion down into the land of “primitives you shouldn’t have to think about”. Recursion and induction are brothers in arms, and enable you to properly decompose problems mentally, enabling you to “see” the solution without the trial/error method of bending code to your will. While explicit recursion might be commonly avoidable, a recursive mindset is a powerful asset.

  8. recursive mindset is a powerful asset.

    I’m not sure that I’m willing to tackle that one. I would probably agree with you if I knew what you meant.

  9. Michael

    I would probably agree with you if I knew what you meant.

    I’m nit picking, as I agree with the underlying message of your post.

    I was only commenting that (mathematically) inductive reasoning is a powerful method of problem decomposition, and may (at times) lead to correctness being more obvious than in equational (or heaven forbid… imperative) reasoning.

    Baby/bathwater sort of thing.

  10. Lemming

    Recursion is the GOTO in functional programming languages. Too often I see recursive code in Haskell, that actually does ‘map’.

  11. A previous poster said: “(mathematically) inductive reasoning is a powerful method of problem decomposition, and may (at times) lead to correctness being more obvious than in equational (or heaven forbid… imperative) reasoning.”

    Extraordinary claims require extraordinary evidence… how do you even know that imperative programs are a form of mathematics themselves (Dijkstra was a mathematician and seemed to have no problem reasoning about imperative programs, as long as he avoided using GOTO as much as possible). Recursion can be very hard to reason about since it confuses the human brain.

    Continuations jokingly reinvent GOTO statements. Exception handling reinvents intraprocedural gotos.. Monads reinvents the state by pretending that you can isolate concerns and magically your programs are more robust (extraordinary claims… require…. that’s right.. evidence). Lisp allows one to redefine his supposed functional language to be anything under the sun that he wants – and people get lost in macro mind games and recursive mind games, instead of GOTO mind games. How do you delete a file in Haskell? You do it the same way as you would in an imperative program since it is a side effect that must occur… If you actually look at the code that haskell requires in order to delete a file, it’s the same, or even worse, than an imperative program… it looks something like an exact replica of an imperative program..

    when fileExists $ removeFile FileName
    

    or some nonsensical garbage functional programming that claims to be mathematically superior to an imperative. And the imperative looks strangely similar, almost like Haskell kind of, well, reinvented imperative programming.

    // imperative example:
    fname := 'example.txt';
    if fileExists(fname) then deleteFile(fname);
    

Reply to “Recursion is a low-level operation”