[racket] Making a Racket function "recallable"

[Joe Gilray]

Warning: extreme newbie question ahead.

I wrote the following fibonacci function:

; function that returns the next fibonacci number each time it is called

; invoke as (fib)

(define fib

  (let ([n0 -1] [n1 1])

    (lambda ()

      (let ([next (+ n0 n1)])

        (set! n0 n1)

        (set! n1 next))

      n1)))

This function works, but is not "recallable" (is there a better word?).  In other words I cannot do the following:

(define f1 fib)

(define f2 fib)

(f1) (f1) (f2) ...

and have f1 and f2 be separate fibonacci lists.  Somehow n0 and n1 have to be instance-specific and right now they are not.

Because of this limitation the following useful looking function only works the first time it is called:

; function that returns a list of fibonacci numbers less than the passed argument

(define (fib-less-than-n n)

  (let ([fib-val (fib)])

    (if (>= fib-val n) '() (cons fib-val (fib-less-than-n n)))))

Any help appreciated.  Any tips about stupidities in the code above welcome too!

Thanks,

-Joe

[Danny Yoo]

On Mon, Feb 13, 2012 at 11:52 PM, Joe Gilray <jgi...@gmail.com> wrote:
> Warning: extreme newbie question ahead.
>
> I wrote the following fibonacci function:
>
> ; function that returns the next fibonacci number each time it is called
> ; invoke as (fib)
> (define fib
>   (let ([n0 -1] [n1 1])
>     (lambda ()
>       (let ([next (+ n0 n1)])
>         (set! n0 n1)
>         (set! n1 next))
>       n1)))

One thing you can do is turn fib into a "sequence", and then from a
sequence into a stream that knows how to remember its previous values.

Here's what it might look like:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
#lang racket
(require racket/sequence)

(define fib
(let ([n0 -1] [n1 1])
(lambda ()
(let ([next (+ n0 n1)])
(set! n0 n1)
(set! n1 next))
n1)))

(define fib-stream
;; Here's a sequence of the function:
(let ([fib-sequence (in-producer fib 'donttellmecauseithurts)])

;; Let's wrap it and turn it into a stream that remembers...
(sequence->stream fib-sequence)))

;; Ok, we've got a stream. Let's look at its first few elements.
(define (peek-fibs n)
(for ([elt fib-stream]
[i (in-range n)])
(displayln elt)))

(peek-fibs 10)
(printf "-----\n")
(peek-fibs 20)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

____________________
Racket Users list:
http://lists.racket-lang.org/users

[Erik Silkensen]

Another option is you could turn change your fib function to be 'mk-fib' that returns a new instance of the fib function each time it's called:

(define (mk-fib)

(let ([n0 -1] [n1 1])
(lambda ()
(let ([next (+ n0 n1)])
(set! n0 n1)
(set! n1 next))
n1)))

- Erik

[Danny Yoo]

>  (let ([fib-sequence (in-producer fib 'donttellmecauseithurts)])

I realize that I forgot to add explanation.

This line creates a "sequence" by repeatedly calling your fib
function. in-producer will continue to call fib until it sees the
second argument. But since the fibonacci numbers don't end, I want to
tell in-producer to go on forever, so I passed it something that fib
won't ever produce.

... and It's from a song by the music group No Doubt. Why? Dunno.
Valentine's Day brought it to mind for some reason. :)

The second part:

;; Let's wrap it and turn it into a stream that remembers...
(sequence->stream fib-sequence)

turns the sequence into another sequence. But this one will remember
its previous values as we walk across it.

So when we do start walking the streamified sequence, we can do that
repeatedly without losing the old values.

[Joe Gilray]

Danny,

Thanks for the explanations.  These are powerful ideas.  It appears not to generate the sequence until needed, very nice.

How could I modify this to do the "less than n" idea?

-joe

[Joe Gilray]

Erik,

Intriguing idea and it works "flat", but if I write the following I end up with an infinite loop:

(define (fib-less-than-n n)

  (let ([f1 (mk-fib)])

    (let ([fib-val (f1)])

      (if (>= fib-val n) '() (cons fib-val (fib-less-than-n n))))))

How would I use your idea in this case?

thanks!

-joe

[Erik Silkensen]

Instead of calling fib-less-than-n recursively, you could add a loop inside, for example something like,

(define (fib-less-than-n n)

  (define fib (mk-fib))

  (let loop ([vs '()])

    (let ([fib-val (fib)])

      (if (>= fib-val n)

          (reverse vs)

          (loop (cons fib-val vs))))))

- Erik

[Danny Yoo]

On Tue, Feb 14, 2012 at 12:32 AM, Joe Gilray <jgi...@gmail.com> wrote:
> Danny,
>
> Thanks for the explanations.  These are powerful ideas.  It appears not to
> generate the sequence until needed, very nice.
>
> How could I modify this to do the "less than n" idea?

A stream is a sequence, and also has a few more functions that act
very much like the familiar list-oriented functions.

http://docs.racket-lang.org/reference/streams.html#(tech._stream)

So you could use stream-first and stream-rest on the fib-stream, as if
you had entire fibonacci sequence in front of you as an infinite list.
Just don't try to stream->list it.

[Joe Gilray]

Thanks Erik.  Very nice!  Although I miss the recursion.

please help me understand how this works, especially (let loop ([vs '()]). What exactly is going on there?

Thanks again,

-joe

[Joe Gilray]

Thanks Danny,

Now I can use the original recursive formulation:

; function to use the fib-stream to generate a list of all fibs < n

(define (fib-stream-less-than-n n)

  (let ([fib-val (stream-first fib-stream)])

    (if (>= fib-val n) '() (cons fib-val (fib-less-than-n n)))))

I've learned a lot tonight.  I have been reading the manuals, but they are hard to get your arms around when you are just starting out. Also it would be great if the manuals had more and longer examples.  Have anyone looked into doing a Racket "cookbook"?

Thanks again,

-Joe

[Erik Silkensen]

Sure, sounds good.

The (let loop ([vs '()]) ...) is a 'named let' (http://docs.racket-lang.org/guide/let.html?q=named%20let#(part._.Named_let)) which as the guide says is equivalent to (letrec ([loop (lambda (vs) ...)]) (loop '()) --- so 'loop' is a recursive function that we're using to iterate until (fib) is >= n, accumulating the values in the vs argument.  If you're not familiar with letrec, another definition would be

(define (fib-less-than-n n)

  (define fib (mk-fib))

  (define (loop vs)

    (let ([fib-val (fib)])

      (if (>= fib-val n)

          (reverse vs)

          (loop (cons fib-val vs)))))

  (loop '()))

Thinking of loops as just a form of recursion can be a little strange at first.  There's more information in the Racket guide here- http://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html or another page to check out might be http://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html. 

Hope this helps,

- Erik

[Stephen Bloch]

On Feb 14, 2012, at 12:18 AM, Erik Silkensen wrote:

Another option is you could turn change your fib function to be 'mk-fib' that returns a new instance of the fib function each time it's called:

(define (mk-fib)
 (let ([n0 -1] [n1 1])
   (lambda ()
     (let ([next (+ n0 n1)])
       (set! n0 n1)
       (set! n1 next))
     n1)))

I frequently assign this sort of thing near the end of a first programming course.  First, I have students write a function "next" which returns how many times it's been called.  Then "next-color", which on successive calls returns "red", "orange", "yellow", "green", "blue", "violet", #f, #f, ...  Then "make-lister", which on input (list "red" "orange" "yellow" "green" "blue" "violet") returns a function acting like "next-color".

One suggestion: I would have mk-fib take in two parameters specifying the initial values of fib, rather than always making them -1 and 1.

Stephen Bloch

sbl...@adelphi.edu

[Stephen Bloch]

On Feb 14, 2012, at 12:51 AM, Erik Silkensen wrote:

Instead of calling fib-less-than-n recursively, you could add a loop inside, for example something like,

(define (fib-less-than-n n)

  (define fib (mk-fib))

  (let loop ([vs '()])

    (let ([fib-val (fib)])

      (if (>= fib-val n)

          (reverse vs)

          (loop (cons fib-val vs))))))

Let's generalize and abstract this to "take-while":

(define (take-while generator test?)

   (reverse

      (let loop [[vs '()]]

         (let [[value (generator)]]

            (if (test? value)

                (loop (cons value vs))

                vs)))))

(define (fib-less-than-n n)

   (take-while (mk-fib) (lambda (value) (< value n))))

[I haven't typed this code in and tested it, so there may be typos.]

Stephen Bloch

sbl...@adelphi.edu

[Stephen Bloch]

On Feb 13, 2012, at 11:52 PM, Joe Gilray wrote:

This function works, but is not "recallable" (is there a better word?).  In other words I cannot do the following:

(define f1 fib)

(define f2 fib)

(f1) (f1) (f2) ...

and have f1 and f2 be separate fibonacci lists.

This is the impulse motivating the historical shift from imperative to object-oriented programming.  Whenever you have one or more functions that share mutable state, ask yourself whether one might ever conceivably want more than one instance of that state.  Look at your favorite 40-year-old Fortran, BASIC, or Pascal program: odds are that a bunch of different procedures all operate on the same global data.  If, for some reason, you needed two instances of all of this, you'd need to duplicate all the procedures and the global variables, which is a Royal Pain.  One solution is to have each procedure take the relevant data as parameters (by reference, so they can be mutated), and that works as long as there aren't too many different chunks.  I recall writing, as an undergraduate, an OS simulation in which every function took about fifteen parameters, because the teacher had decreed "no global variables".  In retrospect, I should have packaged them up into a record/struct, which would not only make the code cleaner and less error-prone but also make it easy to simulate multiple instances of the OS.

Stephen Bloch

sbl...@adelphi.edu

[Joe Gilray]

The code that Danny wrote to create fib-stream works great with his peek-fibs function, but I really don't understand stream-first.

I wrote:

; function to use the fib-stream to generate a list of all fibs < n

(define (fib-stream-less-than-n n)

  (let ([fib-val (stream-first fib-stream)])

    (if (>= fib-val n) '() (cons fib-val (fib-less-than-n n)))))

I get:

(fib-stream-less-than-n 500)

'(0 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377)

Note the two leading 0s.  This perplexed me, until I read about stream-first then I realized that I really didn't understand anything.  I believe the function above should return

'(0 0 0 0 0 0 0 ...)

Can someone tell me what is going on?

Thanks,

-Joe

[Danny Yoo]

On Wed, Feb 15, 2012 at 3:10 AM, Joe Gilray <jgi...@gmail.com> wrote:
> The code that Danny wrote to create fib-stream works great with his
> peek-fibs function, but I really don't understand stream-first.
>
> I wrote:
>
> ; function to use the fib-stream to generate a list of all fibs < n
> (define (fib-stream-less-than-n n)
>   (let ([fib-val (stream-first fib-stream)])
>     (if (>= fib-val n) '() (cons fib-val (fib-less-than-n n)))))

^^^^^^^^^^^^^^^^

Are you sure you mean to use fib-less-than-n here?

[Danny Yoo]

> I've learned a lot tonight.  I have been reading the manuals, but they are
> hard to get your arms around when you are just starting out. Also it would
> be great if the manuals had more and longer examples.  Have anyone looked
> into doing a Racket "cookbook"?

Some of the documentation is meant to be reference, but other docs are
approachable as tutorials. The ones listed here:

http://docs.racket-lang.org/getting-started/index.html

use extended examples that should be straightforward. I'd go at the
"Quick", "More", and "Continue" tutorials there.

I have some ideas for more documented guides through Racket... but I
have to graduate or get kicked out first. :) I've written a guide
about one way to apply the language extension features in Racket:
(http://hashcollision.org/brainfudge/index.html)

I think there's supposed to be something about "Realm of Racket"
(http://realmofracket.com/), but they've been very hush-hush.

[Joe Gilray]

Danny is correct... ouch (/.\ <- covering my head in shame).

Anyway to close the chapter on this, below is the final result using Danny's stream suggestions/code.  I also have a non-streams version thanks to Erik (and Stephen and Joshua).

-Joe

#lang racket

(require racket/sequence)

; a sequence function that creates an "infinite" sequence then turns that into a stream that remembers its previous values as we walk across it.

; invoke in a loop-expr (see below)

(define fib-stream

  (let ([fib-sequence (in-producer (fib) 'donttellmecauseithurts)])

    (sequence->stream fib-sequence)))

; function to generate a list of all values in a stream < n

(define (stream-less-than-n n strm)

  (let ([fib-val (stream-first strm)])

    (if (>= fib-val n) '() (cons fib-val (stream-less-than-n n (stream-rest strm))))))

[Phil Bewig]

You might be interested in SRFI-41. One of the examples is an infinite stream of fibonacci numbers.

[Eli Barzilay]

Two days ago, Phil Bewig wrote:
> You might be interested in SRFI-41

> <http://srfi.schemers.org/srfi-41/>. One of the examples is an

> infinite stream of fibonacci numbers.

Or in lazy racket, where that example becomes very clear:

#lang lazy
(define fibs (list* 1 1 (map + fibs (cdr fibs))))

--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://barzilay.org/ Maze is Life!