# SELECTION SORT: la funzione minimo restituisce il minimo e il resto della lista
# non e' definita su nil. Me ne devo preoccupare?
fun minimo   [h]  min = (h, nil)
 |  minimo (h::t) min = 
        let val (m, r) = minimo t min 
            in if (min h m)
		then (h, m::r) 
		else (m, h::r)
        end; 
! ....minimo   [h]  min = (h, nil)
!  |  minimo (h::t) min = 
!         let val (m, r) = minimo t min 
!             in if (min h m)
!               then (h, m::r) 
!               else (m, h::r)
!         end..
! Warning: pattern matching is not exhaustive

> val 'a minimo = fn : 'a list -> ('a -> 'a -> bool) -> 'a * 'a list

fun selectSort nil min = nil
 |  selectSort  l  min = 
       let val (m,r) = minimo l min
           in m::(selectSort r min)
       end;
> val 'a selectSort = fn : 'a list -> ('a -> 'a -> bool) -> 'a list

# INSERTION SORT: prima faccio una funzione che inserisce un elemento
# al posto giusto in una lista ordinata
fun addOrd a   nil  min = [a]
 |  addOrd a (h::t) min = 
        if (min a h) then h::(addOrd a t min)
                     else a::(h::t);
> val 'a addOrd = fn : 'a -> 'a list -> ('a -> 'a -> bool) -> 'a list

fun insertSort  nil   min = nil
 |  insertSort (h::t) min =
      addOrd h (insertSort t min) min;
> val 'a insertSort = fn : 'a list -> ('a -> 'a -> bool) -> 'a list

# RICOSTRUZIONE DI ALBERI
# 1. Assiomatizzazione induttiva della relazione tra liste, tale che
# R(I, P) significa che I e P sono la visita inorder e postorder
# dello stesso albero (l'append viene scritto semplicemente scrivendo
# le liste di seguito... n e' un intero)


(Ax)		R(nil, nil)

	R(I',P')	R(I'', P'')
(App)	---------------------------
		R(I'nI'',nP'P'')

# I e P rappresentano UNIVOCAMENTE un albero se una derivazione formale 
# se e solo se, usando le regole di derivazione (Ax) ed (App), la
# dimostrazione di R(I,P) e' UNICA.
# Altre condizioni interessanti:

# Se I e P hanno elementi tutti distinti (e R(I,P)!) allora la ricostruzione e' unica.

# Se nell'albero di partenza ogni cammino radice-foglia ha elementi tutti distinti.
# Questa e' la precondizione del seguente programma:
# prende la testa h della preorder, prende il primo elemento nella preorder uguale ad h
# e spezza opportunamente le liste di ingresso attivandosi ricorsivamente. 

fun decomponi x nil m = (nil, m)
 |  decomponi x (h::t) m = 
          if h=x then (m, t)
          else let val (p, q) = decomponi x t m 
                   in (h::p, q)
               end;
 
fun decomponiP   l    0 = (nil, l)
 |  decomponiP (h::t) n = 
      let val (p, q) = decomponiP t (n-1) in (h::p, q)
      end;
 
fun ricostruisci   nil nil = emptyTree
 |  ricostruisci (h::t) l  =
      let val (p, q) = decomponi  h l nil
      in let val (l, r) = decomponip t (length p)
      in node(h, ricostruisci p l, ricostruisci q r)
      end
      end;
 
# osservate che questa non funziona per le liste di ingresso: [5 5 1 3] e [1 5 5 3] che effettivamente
# non rispettano la precondizione, ma esiste un UNICO albero associato: 
# node(5, node(5, node(1, emptytree, emptytree), emptytree), node(3, emptytree, emptytree)))
# o se preferite:
#			5
#		   5         3
#               1

# Un altro programma piu' preciso non si limita a prendere nella lista inorder la prima 
# occorrenza della radice selezionata nella lista preorder, ma a verificare se e' possibile
# decomporre le liste di ingresso in liste che I' e P' che sono ancora coppie legali,
# cioe' per cui vale R(I', P'). [Questo programma verifica per la verita' solo che le due
# liste abbiano gli stessi elementi]

fun isIn x nil l    = (false, nil)
 |  isIn x (h::t) l = 
        if x=h then (true, (append t l))
               else let val (b, m) = isIn x t (h::l)
                        in if b then (true, m)
                                else (false, nil)
                    end;

fun sameElements nil nil = true
 |  sameElements nil l = false
 |  sameElements l nil = false
 |  sameElements (h::t) l = 
        let val (b, m) = isIn h l nil 
            in if b then sameElements t m
                       else false
        end;

fun decomponiI x f (h::t) l = 
     if x=h 
        then let val (p, q) = decomponiP l (length f)
                 in if (sameElements p f) then (f, t, p, q)
                       else decomponiI x (append f [h]) t l
             end
        else decomponiI x (append f [h]) t l;

fun ricostruisci nil nil = emptyTree
 |  ricostruisci (r::p) i =
        let val (p1, p2, i1, i2) = decomponiI r [] i p
        in node(r, (ricostruisci l p), (ricostruisci r q))
        end;