This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2021-12-27
Channels
- # adventofcode (1)
- # announcements (16)
- # babashka (16)
- # beginners (59)
- # calva (13)
- # clj-kondo (7)
- # clj-on-windows (3)
- # cljdoc (5)
- # clojure (85)
- # clojure-dev (5)
- # clojure-europe (4)
- # clojured (3)
- # clojurescript (87)
- # cursive (12)
- # emacs (4)
- # fulcro (15)
- # gratitude (1)
- # introduce-yourself (4)
- # malli (7)
- # off-topic (5)
- # polylith (6)
- # re-frame (15)
- # reagent (2)
- # shadow-cljs (5)
- # tools-deps (6)
- # web-security (2)
- # xtdb (5)
What is a hike, but a really long walk? ⛰️🚶:skin-tone-2:
I am pleased to announce a new library, https://github.com/lilactown/cascade. It provides a couple of helpful capabilities in two namespaces
1. cascade.core
is a collection of continuation-passing, thunk-producing versions of many Clojure core functions. This provides the ability to write recursive algorithms that do not use the call stack in Clojure(Script) by combining familiar operations like reduce
and into
with trampoline
.
2. cascade.hike
is like `clojure.walk`, but defines `walk` in a way that supports walking very large, nested data structures without using the call stack. prewalk
, postwalk
et al. work just like their original counterparts but can traverse arbitrarily nested forms without overflowing the stack.
Documentation is https://cljdoc.org/d/town.lilac/cascade/1.1.0/doc/readme. Any questions, comments, or issues can be DMed to me or opened in a GitHub issue. Happy hiking!
Nicely done I'm of a mind to extract the lazy streams idea from micro kanren and see how it interacts with this :thinking_face:
Another thing which I find interesting is how CPS identity
is 1 in Church numerals and constantly
is 0
Hi! It would help me to understand when I might want to use Cascade if the README has some motivating examples. I do no think I run into the need that it satisifies. What kind of algorithms/problems that need you have you two encountered? 🙏
from what I understand, it emulates recursion but it doesn't fill up the stack. ie, a classic problem is depth-first search on a tree (think of reimplementing ls -R
for a filesystem) - the recursive solution is simple but in practice limited by the stack size, so if the depth exceeds some limit it crashes. With cascade you keep the simple nature of the solution but the limit is "magically" gone.
Specifically, Will came to this solution trying to prevent stack overflows in his other library, pyramid
@U0522TWDA the cascade.walk
namespace is what originally motivated me to write the rest of the library. it allows you to walk an arbitrarily nested Clojure data structure without worrying about failing with a StackOverflow exception
like Ben said, I wanted this ability in pyramid to normalize extremely large data structures. See it used here: https://github.com/lilactown/pyramid/blob/trampoline/src/pyramid/core.cljc#L120-L133
a library that meets a similar need is clojure.zip. cascade is quite a bit faster than zippers IME, although I haven't figured out how to move up/down/left/right in all the ways zippers do yet
there's some other interesting properties that Ben referenced above, like the ability to pause/resume and interleave the calculation of algorithms that are written in the trampolined styled that cascade is
Thanks a lot!