;; Questo file contiene il codice Scheme che risolve
;; alcuni degli esercizi svolti in classe - 31/10/02


;; Calcolo dell'IRPEF sulla base delle istruzioni Unico2002.
;;
;; Analisi ricorsiva del problema, che coglie piu' precisamente
;; il criterio adottato per determinare l'imposta.


;; Astrazione procedurale: modalita' di calcolo dell'IRPEF.

(define irpef           ; imponibile >= 0
  (lambda (imponibile)
    (tassa imponibile (scaglione imponibile))
    ))

(define tassa
  (lambda (imponibile scaglione)
    (if (= scaglione 1)
        (* (aliquota 1) imponibile)
        (+ (tassa (inf scaglione) (- scaglione 1))
           (* (aliquota scaglione) (- imponibile (inf scaglione))))
        )
    ))


(define scaglione
  (lambda (reddito)
    (localizza-da ultimo-scaglione reddito)
    ))

(define localizza-da
  (lambda (scaglione reddito)
    (if (>= reddito (inf scaglione))
        scaglione
        (localizza-da (- scaglione 1) reddito)
        )
    ))


;; Parametri contingenti relativi agli scaglioni.

(define ultimo-scaglione 5)

(define aliquota
  (lambda (scaglione)
    (cond ((= scaglione 1) 0.18)
          ((= scaglione 2) 0.24)
          ((= scaglione 3) 0.32)
          ((= scaglione 4) 0.39)
          (else            0.45)  ; scaglione 5
          )
    ))
  
(define inf
  (lambda (scaglione)
    (cond ((= scaglione 1)      0)
          ((= scaglione 2)  20000)
          ((= scaglione 3)  30000)
          ((= scaglione 4)  60000)
          (else            135000)  ; scaglione 5
          )
    ))


;; Algoritmo del "Contadino Russo" per calcolare il prodotto

(define prodotto-alla-Russa
  (lambda (x y)
    (cond ((= y 0)
           0)
          ((even? y)
           (prodotto-alla-Russa (+ x x) (quotient y 2)))
          (else  ; odd y
           (+ x (prodotto-alla-Russa x (- y 1))))
          )
    ))


;; Verifica se un numero e' primo

(define prime?
  (lambda (n)  ; n > 2 naturale
    (not (there-are-divisors-between? 2 (- n 1) n))
    ))

(define there-are-divisors-between?
   (lambda (x y n)  ; ci sono divisori di n nell'intervallo [x,y] ?
     (cond ((> x y) #f)                ; intervallo vuoto
           ((= 0 (remainder n x)) #t)  ; x divide n
           (else                       ; si toglie x dall'intervallo
            (there-are-divisors-between? (+ x 1) y n))
           )
     ))


;; Piu' lungo prefisso comune di due stringhe

(define common-prefix
  (lambda (s t)
    (cond ((or (string-empty? s) (string-empty? t))
           "")
          ((not (char=? (first-char s) (first-char t)))
           "")
          (else  ; stesso carattere iniziale
           (string-append
            (string (first-char s))
            (common-prefix (string-tail s) (string-tail t))
           ))
          )
    ))

(define first-char
  (lambda (s)
    (string-ref s 0)
    ))

(define string-tail
  (lambda (s)
    (substring s 1 (string-length s))
    ))

(define string-empty?
  (lambda (s)
    (= (string-length s) 0)
    ))


;; Quali funzioni di n calcolano
;; le procedure odd e unknown?

(define odd
  (lambda (i)    ;; i naturale
    (if (= i 1)
        1
        (+ (odd (- i 1)) 2)
        )
    )
  )

(define unknown
  (lambda (x)    ;; x naturale
    (if (= x 0)
        0
        (+ (unknown (- x 1)) (odd x))
        )
    )
  )


;; Altri esempi di procedure ricorsive.

;; Lato maggiore dei fogli in formato Ak - versione ricorsiva

(define sqrt-2 (sqrt 2))

(define A
  (lambda (k)
    (if (= k 0)
        (sqrt sqrt-2)
        (/ (A (- k 1)) sqrt-2)
        )
    ))


;; Numero di permutazioni

(define permutation-number
  (lambda (n)    ;; n naturale positivo
    (if (= n 1)
        1
        (* n (permutation-number (- n 1)))
        )
    )
  )


;; Numero di nodi di un albero d-ario
;; di altezza h

(define number-of-nodes
  (lambda (d h)  ;; d, h naturali
    (if (= h 0)  ;; d > 0 = grado, h = altezza
        1        ;; solo la radice
        (+
         1       ;; radice piu'
         (* d    ;; d sottoalberi di altezza h-1
            (number-of-nodes d (- h 1)))
         )
        )
    )
  )