Cvičení 10
------------------
- připomenout makro delay a force
Naivní implementace delay (obalení lambdou bez parametrů):
    (define-macro delay
        (lambda (x)
            `(lambda () ,x)))

Skutečná implementace si musí pamatovat výsledek vyhodnocení, takže daná lambda se spočítá nejvýše jednou. Ve schemeu delay vrací nový element #promise (příslib)

Procedura (naivní) force spouští výpočet přílibu typu #promise
    (define force
        (lambda (promise)
            (promise)))

Př:        
    (define hard-computation (delay (+ 3 2)))
    (force hard-computation) => 5

Pozor na vedlejší efekt (vyhodnotí se jenom jednou)!
----------------------------------------------------

    (define a 5)
    (define hc (delay (begin (set! a (+ a 1)) a)))
    (force hc) => 6
    (force hc) => 6 !!
    (force hc) => 6 !!
    ...    

Využití:
    - "zhmotnění" výpočtu - můžeme s výpočtem nakládat jako s daty
    - odložení (potenciálně náročného) výpočtu na později (ideálně pokud je nízká pravděpodobnost jeho spuštění)
        - počítáme až je potřeba
    - streamy

Streamy:
--------
    - seznamy, jejichž druhý prvek páru je vždy příslib nebo '()
    Def( stream ):
        (I)  null je stream
        (II) (a . b), kde b je stream

    - Knihovny na práci se streamy:
        - buď (require racket/stream) - vestavěná v racketu (není tolik vybavená)
            - procedury se v ní nejmenují moc očekávatelně
        - nebo http://phoenix.inf.upol.cz/~procpa01/files/vyuka/papr2/stream.ss
            - napsané podle přednášek (doporučuji, příklady budou podle ní)

Důležitá makra:
---------------

(define-macro cons-stream
  (lambda (a b)
    `(cons ,a (delay ,b))))

(define stream-car car)

(define stream-cdr
  (lambda (stream)
    (force (cdr stream))))

Pozn: knihovna obsahuje stejné procedury jako znáte pro seznamy, obvykle mají prefix stream- (nebo suffix -stream)

Př:
  (define s (cons-stream 1 (cons-stream 2 (cons-stream 3 '()))))
  (stream-car s) => 1
  (stream-cdr s) => (2 . #<promise:unsaved-editor312:13:27>)

  (display-stream s) =>
  1
  2
  3

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

  (stream-length s)
  3

  Pozor!:

  (stream-map (lambda (x) (* x x)) s)
  (1 . #<promise:unsaved-editor618:54:8>)

  (define stream-map
    (lambda (f . streams)
      (if (stream-null? (car streams))
          '()
          (cons-stream
           (apply f (map stream-car streams))
           (apply stream-map f
                  (map stream-cdr streams))))))

Všechny procedury, které mají vracet stream NESMÍ procházet celý stream - ten může být i nekonečný!

Př:
  (define to10
    (let iter ((x 1))
      (if (<= x 10)
          (cons-stream x (iter (+ x 1)))
          '())))

  Jak se vyhodnotí?:
  to10 =>
  (stream-cdr to10) =>
  (stream-car (stream-cdr to10)) =>
  (stream->list to10) =>

  ; nekonečný proud samých jedniček
  (define ones
    (let it ()
      (cons-stream 1 (it))))

  (display-stream ones 3)
  1
  1
  1

;Př: napište nekonečný proud všech přirozených čísel

;Př: napište nekonečný proud všech sudých přirozených čísel

;Př: napište proceduru, která spojí dva seznamy po prvcích
  (display-stream (merge-streams ones naturals) 6) =>
  1
  1
  1
  2
  1
  3

  (display-stream (merge-streams (stream 1 2 3 4 5) (stream -2 -4 -5 -6) (stream 12 34)))
  1
  -2
  12
  2
  -4
  34
  3
  -5
  4
  -6
  5

; Př napište proud všech prvočísel

Implicitní zadání nekonečných proudů (bez iterace, bez pomocné procedury):
-------------------------------------
    (define ones (cons-stream 1 ones))
    (display-stream ones 3)
    1
    1
    1

(define pow2
    (cons-stream 1
        (stream-map (lambda (x) (* 2 x))
        pow2)))

(display-stream pow2 6)
1
2
4
8
16
32
; Proč to funguje ?

Př: Napište implicitně zadaný nekonečný proud všech faktoriálů

Pro příjemnější psaní nekonečných proudů můžeme použít build-stream, fungující podobně jako build-list (pouze bez omezení délky)


Práce se soubory ve scheme:
---------------------------
- pomocí portů viz. přednáška
(define p (open-input-file "/tmp/blah.txt"))
(display (read p))
(display (read p))
(display (read p))
(close-input-port p)

Pomocné procedury pro převod problému čtení ze souboru na streamy:

(stream->list (file->stream (lambda (x) (read x)) "/tmp/blah.txt")) =>
(1 2 3 4)

Procedury s keší:
-----------------
    - pamatujeme si pro jaké parametry jsme vrátili jaké hodnoty (třeba v asociativním seznamu)
    - nemusíme pořád dokola počítat (stejné) náročné výpočty
    - procedura memoize (součást knihovny) si pamatuje neomezné množství argumentů (může jich být moc)

(define fib
  (memoize
   (lambda (n)
     (if (<= n 2)
         1
         (+ (fib (- n 1))
            (fib (- n 2)))))))

    - procedura (make-memoize slots-count) dělá to samé jako memoize, jen má omezenou velikost keše

(define fib
    ((make-memoize 5)
        (lambda (n)
            (if (<= n 2)
            1
            (+ (fib (- n 1))
            (fib (- n 2)))))))


Domácí úkoly (možno odevzdat až 3.5)
1) Napiste stream-append, ktery spojĂi dva streamy, podobne jako append spojuje 2 seznamy. Musí produkovat stream! (1 bod)
  (define s1 (list->stream '(1 2 3 4)))
  (define s2 (list->stream '(5 6 7)))
  (display-stream (stream-append s1 s2)) => #<stream (1 2 3 4 5 6 7)>

2) Napiste stream-rm-duplicates, ktery vymaze duplicitni prvky ze streamu. (2 body)
  Priklad pouziti:
  (stream->list (stream-rm-duplicates (list->stream '(2 2 3 4 5 6 5 7 2)))) =>
  (2 3 4 5 6 7)