clojure.core/trampoline

View this page on ClojureDocs

Type: function Added: Clojure 1.0 Examples: 5 Runnable: 3

([f] [f & args])

trampoline can be used to convert algorithms requiring mutual recursion without stack consumption. Calls f with supplied args, if any. If f returns a fn, calls that fn with no arguments, and continues to repeat, until the return value is not a fn, then returns that non-fn value. Note that if you want to return a fn as a final value, you must wrap it in some data structure and unpack it after trampoline returns.

Examples

by dakrone on 2010-12-30 ▶

(defn foo [x] (if (< x 0) (println "done") #(foo (do (println :x x) (dec x))))) ;; #'user/foo ;; `trampoline` will keep calling the function ;; for as long as "foo" returns a function. (trampoline foo 10) ;; :x 10 ;; :x 9 ;; :x 8 ;; :x 7 ;; :x 6 ;; :x 5 ;; :x 4 ;; :x 3 ;; :x 2 ;; :x 1 ;; :x 0 ;; done ;;=> nil

by jafingerhut on 2015-01-15 ▶

;; Short tutorial-style article with example of using trampoline at this link: ;; http://jakemccrary.com/blog/2010/12/06/trampolining-through-mutual-recursion/

by phreed on 2015-01-27 ▶

;; Using mutually recursive functions to implement a finite state machine (FSM) ;; This machine has three states {a b c} and ;; seven transitions {:a-b :a-c :b-a :b-c :c-a :c-b :final}. (defn foo [cmds] (letfn [(a-> [[_ & rs]] #(case _ :a-b (b-> rs) :a-c (c-> rs) false)) (b-> [[_ & rs]] #(case _ :b-a (a-> rs) :b-c (c-> rs) false)) (c-> [[_ & rs]] #(case _ :c-a (a-> rs) :c-b (c-> rs) :final true false))] (trampoline a-> cmds))) (foo [:a-b :b-c :c-a :a-c :final]) ;;=> true

by foxlog on 2015-05-13 . May have evaluation errors. ▶

;; from <the joy of clojure 2nd> ;; Mutually recursive functions are nice for implementing ;; finite state machines (FSAs) (defn elevator [commands] (letfn [(ff-open [[_ & r]] "When the elevator is open on the 1st floor it can either close or be done." #(case _ :close (ff-closed r) :done true false)) (ff-closed [[_ & r]] "When the elevator is closed on the 1st floor it can either open or go up." #(case _ :open (ff-open r) :up (sf-closed r) false)) (sf-closed [[_ & r]] "When the elevator is closed on the 2nd floor it can either go down or open." #(case _ :down (ff-closed r) :open (sf-open r) false)) (sf-open [[_ & r]] "When the elevator is open on the 2nd floor it can either close or be done" #(case _ :close (sf-closed r) :done true false))] (trampoline ff-open commands))) (elevator [:close :open :close :up :open :open :done]) ;=> false (elevator [:close :up :open :close :down :open :done]) ;=> true ;; run at your own risk! (elevator (cycle [:close :open])) ; ... runs forever

by mhmdsalem1993 on 2016-12-28 . May have evaluation errors. ▶

;; without trampoline (declare hatt) (defn catt [n] (when-not (zero? n) (when (zero? (rem n 100)) (println "catt:" n)) (hatt (dec n)))) (defn hatt [n] (when-not (zero? n) (if (zero? (rem n 100)) (println "hatt:" n)) (catt (dec n)))) ;; std=> catt: 100000000 ;; std=> catt: 99999900 ;; std=> catt: 99999800 ;; std=> catt: 99999700 ;; std=> catt: 99999600 ;; std=> catt: 99999500 ;; std=> catt: 99999400 ;; . ;; . ;; . ;; std => CompilerException java.lang.StackOverflowError ;; with trampoline (declare hattr) (defn cattr [n] (when-not (zero? n) (when (zero? (rem n 100)) (println "cattr:" n)) (fn [] (hattr (dec n))))) (defn hattr [n] (when-not (zero? n) (if (zero? (rem n 100)) (println "hatttr:" n)) (fn [] (cattr (dec n))))) (trampoline cattr 10000000) ;; std=> catt: 100000000 ;; std=> catt: 99999900 ;; std=> catt: 99999800 ;; std=> catt: 99999700 ;; std=> catt: 99999600 ;; std=> catt: 99999500 ;; std=> catt: 99999400 ;; . ;; . ;; . ;; std=> catt: 100

Note by gstamp

A tutorial on how to use trampoline is available here:

http://pramode.net/clojure/2010/05/08/clojure-trampoline/

and here:

http://jakemccrary.com/blog/2010/12/06/trampolining-through-mutual-recursion.html

Note by dvingo

The links above are dead. Here are the archived versions:

https://web.archive.org/web/20190626232715/http://pramode.net:80/clojure/2010/05/08/clojure-trampoline/

https://web.archive.org/web/20110111121137/http://jakemccrary.com:80/blog/2010/12/06/trampolining-through-mutual-recursion.html

See also

• clojure.core/loop (10)
• clojure.core/recur (9)
• clojure.core/letfn (1)

---

Content from the matching ClojureDocs page, with authors credited on each contribution.