What's the equivalent of Clojure's iterate function in Racket

Question

I'm playing with Racket today, and trying to produce an indefinite sequence of numbers based on multiple applications of the same function.

In Clojure I'd use the iterate function for this, but I'm not sure what would be the equivalent in Racket.

Morality

Answer 1

In most situations you can replace the use of iterate with for/fold.

> (define (mult2 x) (* x 2))

> (for/fold ([x 1])   ; the initial value of x is 1
            ([i 8])   ; count i=0,...,7
   (mult2 x))         ; put x = (mult2 x)
256

The advantage of for/fold is that you can iterate more variables at a time:

(define (mult2 x) (* x 2))
(define (div2 x)  (/ x 2))

(for/fold ([x 1]        ; bind x to 1
           [y 1])       ; bind y to 1
          ([i 8])       ; i=0,...,7
  (values (mult2 x)     ; put x = (mult2 x)
          (div2  y)))   ; put y = (div2 y)

This will return two values: 256 and 1/256.

Collecting elements are easy. Here is the Fibonacci example:

(for/fold ([fs '(1)]     ; list of fibonacci numbers generated so far
           [f1   1]      ; a fibonacci number
           [f2   1])     ; the following fibonacci number
          ([i   10])     ; i = 0,...,9
  (values (cons f2 fs)   ; cons the new fibonacci number to the list fs
          f2             ; put f1 = (the old) f2
          (+ f1 f2)))    ; put f2 = (the old) f1+f2

The result consists of three values:

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

Skaggs

Also - expect for/fold to be more faster than stream. – Skaggs

Well, of course eager comprehensions are much more lightweight than streams. ;-) I should actually write an in-iterate sequence generator that can be used directly with for comprehensions. – Conference

@ChrisJester-Young That is a nice idea. – Skaggs

I've posted my in-iterate as a new answer. What I like about it is that it handles multiple values without making the user do funky argument packing and unpacking (unlike Óscar's answer and my initial answer). Actually, I'd like to see that become part of Racket's standard library someday...(my code is released under "public-domain-style" CC0, use freely with or without attribution). – Conference

Answer 2

SRFI 41 ((require srfi/41)) provides stream-iterate directly.

You can use Óscar's examples and substitute stream-iterate wherever you see iterate, without having to define your own iterate. In addition, you can simulate Clojure's parameter destructuring using match-lambda:

(require srfi/41)
(define fib
  (stream-map first
              (stream-iterate (match-lambda
                                ((list a b)
                                 (list b (+ a b))))
                              '(0 1))))
(stream->list 10 fib)  ; => (0 1 1 2 3 5 8 13 21 34)

Conference

Answer 3

There's no direct equivalent within the built-in Racket procedures, but we can implement something with a similar functionality using streams. Try this:

(define (stream-take m s)
  (if (zero? m)
      '()
      (cons (stream-first s)
            (stream-take (sub1 m) (stream-rest s)))))

(define (iterate f x)
  (stream-cons x (iterate f (f x))))

For instance, here's how the examples from the Clojure documentation would look like in Racket:

(stream-take 5 (iterate add1 5))
=> '(5 6 7 8 9)

(stream-take 10 (iterate (curry + 2) 0))
=> '(0 2 4 6 8 10 12 14 16 18)

(define powers-of-two (iterate (curry * 2) 1))
(stream-ref powers-of-two 10)
=> 1024
(stream-take 10 powers-of-two)
=> '(1 2 4 8 16 32 64 128 256 512)

(define fib
  (stream-map first
              (iterate (lambda (pair)
                         (list (second pair)
                               (+ (first pair) (second pair))))
                       '(0 1))))
(stream-take 10 fib)
=> '(0 1 1 2 3 5 8 13 21 34)

Ealasaid

Answer 4

Based on soegaard's idea to use eager comprehensions, here's an in-nest-sequence sequence generator (also available on Code Review and as a Gist):

#lang racket
(require (for-syntax unstable/syntax))
(provide (rename-out [*in-nest-sequence in-nest-sequence]))

(define in-nest-sequence
  (case-lambda
    [(func init)
     (make-do-sequence
      (thunk (values identity func init #f #f #f)))]
    [(func . inits)
     (make-do-sequence
      (thunk (values (curry apply values)
                     (lambda (args)
                       (call-with-values (thunk (apply func args)) list))
                     inits #f #f #f)))]))

(define-sequence-syntax *in-nest-sequence
  (lambda () #'in-nest-sequence)
  (lambda (stx)
    (syntax-case stx ()
      [[(x ...) (_ func init ...)]
       (unless (= (syntax-length #'(x ...)) (syntax-length #'(init ...)))
         (raise-syntax-error 'in-nest-sequence
                             (format "~a values required" (syntax-length #'(x ...)))
                             stx #'(init ...)))
       (with-syntax ([for-arity (syntax-length #'(init ...))]
                     [(value ...) (generate-temporaries #'(init ...))]
                     [(y ...) (generate-temporaries #'(init ...))])
         #'[(x ...) (:do-in ([(f) func])
                            (unless (procedure-arity-includes? f for-arity)
                              (raise-arity-error f (procedure-arity f) init ...))
                            ([value init] ...)
                            #t
                            ([(x ...) (values value ...)]
                             [(y ...) (f value ...)])
                            #t
                            #t
                            (y ...))])])))

Sequences generated by in-nest-sequence do not terminate, so you will want to pair it with either a sequence that does, or a #:break or similar termination condition. For example (using the powers-of-two example in Óscar's answer):

;; first ten powers of 2
(for/list ((_ (in-range 10))
           (x (in-nest-sequence (curry * 2) 1)))
  x)
; => (1 2 4 8 16 32 64 128 256 512)

;; powers of 2 above 10,000 and below 1,000,000
(for/list ((x (in-nest-sequence (curry * 2) 1))
           #:when (> x 10000)
           #:break (> x 1000000))
  x)
; => (16384 32768 65536 131072 262144 524288)

;; first power of 2 above 10,000,000
(for/first ((x (in-nest-sequence (curry * 2) 1))
            #:when (> x 10000000))
  x)
; => 16777216

And here's the Fibonacci sequence example:

;; first ten Fibonacci numbers
(for/list ((_ (in-range 10))
           ((x y) (in-nest-sequence (lambda (a b) (values b (+ a b))) 0 1)))
  x)
; => (0 1 1 2 3 5 8 13 21 34)

;; first Fibonacci number above 10,000,000
(for/first (((x y) (in-nest-sequence (lambda (a b) (values b (+ a b))) 0 1))
            #:when (> x 10000000))
  x)
; => 14930352

Conference

Can't wait to see the define-sequence-syntax version too :-) – Skaggs

That looks great, though I'm going to take a bit of time to digest it. I'm very much a Racket n00b. – Morality

@Morality There's no really easy way to digest in-* implementations; they're written using a special domain-specific language (whether that's make-do-sequence as I used, or define-sequence-syntax as soegaard suggested). But if you like to learn something new, it'll definitely serve that purpose! – Conference

As for the usage of in-iterate, that's easier. For the one-argument case (the (curry * 2) example above, which by the way is the same as (lambda (x) (* 2 x))), that should be pretty straightforward. The two-argument case just extends the concept (and the function you pass in) to use two arguments, and two return values. – Conference

@Skaggs I wrote a first cut of a define-sequence-syntax version. I'm a total noob at this, though, so I welcome any critique you have! (Actually, I should post this to Code Review Stack Exchange and see what feedback I get. :-P) – Conference