;;; -*- scheme -*-

;;; **********
;;; Attenzione: per eseguire tutti gli esempi che ci sono un questo
;;; file e' necessaria l'istruzione seguente:

(load "stream.scm")

;; ----------
;; Stream finiti.

(define stream-prova
  (stream 1 2 3 4 5 6))

stream-prova
(stream-car stream-prova)		; Primo elemento dello stream.
(stream-cdr stream-prova)		; Coda dello stream.

(stream-head 3 stream-prova)		; Lista dei primi 3 elementi.
(stream-display stream-prova)		; Stampa tutti gli elementi.
(stream-car (stream-cdr stream-prova))	; Secondo elemento dello stream.
(stream-car (stream-cdr (stream-cdr stream-prova)))
					; Terzo elemento dello stream.

;; ----------
;; `stream-null'
;; `stream-null?'

(stream-null? (stream 1 2 3))
(stream-null? stream-null)

;; ----------
;; Costruzione di uno stream.

(stream-display
 (stream-cons 1
	      (stream-cons 2
			   (stream-cons 3
					stream-null))))

;; ----------
;; ** Funzione: stream-ref
;; Nota: le funzioni con le stellette `**' sono gia' implementate in
;; `stream.scm'.

(define (stream-ref s n)
  (if (positive? n)
      (stream-ref (stream-cdr s) (- n 1))
      (stream-car s)))

(stream-ref (stream 0 1 2 3) 2)

;; ----------
;; ** stream->list

(define (stream->list s)
  (if (stream-null? s)
      '()
      (cons (stream-car s)
	    (stream->list (stream-cdr s)))))

(stream->list (stream 3 46 51 2))

;; ----------
;; Esercizio 1: Scrivere `list->stream' che converte una lista in uno
;; stream.

;; ----------
;; Esercizio 2: Scrivere `stream-head' che restituisce una lista con gli
;; elementi del segemento iniziale di uno stream.
;;    (stream-head 3 (stream 0 1 2 3 4 5 6))
;;       => (0 1 2)

;; ----------
;; Stream infiniti.
;; ** integers-starting-from

(define (integers-starting-from n)
  (stream-cons n
	       (integers-starting-from (+ n 1))))

(stream-head 20 (integers-starting-from 0))
;;(stream-display (integers-starting-from 0))

;; ----------
;; Con le liste non si puo' fare.  Questo codice non funziona:
;;
;; (define (isf n)
;;   (cons n (isf (+ n 1))))
;; (define i (isf 0))

;; ----------
;; ** stream-constant

(define (stream-constant x)
  (stream-cons x
	       (stream-constant x)))

(stream-head 10 (stream-constant 1))

;; ----------
;; Semplici manipolatori di stream.

(stream-head 10
             (stream-filter odd? (integers-starting-from 53)))

(define (square x) (* x x))

(stream-head 10
             (stream-map square
                         (integers-starting-from 0)))

;; ----------

(define (crea-int2 n)
  (stream-cons n
	       (crea-int2 (+ n 2))))

(define int2 (crea-int2 0))

(stream-head 10 int2)

;; ----------
;; ** stream-add

(define (stream-add s1 s2)
  (if (stream-null? s1)
      s2
      (if (stream-null? s1)
	  s1
	  (stream-cons (+ (stream-car s1)
			  (stream-car s2))
		       (stream-add (stream-cdr s1)
				   (stream-cdr s2))))))

(stream->list (stream-add (stream 1 2 3 4)
			 (stream 2 4 6 3)))

;; ----------
;; Definizione dello stream dei numeri naturali con `stream-add'.

(define naturali
  (stream-cons 0
               (stream-add naturali
			   (stream-constant 1))))

(stream-head 10 naturali)

;; ----------
;; Esercizio 3: Riscrivere in modo piu' compatto `stream-add' con
;; l'aiuto di `cond' invece che `if'.

;; ----------
;; Esercizio 4: Scrivere `stream-mult' che moltiplica due stream.

;; ----------
;; Esercizio 5: Costruire lo stream dei quadrati in tutti i modi che
;; vengono in mente:
;;   (stream-head 5 quadrati)
;;       => (0 1 4 9 16)

;; ----------
(define fact
  (stream-cons 1
               (stream-mult fact (integers-starting-from 1))))

(stream-head 10 fact)

;; ----------
(define fib
  (stream-cons 0
               (stream-cons 1
                            (stream-add fib (stream-cdr fib)))))

(stream-head 10 fib)

;; ----------
(define (1+ x) (+ x 1))

;; (define (1+ x)
;;   (display x)
;;   (newline)
;;   (+ x 1))

(define pari (stream-cons 0
                          (stream-map 1+ (stream-cdr dispari))))

(define dispari (stream-cons 1
                             (stream-map 1+ pari)))

(stream-head 10 pari)

;; ----------
(define (divisible? x q)
  (= 0 (remainder x q)))

(define (sieve s)
  (stream-cons
   (stream-car s)
   (sieve (stream-filter (lambda (x)
			   (not (divisible? x (stream-car s))))
			 (stream-cdr s)))))

(define primes (sieve (integers-starting-from 2)))

(stream-head 10 primes)
;; (stream-display primes)

;; ----------
(define (stream-merge less? s1 s2)
  (cond ((stream-null? s1) s2)
	((stream-null? s2) s1)
	((less? (stream-car s1)
		(stream-car s2))
	 (stream-cons (stream-car s1)
		      (stream-merge less? (stream-cdr s1) s2)))
	(else
	 (stream-cons (stream-car s2)
		      (stream-merge less? s1 (stream-cdr s2))))))

(define (stream-jump s)
  (if (or (stream-null? s)
	  (stream-null? (stream-cdr s)))
      s
      (stream-cons (stream-car s)
		   (stream-jump (stream-cdr (stream-cdr s))))))

(define (stream-merge-sort less? s)
  (if (or (stream-null? s)
	  (stream-null? (stream-cdr s)))
      s
      (stream-merge less?
		    (stream-merge-sort less? (stream-jump s))
		    (stream-merge-sort less? (stream-jump (stream-cdr s))))))

(stream->list
 (stream-merge-sort <
		    (stream 36 5 1 37 2 5 61 3 1 74 89 7 9 0)))

;; ----------
(define (stream-binary-sort less? s)
  (if (null? s)
      stream-null
      (stream-append (stream-binary-sort
		      less?
		      (stream-filter (lambda (x)
				       (less? x (stream-car s)))
				     (stream-cdr s)))
		     (stream (stream-car s))
		     (stream-binary-sort
		      less?
		      (stream-filter (lambda (x)
				       (not (less? x (stream-car s))))
				     (stream-cdr s))))))

(stream->list
 (stream-binary-sort <
		     (stream 36 5 1 37 2 5 61 3 1 74 89 7 9 0)))