Y-Combinator defined and used in Clojure

Below is Y-Combinator (a fixed-point combinator) encoded in Clojure and examples of its use. Note that this is the call-by-value version of Y-Combinator since the one given in the book converges only in the call-by-name lambda-calculus, and results in divergence in call-by-value.


(ns YCombinator) 

;; the Y-Combinator 
(def Y (fn [f] ((fn [x] (f (fn [y] ((x x) y)))) 
                (fn [x] (f (fn [y] ((x x) y)))))))

;; the function that is used to define recursive factorial. 
;; Note that f is a parameter and the function itself is anonymous. 
(def fact-funct (fn [f] (fn [n] (if (<= n 0) 1 (* n (f (- n 1)))))))

;; using fact-funct to define the factorial function as the fixed
;; point.  
(def fact (Y fact-funct))

;; checking that fact works as expected
(println (fact 5))

;; the function for recursion on collections
(def sum-funct (fn [f] (fn [coll] (if (empty? coll) 0
                                         (+ (first coll) (f (rest coll)))))))

;; defining the sum-coll function using Y-Combinator
(def sum-coll (Y sum-funct))

(println (sum-coll [2 3 4 5]))

UMM CSci 4651

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.