infinite sequence scheme to make infinite sequence

Question

I have a project in scheme in which I need to implement an infinite sequence of numbers. I can't use any scheme-built-in complex functions, and I just do not know how to make my sequence infinite without program crashing in infinite loop. I don't have to really output it, but I need to be able to use it.

(seq n)   ;;output: n,n+1,n+2,n+3.... to infinity (seq 5) ->5,6,7,8,9...

Right now I did a sequence until n+7, but I need this to infinity:

(define (seq n)
   (define (asc-order LIST counter)
     (cond ((= counter (+ n 7)) LIST)
           (else (asc-order (append LIST (cons (+ counter 1) '()))  
           (+ counter 1)))))
(asc-order '() (- n 1))
)

IO example (It works, but I need it infinite sequence):

>(define s (seq 3)) 
>(car s)   
3

score 3 · Answer 1 · answered Jan 05 '17 at 11:36

You can represent an infinite sequence as a function that produces one element at a time. The user (consumer) can then call the function each a new element of the sequence is needed.

An example:

(define (f x) (* x x))

(define seq
  (let ()
    (define n 0)        ; current index
    (lambda ()          ; the function that is to be called repeatedly
      (define a (f n))  ;   compute the new element
      (set! n (+ n 1))  ;   compute new index
      a)))              ;   return the new element

(seq)  ; compute element 0
(seq)  ; compute element 1
(seq)  ; ...
(seq)
(seq)
(seq)

This evaluates to:

In order to write (sequence->list s n) which computes the first n elements of the sequence s, make a loop that calls s in total n times - and collect the results in a list.

Thanks @soegaard, but as i mentioned I'm not allowed to use built-in non-primitive functions, particaularly set! — mooly, Jan 05 '17 at 13:21

score 1 · Answer 2 · answered Jan 06 '17 at 15:21

The key is to delay evaluation of the list by wrapping a procedure around it.

Here's the simplest implementation I can think of.
It's only "lazy" in the tail.

(define (seq n)
  (cons n (lambda () (seq (+ n 1)))))

(define (seq-car s)
  (car s))

(define (seq-cdr s)
  ((cdr s)))

Example use:

; Get the 'n' first elements of 's'.
(define (seq-take n s)
  (if (<= n 0)
      '()
      (cons (seq-car s) (seq-take (- n 1) (seq-cdr s)))))


> (define s (seq 10))
> s
'(10 . #<procedure>)
> (seq-take 5 s)
'(10 11 12 13 14)

a common mistake in `take` implementation is to over-produce by 1. for n=1 there's no need to force the tail, which might diverge, too. :) — Will Ness, Jan 06 '17 at 22:17

score 0 · Answer 3 · answered Jan 06 '17 at 11:13

Here is another solution using delayed evaluation:

(use-modules (ice-9 receive))


(define (seq f)
  (let loop ((n 0))
    (lambda ()
      (values (f n) (loop (1+ n))))))


(define squares (seq (lambda (x) (* x x))))

(receive (square next) (squares)
  (pk square) ;; => 0
  (receive (square next) (next)
    (pk square) ;; => 1
    (receive (square next) (next)
      (pk square) ;; => 4
      (receive (square next) (next)
        (pk square))))) ;; => 9

infinite sequence scheme to make infinite sequence

3 Answers3