Or maybe I do mind if it’s slower…
I’ll try to show a short example of how one can get around needing binding recursion or the possibility of cyclic data structures at all, as follows (note that since deferred execution and memoizing recursion are different forms of the same thing, I’ll implement this as a Stream so it can run on Ellie with Elm version 0.19):
To recap, using binding recursion/cyclic data, we can implement “ones” as follows:
type Stream a = ConsSteam a (() -> Stream a)
ones = ConsStream 1 <| \() -> ones
we can rewrite that using function recursion as:
ones = let rept() = ConsStream 1 <| \() -> rept() in rept()
or given the following definition for the “Y-combinator” for recursive functions with deferred execution injected so it doesn’t infinitely loop:
fix f = f <| \() -> fix f
we can write it as the following:
ones = let rept strm = ConsStream 1 <| \() -> strm() in fix rept
which works equally as well and more generally.
So what’s the disadvantage of using function recursion rather than the current global recursive bindings/possibility of global cyclic data structure?
It’s primarily one of speed of execution, as the recursive binding version only makes one “thunk” call per element and no new memory allocations per element, whereas both of the recursive function call versions make two function calls and much more seriously as to execution time is that it needs to make several new heap allocations for every successive element evaluation (speed of many small memory allocations is not very optimal for most primarily imperative languages such as JavaScript/C/C++ etc.). The memory allocations are due to creating the actual new “Stream” instance as well as the “closure” for the tail, and in the case of the “fix/Y-combinator” version, an extra closure/function for the combinator formulation.
Compare the speed with this Ellie link, setting the clock rate to that of your CPU (the boosted, single threading rate), and selecting which of the versions to run, commenting out the others, recompiling before each run.
You’ll see that it only takes less than 20 clock cycles to do the single function call and return, whereas it takes hundreds to do the memory allocation (variable time due to garbage collection as occasionally required), and even more time to run the Y-combinator version as explained.
Perhaps that is why @evancz has left us with the possibility of cyclic data structures at the global level. However, he understands (in my view incorrectly as per my post looking at number of references) that when used in combination with the old Lazy library, that the cyclic data reference count will continuously increase.
This example is actually somewhat an argument for use of the Lazy library, as the function recursive version would still need to allocate memory for the “Stream” elements for the first pass, but future sweeps through the sequence would not have to do further element allocations for already evaluated elements, saving a significant amount of time in not doing memory allocations. So if one needs to sweep through a sequence twice or more, it makes a lot of sense to use Lazy in formulation.
It’s true that if implemented with the Lazy, memory use would increase with every element evaluated, but that’s what we want in the case of many sweeps across the sequence as that is what saves the recalculation and re-allocation time. If it were desired to reduce memory use where the algorithm only needs access to a narrow range of list values at a time, then the head of the list/stream shouldn’t be bound by a fixed binding but rather be generated by a function with the head(s) of the stream released when no longer required.
Another argument as to reduced execution time for some algorithms is that memoizing using a lazy list is O(n) asymptotic performance instead of O(n log n) as all of Elm’s persistent data structures are.