StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I have written few variants. First you ask if</p> <pre><code>(define (each-fib fn) (letrec ((next (lambda (a b) (fn a) (next b (+ a b))))) (next 0 1))) </code></pre> <p>can be written any shorter. The pattern is used so often that special syntax called <code>named let</code> has been introduced. Your function looks like this using a named let:</p> <pre><code>(define (each-fib fn) (let next ([a 0] [b 1]) (fn a) (next b (+ a b)))) </code></pre> <p>In order to get the control flowing from one function to another, one can in languages with supports TCO use continuation passing style. Each function gets an extra argument often called k (for continuation). The function k represents what-to-do-next.</p> <p>Using this style, one can write your program as follows:</p> <pre><code>(define (generate-fibs k) (let next ([a 0] [b 1] [k k]) (k a (lambda (k1) (next b (+ a b) k1))))) (define (count-down n k) (let loop ([n n] [fibs '()] [next generate-fibs]) (if (zero? n) (k fibs) (next (λ (a next) (loop (- n 1) (cons a fibs) next)))))) (count-down 5 values) </code></pre> <p>Now it is a bit annoying to write in style manually, so it could be convenient to introduce the co-routines. Breaking your rule of not using <code>set!</code> I have chosen to use a shared variable <code>fibs</code> in which <code>generate-fibs</code> repeatedly conses new fibonacci numbers onto. The <code>count-down</code> routine merely read the values, when the count down is over.</p> <pre><code>(define (make-coroutine co-body) (letrec ([state (lambda () (co-body resume))] [resume (lambda (other) (call/cc (lambda (here) (set! state here) (other))))]) (lambda () (state)))) (define fibs '()) (define generate-fib (make-coroutine (lambda (resume) (let next ([a 0] [b 1]) (set! fibs (cons a fibs)) (resume count-down) (next b (+ a b)))))) (define count-down (make-coroutine (lambda (resume) (let loop ([n 10]) (if (zero? n) fibs (begin (resume generate-fib) (loop (- n 1)))))))) (count-down) </code></pre> <p>And a bonus you get a version with communicating threads:</p> <pre><code>#lang racket (letrec ([result #f] [count-down (thread (λ () (let loop ([n 10] [fibs '()]) (if (zero? n) (set! result fibs) (loop (- n 1) (cons (thread-receive) fibs))))))] [produce-fibs (thread (λ () (let next ([a 0] [b 1]) (when (thread-running? count-down) (thread-send count-down a) (next b (+ a b))))))]) (thread-wait count-down) result) </code></pre> <p>The thread version is Racket specific, the others ought to run anywhere.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload