Local recursive lazy sequences

[Achim Passen]

Hi!

Is there a way to have locally bound recursive lazy sequences in
Clojure? I'd like to define a function that uses a lazy seq as an
interim result, so i wouldn't want to use a top-level def.

I'll try to give a short example. You can define the sequence of
fibonacci numbers lazily-recursively like this:

(def fibs (lazy-cat '(0 1) (map + fibs (drop 1 fibs))))

Now suppose you want to define a function which returns the nth
fibonacci number, but you down want "fibs" around globally. My guess
was:

(defn fib [n]
(let [fibs2 (lazy-cat '(0 1) (map + fibs2 (drop 1 fibs2)))]
(nth fibs2 n)))

But this yields "Unable to resolve symbol: fibs2 in this context", so
let doesn't allow being self-referential the way def does. I don't
quite understand why the second arg to lazy-cat is being evaluated in
the first place. Shouldn't evaluation be delayed until needed?

Does anyone know how to get around this?

Thanks a lot!

Kind regards,
achim

[Michael Reid]

Hi Achim,

On Sun, Aug 31, 2008 at 1:58 PM, Achim Passen <achim....@gmail.com> wrote:

> Now suppose you want to define a function which returns the nth
> fibonacci number, but you down want "fibs" around globally. My guess
> was:
>
> (defn fib [n]
> (let [fibs2 (lazy-cat '(0 1) (map + fibs2 (drop 1 fibs2)))]
> (nth fibs2 n)))
>
> But this yields "Unable to resolve symbol: fibs2 in this context", so
> let doesn't allow being self-referential the way def does. I don't
> quite understand why the second arg to lazy-cat is being evaluated in
> the first place. Shouldn't evaluation be delayed until needed?
>
> Does anyone know how to get around this?

You can create locally recursive functions by writing an inline (fn
..) form with a name. So your example above becomes:

(defn fib [n]
(let [fibs2 (fn fibs2 [] (lazy-cat '(0 1) (map + (fibs2) (drop 1 (fibs2)))))]
(nth (fibs2) n)))

So instead of defining fibs2 as a lazy-cat directly, we wrap it in a
function that when called returns the lazy-cat you are trying to
define. Note that the inline (fn) form has a symbol inserted before
its argument list:

(fn fibs2 [] (lazy-cat ...)))

This allows an anonymous function to refer to itself. Then we just
need to replace each use of fibs2 with a call to the wrapper instead
of a direct reference to the lazy-cat--each reference to fibs2 becomes
a call to (fibs2).

Results:

user> (fib 0)
0
user> (fib 1)
1
user> (fib 2)
1
user> (fib 3)
2
user> (fib 4)
3
user> (fib 5)
5

There might be a cleaner way to do this, I'm not sure. This was the
first idea that popped into my head :).

/mike.

[Achim Passen]

Hi Mike,

thank you for your reply!

On Sep 1, 3:15 pm, "Michael Reid" <kid.me...@gmail.com> wrote:
> (defn fib [n]
>   (let [fibs2 (fn fibs2 [] (lazy-cat '(0 1) (map + (fibs2) (drop 1 (fibs2)))))]
>     (nth (fibs2) n)))

Dodgy. ;-) I wasn't aware of named anonymous fns – nice.

But i suspect disguising lazy seqs as fns prevents memoization from
happening, which is the benefit of using lazy seqs over naive
recursion. So on each (fibs2) call, a completely new fibs sequence is
built, without reusing values computed earlier, it seems:

With

(def fibs (lazy-cat '(0 1) (map + fibs (drop 1 fibs))))

(defn fib [n]
(let [fibs2 (fn fibs2 [] (lazy-cat '(0 1) (map + (fibs2) (drop 1
(fibs2)))))]
(nth (fibs2) n)))

freshly defined, (nth fibs 10000) finishes in a couple of seconds,
while (fib 10000) might run for ages …

Any ideas very much appreciated!

Thanks again,

kind regards,
achim

[Rich Hickey]

On Aug 31, 1:58 pm, Achim Passen <achim.pas...@gmail.com> wrote:
> Hi!
>
> Is there a way to have locally bound recursive lazy sequences in
> Clojure? I'd like to define a function that uses a lazy seq as an
> interim result, so i wouldn't want to use a top-level def.
>
> I'll try to give a short example. You can define the sequence of
> fibonacci numbers lazily-recursively like this:
>
> (def fibs (lazy-cat '(0 1) (map + fibs (drop 1 fibs))))
>
> Now suppose you want to define a function which returns the nth
> fibonacci number, but you down want "fibs" around globally. My guess
> was:
>
> (defn fib [n]
> (let [fibs2 (lazy-cat '(0 1) (map + fibs2 (drop 1 fibs2)))]
> (nth fibs2 n)))
>
> But this yields "Unable to resolve symbol: fibs2 in this context", so
> let doesn't allow being self-referential the way def does.

This is not self-referential, but mutually referential - fibs2 is a
sequence, the result of a call to an anonymous function which refers
to that sequence via fibs2.

There is no local mutual reference (i.e. letrec) in Clojure at
present, short of the Y combinator:

http://groups.google.com/group/clojure/browse_frm/thread/3259f09e08be4cfd/21f0e19fdce15ae9

>I don't
> quite understand why the second arg to lazy-cat is being evaluated in
> the first place. Shouldn't evaluation be delayed until needed?
>

The evaluation is delayed, but the name resolution isn't.

Rich