Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Applying the Y-Combinator to a recursive function with two arguments in Clojure?

Doing the Y-Combinator for a single argument function such as factorial or fibonacci in Clojure is well documented: http://rosettacode.org/wiki/Y_combinator#Clojure

My question is - how do you do it for a two argument function such as this getter for example?

(Assumption here is that I want to solve this problem recursively and this non-idiomatic clojure code is there deliberately for another reason)

[non y-combinator version]

(defn get_ [n lat]
    (cond
      (empty? lat) ()
        (= 0 (- n 1)) (first lat)
        true (get_ (- n 1) (rest lat))))

(get_ 3 '(a b c d e f g h i j))
like image 467
hawkeye Avatar asked Aug 14 '10 11:08

hawkeye


2 Answers

The number of args doesn't change anything since the args are apply'd. You just need to change the structure of get_:

(defn get_ [f]
  (fn [n lat]
    (cond
      (empty? lat) ()
      (= 1 n) (first lat)
      :else (f (dec n) (next lat)))))

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
     (f (fn [& args]
          (apply (x x) args))))))
user=> ((Y getf) 3 '(a b c d e f g h i j))
c
like image 145
Alex Taggart Avatar answered Sep 28 '22 01:09

Alex Taggart


It'd be pretty straight forward.

Say you've got a function H:

(def H
  (fn [x] 
        (fn [x y]
              (stuff happens))))

Then you apply the same ol' Y-Combinator:

((Y H) 4 5)

Where 4 and 5 are arguments you want to pass to H.

The combinator is essentially "dealing with" the top-level function in H, not the one that's doing the hard work (the one with arity 2, here).

like image 35
Isaac Avatar answered Sep 28 '22 01:09

Isaac