Racket: Stream negative and ith element problem

Question

I have two Racket programming homework questions:

The first one: Write a function kth-item that takes two arguments, the first is a stream s and the second is a number k, and it produces the result of extracting k elements from the stream, returning only the last element. Very similar to the previous one, but only returns a single element. You may assume k is greater than 0.

The second one: Write a stream negate-2-and-5 that is like the stream of natural numbers (i.e., 1, 2, 3, ...) except that numbers divisible by 2 or 5 are negated (i.e., 1, -2, 3, -4, -5, -6, 7, -8, 9, -10, 11, -12, 13, -14, ...). Remember a stream is a thunk that when called produces a pair, where the car of the pair is the next number and the cdr will be the continuation of the stream.

For first questions I know how to get the list of ith but I have not idea how to continues to get the last element.

For second questions, I know how to get either 2 or 5 works, but I have not idea how to combine them, so both 2 and 5 can work at the same time.

(define (next-k-items s k)
  (if (<= k 0)
      empty
      (cons (car (s))
            (next-k-items (cdr (s)) (- k 1)))))


(define (negate-2-and-5)
  (define (f x) (cons (if (= 0 (remainder x 5)) (- x) x)
                      (lambda () (f (+ x 1)))))
  (f 1))

Here are the testing codes:

(check-expect (kth-item nats 3) 3)

(check-expect (next-k-items negate-2-and-5 7) '(1 -2 3 -4 -5 -6 7))

Atharva Shukla Atharva Shukla · Accepted Answer · 2019-05-21T06:52:16

(require racket)

Streams can be thought of as infinite lists where the cdr is wrapped in a thunk (lambda with no arguments)

(define-syntax-rule (cons-stream x y)
  (cons x (lambda () y)))

To make it easier to operate on streams, we define the following interface:

(define stream? pair?)
(define null-stream null)
(define null-stream? null?)
(define stream-first car)
(define (stream-rest s) ((cdr s)))

A stream can be made using a self reference:

(define ones (cons-stream 1 ones))

We can define map(s) on streams:

(define (stream-map f s)
  (if (null-stream? s)
      null-stream
      (cons-stream (f (stream-first s))
                   (stream-map f (stream-rest s)))))

(define (stream-map2 f s1 s2)
  (if (null-stream? s1)
      null-stream
      (cons-stream (f (stream-first s1) (stream-first s2))
                   (stream-map2 f (stream-rest s1)
                                (stream-rest s2)))))

... and use it to make a nats stream:

(define nats (cons-stream 1 (stream-map2 + ones nats)))

Function you want can be cleanly defined using the above functions:

;; Stream Number -> Number
;; the kth item of s
(define (kth-item s k)
  (if (= k 1)
      (stream-first s)
      (kth-item (stream-rest s) (sub1 k))))


(check-expect (kth-item nats 1) 1)
(check-expect (kth-item nats 2) 2)
(check-expect (kth-item nats 3) 3)

In your code, (s) is not correct because s is not a lambda. We need to cons the first element (car s) and force the rest of the stream ((cdr s)). This is taken care of by stream-first and stream-rest.

;; Stream Number -> Stream
;; builds a list of first k items of s
(define (next-k-items s k)
  (if (= k 0)
      empty
      (cons (stream-first s)
                   (next-k-items (stream-rest s) (- k 1)))))

(check-expect (next-k-items nats 10) '(1 2 3 4 5 6 7 8 9 10))

The definition of map proves useful again:

;; Stream -> Stream
;; negates the multiples of 2 and 5
(define (negate-2-and-5 s)
  (stream-map (λ (x) (if (or (zero? (modulo x 2))
                             (zero? (modulo x 5)))
                         (* -1 x)
                         x))
              s))

... and next-k-items

(check-expect (next-k-items (negate-2-and-5 nats) 7) '(1 -2 3 -4 -5 -6 7))

Racket: Stream negative and ith element problem

1 Answers