(stream-generate first done? step final)

;; a stream first element (final first)

;; next element (final (step first))

;; next element (final (step (step first)))

;; and so on up to but not including the

;; element e such that (done? e) is true

(list->stream l)

(stream->list s)

;; consumes a list, returns equivalent stream

;; consumes a stream, produces equivalent list

;; examples

(define s (list->stream (list 1 2 3)))

(stream-car s)

(stream-empty? s)

(stream-car (stream-cdr (stream-cdr s)))

(stream-empty? (stream-cdr (stream-cdr (stream-cdr s)))) ;; true

(stream->list s)

(stream->list (stream-generate -3 zero? add1 sqr))

The running time of stream-car and stream-cdr is O(f(n)+g(n)+h(n)) where f(n), g(n) and h(n) are the running times of done?, final and step, respectively. The running time of stream-cons is O(1) .

Implement a module streaming.rkt that requires stream.rkt and provides a function (stream-map fn s) that computes the same result as (list->stream (map fn (stream->list s))). The running time of stream-map must be O(f(n)+g(n)) where f(n) is the running time of fn, and g(n) is the running time of a single stream             operation, as detailed above . The O() running time of the other stream operations must remain unchanged .

Problem A9b. Files: main.rkt and total-order.rkt in a zip file

For the remaining problems in this assignment you will use ordered set ADT ordered-set.rkt and stream            stream.rkt implementations which are supplied to you . You will not modify ordered-set.rkt or stream.rkt but you will modify total-order.rkt (which is required by ordered-set.rkt) as necessary, and also supply a file main.rkt that implements the functions specified below. Here is a trivial Scheme program that exercises

ordered-set .rkt . Use full Racket (#lang racket) to solve these problems, but use only language features from Intermediate Student with Lambda .

To submit your files to Marmoset, you must combine them using zip. For example, to submit total-order.rkt and also main.rkt, execute the following command:

zip submit.zip main.rkt total-order.rkt

then submit submit.zip to Marmoset . Make sure your zip file contains exactly these two files -- not a folder containing these two files .

Write a function count that consumes a stream of numbers, not necessarily unique . Your function should produce a new stream of pairs, represented by lists with two elements . The first member of each pair should be a number from the input stream, in ordered correspondence; the second member should be the number of times that            number has occurred previously in the stream . For example,

(stream->list (count (list->stream '(3 9 3 4 9 3 7))))

;; (list (list 3 0) (list 9 0) (list 3 1) (list 4 0)

;;        (list 9 1) (list 3 2) (list 7 0))

You must use ordered-set.rkt and stream.rkt to solve this problem; you may not use lists, structs, or any

other data structure to store the set of numbers .

The running time of count must be O(1), and the running time for all operations on the resulting stream must be O(log n) where n is the size of the input stream .

Problem A9c. Files: scoreboard.rkt and total-order.rkt

In games of chance like poker, players may win or lose money. When Lisa wins $100, we may represent this event by the pair

(list 'Lisa 100)

When Bob loses $50, we may represent this event by the pair

(list 'Bob -50)

That is, each event is represented by a pair with a symbol representing the player's name as its first element, and the amount of the win or loss as the second element, where a loss is negative . After a number of events, a          player's total winning is the sum of all of his or her wins and losses .

The various wins and losses in a poker tournament may be represented as a chronologically ordered stream of   events . A scoreboard may be represented as a chronologically ordered stream of quadruples, in ordered             correspondence with the events, recording the player's name, the amount of the player's win or loss, the player's total winning up to and including the event, and the name of the player with the highest total winning up to and including the event .

For example, consider the following tournament:

(list->stream

(list

(list 'Lisa 100)

(list 'Bob -50)

(list 'Mel 20)

(list 'Lisa -90)

(list 'Mel -50)))

The corresponding scoreboard is:

(list->stream

(list

(list 'Lisa 100 100 'Lisa)

(list 'Bob -50 -50 'Lisa)

(list 'Mel 20 20 'Lisa)

(list 'Lisa -90 10 'Mel)

(list 'Mel -50 -30 'Lisa)))