Skip to content

Instantly share code, notes, and snippets.

@kohyama
Created June 8, 2012 06:41
Show Gist options
  • Save kohyama/2893987 to your computer and use it in GitHub Desktop.
Save kohyama/2893987 to your computer and use it in GitHub Desktop.
fold-right and reduce-right in Clojure
(use 'clojure.test)
(defn fold-right [f z coll]
(loop [[c & cs] coll rvsd '()]
(if (nil? c)
(loop [acc z [r & rs] rvsd]
(if r (recur (f r acc) rs) acc))
(recur cs (cons c rvsd)))))
(defn reduce-right [f coll]
(loop [[c & cs] coll rvsd '()]
(if (nil? cs)
(loop [acc c [r & rs] rvsd]
(if r (recur (f r acc) rs) acc))
(recur cs (cons c rvsd)))))
(deftest test-fold-right
(are [result expected] (= result expected)
(fold-right - 2 '(3 1 4 1 5 9)) ; (- 3 (- 1 (- 4 (- 1 (- 5 (- 9 2))))))
3
(fold-right #(cons (* 2 %) %2) '() '(3 1 4 1 5 9 2)) ; map #(* 2 %)
'(6 2 8 2 10 18 4)
(fold-right #(concat %2 (list %)) '() '(3 1 4 1 5 9 2)) ; reverse
'(2 9 5 1 4 1 3)
))
(deftest test-reduce-right
(are [result expected] (= result expected)
(reduce-right - '(3 1 4 1 5 9 2))
3
(reduce-right #(cons (* 2 %) (if (seq? %2) %2 (list (* 2 %2)))) '(3 1 4 1 5 9 2))
'(6 2 8 2 10 18 4)
(reduce-right #(concat (if (seq? %2) %2 (list %2)) (list %)) '(3 1 4 1 5 9 2))
'(2 9 5 1 4 1 3)
))
@kohyama
Copy link
Author

kohyama commented Jun 12, 2012

Updated not to eat large stack but heap.

user=> (fold-right - 0 (range 1000000))
-500000
user=> (fold-right - 0 (range 2000000))
OutOfMemoryError Java heap space clojure.lang.ArrayChunk.dropFirst (ArrayChunk.java:54)

@kohyama
Copy link
Author

kohyama commented Jun 12, 2012

How stupid have I been!
'f' doesn't vary in the accumulated list.
We only have to keep 1st operands of 'f' in reversed order in a list.

user=> (fold-right - 0 (range 2000000))
-1000000

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment