;;; -*- scheme -*-
;;; Prima lezione.
;;; Obiettivo principale: da zero alla ricorsione in coda.

;; Linea di commento.  Comincia con `;' e finisce alla fine della linea.
;; Si mettono 3 `;' per i commenti riguardanti l'intero file.
;; Si mettono 2 `;' per i commenti locali che prendono una intera linea.
;; Si mette un solo `;' per i commenti inseriti accanto ad una espressione.

;;; ----------
;;; Esempi di costanti numeriche.
57					; Intero.
2/3					; Razionale.
2.666					; Reale.
2e20					; Notazione esponenziale.
2+3i					; Complesso.

;;; ----------
;;; Aritmetica Elementare.
(+ 2 2/3)
(- 10 2 3)				; => 5 cioe` 10 - 2 - 3
(* 2+3i 5+2i)
(* 1 2 3 4 5 6 7 8 9 10)

;;; ----------
;;; Nota: Da fare con lo stepper.
;;; Nota: Semantica per sostituzione.
;;; Nota: Struttura ad albero dell'espressione.
(* (+ (* 2 3)
      3)
   (- 3
      4
      (* 3
	 (+ 3 2))))

;;; ----------
(/ 12 5)
(quotient 12 5)
(remainder 12 5)

;;; ----------
;;; Altre funzioni matematiche
(sqrt 2)
(expt 3 5)
(exp 3)
(sin 3.14)
(cos 3.14)

;;; ----------
;;; Stringhe di caratteri.
"Hello world!"
(string-append "Hello"
	       " "
	       "world"
	       "!")

;;; ----------
;;; Caratteri
#\a #\A
#\b #\B
;; ...
#\z #\Z
#\0
;; ...
#\9
#\;
#\space
#\newline
#\tab

					; Costruzione di una stringa a partire dai caratteri.
(string #\H #\e #\l #\l #\o
	#\space
	#\w #\o #\r #\l #\d #\!)

;;; ----------
;;; Conversioni
(char->integer #\a)
(integer->char 50)
(string->number "2/3")
(number->string (+ 2 3/2))

;;; ----------
;;; Valori di verita'
#t					; Vero (True).
#f					; Falso (False).
(and (odd? 2) (string? "pippo"))
(or (odd? 2) (string? "pluto"))
(not (string? "paperino"))

;;;----------
;;; Predicati
;;; Nota: Per convenzione i predicati finiscono con "?".
(= 3 (+ 1 2))				; Uguaglianza tra numeri.
(> 10 2)
(<= 2 2)
(equal? (list 1 2 3)			; Uguaglianza tra liste.
	(cons 1 (list 2 3)))
(equal? (list 1 2 3)
	(car (list 0 1 2 3)))
(null? (list 1 2 3))			; Lista vuota?
(null? (list))

;;; ----------
;;; Strutture di controllo.
(if (odd? 3)
    "3 e' dispari."
    "3 e' pari.")

;;; ----------
;;; Liste prima parte.
;;; Nota: Provare sia il livello "Beginner" che quello "Full".
(cons 1 (cons 2 (cons 3 (list))))	; Costruzione di una lista.
(list 1 2 3 4 5 6 7)			; Costruzione di una lista.
(list)					; Lista vuota.
(car (list 1 2 3))			; Primo elemento.
(cdr (list 1 2 3))			; Tutto tranne il primo elemento.
(cons 1					; Aggiungere un elemento in testa.
      (list 1 2 3))
(append (list 1 2 3)
	(list 4 5 6))
(cdr (cons 0 (list 1 2 3)))		; Metto e tolgo zero.

;; Stringhe di caratteri e liste sono oggetti diversi.
(list->string (list #\H #\e #\l #\l #\o))
(string->list "Hello world!")

;;; ----------
;;; Simboli
(quote x)
'x
(string->symbol "tanto va la gatta al lardo che ...")
(string->symbol "(+ 1 2)")
(list 'x 'y 'z)
(list 1 2 3 'x 'y 'z)

;;; ----------
;;; Liste quotate (non funziona con il livello beginner di drscheme).
(quote (1 2 3))
'(1 2 3)

;;; ----------
;;; Rappresentazione di valori e `display'.
"Hello World!"
(display "Hello World!")
(newline)
(list 1 2)
(display (list 1 2))
(newline)
;; GC sta per Giulio Cesare non Gianni Ciolli.
"\"Veni, Vidi, Vici\" -- GC"
(display "\"Veni, Vidi, Vici\" -- GC")

;;; ----------
;;; Definizione di variabili.
(define a 5)
(define b 6)
(+ a b)
(+ a c)					; Errore: c non e' definita.
(define c (+ 1 a b))

c					; Valore di c.

;;; ----------
;;; Caratteri ammessi negli identificatori.  Si fa prima a dire quelli
;;; non ammessi.  Principalmente:
;;;  - lo spazio
;;;  - le parentesi: ()[]{}
;;;  - apici vari: `'"
;;;  - i caratteri: ,;|#
;;; Tutti questi caratteri non sono ammessi perche' hanno un
;;; significato speciale.
;;;
;;; Esempi di identificatori (tratto da R5RS):
;;;       lambda                   q
;;;       list->vector             soup
;;;       +                        V17a
;;;       <=?                      a34kTMNs
;;;       the-word-recursion-has-many-meanings
;;;
;;; Infine, un indentificatore non puo` iniziare con un carattere
;;; numerico 0..9.

;;; ----------
;;; Variabili predefinite.
;;; Nota: Da usare anche con con il livello "Full".
+ - * /
list null? length
display newline

;;; ----------
(define email "maggesi@math.unifi.it")
(define mailto "mailto:")
(define link (string-append
	      "<a href=\""
	      mailto
	      email
	      "\">"
	      email
	      "</a>"))
link
(display link)

;;; ----------
;;; Funzioni.

(define add2
  (lambda (x) (+ x 2)))			; Aggiungi 2 a x.

(define square
  (lambda (x)
    (* x x)))				; Quadrato di x.

(define cube				; Cubo di x.
  (lambda (x)
    (* x (square x))))

(cube 3)

(define (add3 x)			; Notazione compatta.
  (+ x 3))

(add3 2)

;;; ----------
;;; Esercizio 1: scrivere un predicato `maiuscola?' che dice se una
;;; lettera e' maiuscola.  Ad esempio:

(maiuscola? #\space)			; #f
(maiuscola? #\A)			; #t
(maiuscola? #\b)			; #f


;;; ----------
;;; Esercizio 2: scrivere una funzione `to-lower' che trasforma una lettera
;;; maiuscola in una minuscola. Ad esempio:

(to-lower #\space)			; #\space
(to-lower #\A)				; #\a
(to-lower #\b)				; #\b

;;; ----------
;;; Funzioni ricorsive.

;;; Trova la lunghezza di una lista (prima versione).
;;; (Ovviamente esiste gia' una primitiva per questo: `length'.)
(define (lunghezza-lista l)
  (if (null? l)				; l e' la lista vuota?
      0					; allora 0
      (+ 1 (lunghezza-lista (cdr l)))))	; senno' 1 + lunghezza del resto.

(lunghezza-lista (list))
(lunghezza-lista (list 1 2 3))

(define lista-di-prova (list 1 2 3 4 5 6 7 8))

;; Verifica:
(= (lunghezza-lista lista-di-prova)
   (length lista-di-prova))

;;; ----------
;;; Esercizio 3: Scrivere una funzione che conti il numero di interi
;;; dispari in una lista.  Ad esempio:

(numero-di-dispari (list 1 2 3 4 5 6))	; => 3

;;; ----------
;;; Fattoriale ricorsivo (non ricorsivo in coda).
(define (fact n)
  (if (positive? n)
      (* n (fact (- n 1)))
      1))

(fact 100)

;;; ----------
;;; Fattoriale ricorsivo in coda.
(define (fact-aux n acc)
  (if (positive? n)
      (fact-aux (- n 1) (* n acc))
      acc))

(define (fact n)
  (fact-aux n 1))

(fact 5)

;;; ----------
;;; Lunghezza di una lista.  Versione ricorsiva in coda.
(define (lunghezza-lista l)
  (lunghezza-aux l 0))

(define (lunghezza-aux l acc)
  (if (null? l)
      acc
      (lunghezza-aux (cdr l) (+ 1 acc))))

(lunghezza-lista (list 1 2 3))

;;; ----------
;;; Lunghezza di una lista.  Versione ricorsiva in coda.

(define (lunghezza-lista l)
  ;; Funzione ausiliaria definita localmente.
  (define (aux l acc)
    (if (null? l)
	acc
	(-aux (cdr l) (+ 1 acc))))

  ;; Corpo della funzione principale.
  (aux l 0))

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

;;; Esercizio 4: Dopo aver fatto l'esercizio 3, controllare
;;; (eventualmente usando lo stepper) se la la funzione
;;; numero-di-dispari che avete scritto e' ricorsiva in coda o no.
;;; Riscrivere la funzione in modo che lo diventi.

;;; ----------
;;; Funzione filtro.
(define (filtro pred l)
  (if (null? l)
      l
      (if (pred (car l))
	  (cons (car l)
		;; Chiamata ricorsiva NON in coda.
		(filtro pred (cdr l))
		)
	  ;; Chiamata ricorsiva in coda.
	  (filtro pred (cdr l))
	  )))

(filtro odd? (list 1 2 3 4))

;;; ----------
;;; Ricorsione in coda tra due funzioni.

(define (pari? n)
  (if (zero? n)
      #t
      (dispari? (- n 1))))

(define (dispari? n)
  (if (zero? n)
      #f
      (pari? (- n 1))))

(pari? 3)

;;; ============================================================
;;; ALTRI ESERCIZI.

;;; ----------
;;; Esercizio 5: Scrivere una funzione che calcola l'area del
;;; triangolo.  Esempio:

(area-triangolo 3 4)			; => 6


;;; ----------
;;; Esercizio 6: Data una stringa, costruire una nuova stringa dove
;;; tutte le maiuscole sono diventate minuscole.

(string/to-lower "Hello world!")		; => "hello world!"


;;; ----------
;;; Esercizio 7: Considerate la successione di Fibonacci
;;;     fib(n)  :  1 1 2 3 5 8 13
;;; definita dalla regola ricorsiva: fib(n+1) = fib(n) + fib(n-1).
;;; La successione puo` essere calcolata facilmente con una funzione
;;; doppiamente ricorsiva:

(define (fib n)
  (if (or (= n 0)
	  (= n 1))
      1					; Valore dei primi due termini.
      (+ (fib (- n 1))
	 (fib (- n 2)))))

(fib 0)					; => 1
(fib 1)					; => 1
(fib 2)					; => 2
(fib 3)					; => 3
(fib 4)					; => 5

;;; Trasformare la funzione precedente in modo che sia completamente
;;; ricorsiva in coda.