Even if it is hard to explain why, I particularly like the Y combinator. It isn't very practical in most "standard" languages. However, there is something poetic with it.
A couple of years ago I came from long exposure to SML and Haskell. As a consequence, when I started working with Erlang, I really missed the possibility to define everything as an anonymous inner function. I tended to organize my functions with inner sub-functions that often were recursive. As far as I knew (and still know), in Erlang it is rather hard to do this kind of things. First, the syntax is less clear than the Haskell equivalent and second, the "lambda" functions cannot be recursive. As a consequence, I tried using the Y combinator. And no, it is not a particularly good idea, but I enjoyed it.
Some times later, I tried to work with the Y combinator in Python. As Python completely lacks any form of tail call optimization, this is a very bad practice. However, I really liked the idea of using the Y combinator as a decorator... and that is almost as nice as the "apply decorator trick". Well, of course the apply decorator trick has no drawbacks and can be employed in real settings. The Y combinator in Python cannot (besides, the implementation I gave works only with functions with one argument, but the extension to arbitrary functions is trivial).
Back to clojure... I decided to implement Y in clojure as well. Of course, since clojure does not have TCO either, it is just a toy device. Moreover, there is no need for such a tool (as the syntax for nested recursive functions in clojure is nice). However, as I said... I love the Y combinator.
Well... this is the clojure version:
(defn Y [F]
(let [G (fn [K]
(F (fn [& A]
(apply (K K) A))))]
(G G)))
(def fact
(Y (fn [f]
(fn [n]
(if (<= n 0)
1
(* n (f (- n 1))))))))
End of the story (yeah, basically it is like the scheme version). By the way... I'm starting toying with trampolines to see what can be done.
A couple of years ago I came from long exposure to SML and Haskell. As a consequence, when I started working with Erlang, I really missed the possibility to define everything as an anonymous inner function. I tended to organize my functions with inner sub-functions that often were recursive. As far as I knew (and still know), in Erlang it is rather hard to do this kind of things. First, the syntax is less clear than the Haskell equivalent and second, the "lambda" functions cannot be recursive. As a consequence, I tried using the Y combinator. And no, it is not a particularly good idea, but I enjoyed it.
Some times later, I tried to work with the Y combinator in Python. As Python completely lacks any form of tail call optimization, this is a very bad practice. However, I really liked the idea of using the Y combinator as a decorator... and that is almost as nice as the "apply decorator trick". Well, of course the apply decorator trick has no drawbacks and can be employed in real settings. The Y combinator in Python cannot (besides, the implementation I gave works only with functions with one argument, but the extension to arbitrary functions is trivial).
Back to clojure... I decided to implement Y in clojure as well. Of course, since clojure does not have TCO either, it is just a toy device. Moreover, there is no need for such a tool (as the syntax for nested recursive functions in clojure is nice). However, as I said... I love the Y combinator.
Well... this is the clojure version:
(defn Y [F]
(let [G (fn [K]
(F (fn [& A]
(apply (K K) A))))]
(G G)))
(def fact
(Y (fn [f]
(fn [n]
(if (<= n 0)
1
(* n (f (- n 1))))))))
End of the story (yeah, basically it is like the scheme version). By the way... I'm starting toying with trampolines to see what can be done.
No comments:
Post a Comment