Skip to content

Instantly share code, notes, and snippets.

@kohyama
Created June 9, 2012 15:40
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kohyama/2901487 to your computer and use it in GitHub Desktop.
Save kohyama/2901487 to your computer and use it in GitHub Desktop.
unfold in Clojure
(use 'clojure.test)
(defn unfold
"A variant of 'iterate' which accepts a stopping condition,
having the same syntax as 'unfold' of scheme.
Supposed
(x1 x2 x3 ... xk-1 xk ... ) == (s (g s) (g (g s)) ... )
and '(p xi)' returns true first at i == k,
((f x1) (f x2) (f x3) ... (f xk-1))
is returned."
[p f g s]
(loop [c s rvsd '()]
(if (p c)
(loop [acc '() [r & rs] rvsd]
(if r (recur (cons (f r) acc) rs) acc))
(recur (g c) (cons c rvsd)))))
(deftest test-unfold
(are [expected result] (= expected result)
(unfold #(<= 12 %) #(* 2 %) #(+ 2 %) 3) '(6 10 14 18 22)
(unfold #(<= 100 %) #(+ 2 %) #(* 2 %) 1) '(3 4 6 10 18 34 66)
))
@kohyama
Copy link
Author

kohyama commented Jun 10, 2012

'cont-unfold' consumes large stack.
(cont-unfold #(<= 10000 %) identity inc 0) ; -> (0 1 2 ... 9999)
(cont-unfold #(<= 100000 %) identity inc 0) ; -> StackOverflowError clojure.lang.RT.boundedLength (RT.java:1607)
What is a better implementation of unfold?

@kohyama
Copy link
Author

kohyama commented Jun 11, 2012

Using a list which contains what calculations should be done, finally 'reverse' it and apply.
It became not to eat stack, but still using large heap. Hum...

@kohyama
Copy link
Author

kohyama commented Jun 12, 2012

'comp' calls 'reverse' internally.
So I changed not to use 'reverse' and 'comp' but to 'comp'oseing manually.
Still eat large heap.

@kohyama
Copy link
Author

kohyama commented Jun 12, 2012

The operation '#(cons (f %) %2)' doesn't vary in the chain of calculations.
We only have to consing results of '#(g %)' in a list and return with reversed order.

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