#lang racket #| CSC 324 - 2017 Fall - Lab Week 7 |# #| Streams Streams are a datatype for iterable data. As an abstract datatype they have only three list-like or iterator-like operations: Empty? : stream → boolean First : stream → any Rest : stream → stream Many languages have stream libraries, for example Java 8 has streams meant to be used in a functional programming style along with Java 8's new support of anonymous functions. Here's the Java SDK API summary for Package java.util.stream: "Classes to support functional-style operations on streams of elements, such as map-reduce transformations on collections." Here's their tutorial: https://docs.oracle.com/javase/tutorial/collections/streams/ In this lab you'll play with a general implementation of streams as lazy lists. |# #| Lazy Lists A lazy list is built on-demand, delaying the evaluation of its elements. As a small simplification, we'll delay only the evaluation of the tail of the list, i.e. the result of Rest, but not the current element, i.e. the result of First. This will still demonstrate the main significance of the lazy evaluation. A lazy list will either be: Empty, represented by the empty list. A pair containing: • the first element • a function to call to produce the rest of the list |# ; Constructor. (define-syntax-rule (List* e LL) (list e (λ () LL))) ; API. (define Empty? empty?) (define First first) (define (Rest LL) ((second LL))) ; ★ Write out the compile-time expansion of each of these expressions: (List* 1 '()) (List* 1 (List* 2 '())) (define LL.0 (List* 1 (List* 2 (List* (/ 1 0) '())))) ; ★ Predict the result of each of these expressions. ; For λs, write out the λ expression instead of racket's black-boxed "#". ; Algebraically trace as many intermediate steps as you find helpful, but include at least each pair ; of steps showing a call of (λ () ). #;(First LL.0) (define LL.1 (Rest LL.0)) #;(First LL.1) #;(Rest LL.1) #| Infinite Lists Lazy lists allow easily building datastructures that behave like infinite lists. |# (define 324s (List* 324 324s)) ; ★ Write out the compile-time expansion of that definition. ; ★ Predict the result of the following expression. ; Write out the intermediate steps, but hide the steps in the body of Rest. #;(First (Rest (Rest 324s))) ; That behaves like an infinite list of 324s. #| Core Functional Programming Operations, on Streams Most of the common functional programming operations on lists generalize to streams. |# (define (Map f LL) (cond [(Empty? LL) LL] [else (List* (f (First LL)) (Map f (Rest LL)))])) ; ★ Write out the compile-time expansion of that definition. (define N (List* 0 (Map add1 N))) ; ★ Write out the compile-time expansion of that definition. ; ★ Predict the result of each of these expressions. ; Write out the intermediate steps, but hide the steps in the body of Rest. (define N.1 (Rest N)) (define N.2 (Rest N.1)) #;(First N.2)