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.

Answer 1

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

Answer 2

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

Answer 3

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)

Answer 4

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)