# Liste => confrontare con rappresentazione a puntatori in C
# Lista tipo di dato primitivo

- val l = [1, 2, 3];
> val l = [1, 2, 3] : int list

- val [x, y, z] = l;
> val x = 1 : int
  val y = 2 : int
  val z = 3 : int

- val h::t = l;
> val h = 1 : int
  val t = [2, 3] : int list

# nel pattern matching posso usare l'underscore per matchare
# una parte della struttura dati che non mi serve: 
- val h::_ = l;
> val h = 1 : int

# tutti gli elementi della lista hanno lo stesso tipo:
- val m = [ 1, l];
! Toplevel input:
! val m = [ 1, l];
!              ^
! Type clash: expression of type
!   int list
! cannot have type
!   int

- val m = 0::l;
> val m = [0, 1, 2, 3] : int list

- (3::nil)::(4::5::nil)::nil;
> val it = [[3], [4, 5]] : int list list

- val m = [0::l];
> val m = [[0, 1, 2, 3]] : int list list

/* liste polimorfe: map & reduce
- nil;    
> val 'a it = [] : 'a list

# map applica una funzione a tutti gli elementi di una lista:
- fun map f nil = nil
   |  map f (h::t) = (f h)::(map f t);
> val ('a, 'b) map = fn : ('a -> 'b) -> 'a list -> 'b list

# reduce f c [x_1, x_2, ... x_n] calcola:   
# f x_1 (f x_2 ( ...  (f x_n-1 (f x_n c)) ... ))
- fun reduce f c nil = c 
   |  reduce f c (h::t) = f h (reduce f c t);
> val ('a, 'b) reduce = fn : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

# applicaLista applica una lista di funzioni ad una lista di argomenti
# della stessa lunghezza (questa precondizione causa il warning, in quanto
# non sono ammessi pattern del tipo "nil (h::t)" oppure "(h::t) nil" 
- fun applicaLista   nil    nil  = nil 
 |  applicaLista (f::F) (h::t) = (f h)::(applicaLista F t);
! Toplevel input:
! ....applicaLista   nil    nil  = nil 
!  |  applicaLista (f::F) (h::t) = (f h)::(applicaLista F t).
! Warning: pattern matching is not exhaustive

> val ('a, 'b) applicaLista = fn : ('a -> 'b) list -> 'a list -> 'b list

- fun sum x y = x+y;
> val sum = fn : int -> int -> int

- reduce sum 0 l;
> val it = 6 : int

# La funzione accoppia (o zip, cerniera) prende due liste della stessa
lunghezza
# e restituisce la lista delle coppie (della stessa lunghezza)  
- fun accoppia nil nil = nil
   |  accoppia (h1::t1) (h2::t2) = (h1,h2)::(accoppia t1 t2);
! Toplevel input:
! ....accoppia nil nil = nil
! | accoppia (h1::t1) (h2::t2) = (h1,h2)::(accoppia t1 t2).
! Warning: pattern matching is not exhaustive

> val ('a, 'b) accoppia = fn : 'a list -> 'b list -> ('a * 'b) list

# esiste anche l'operatore INFISSO @ predefinito, ma volendo far da
soli...
- fun append nil l = l
   |  append (h::t) l = h::(append t l);
> val 'a append = fn : 'a list -> 'a list -> 'a list

- fun remove nil a = nil
   | remove (h::t) a = let val l=remove t a 
			   in if a=h then l else h::l 
		       end;
> val ''a remove = fn : ''a list -> ''a -> ''a list

- fun elimcopie nil = nil
  |  elimcopie (h::t) = h::(elimcopie(remove t h));
> val ''a elimcopie = fn : ''a list -> ''a list

- elimcopie [1, 2, 5, 7,1,7,3,3,3];
> val it = [1, 2, 5, 7, 3] : int list

# reverse quadratica
- fun reverse nil = nil 
   |  reverse (h::t) = append (reverse t) [h];
> val 'a reverse = fn : 'a list -> 'a list

# reverse efficiente con funzione ausialiaria
- fun reverseEff l =
   let fun revAux nil m = m
        |  revAux (h::t) m = revAux t (h::m)
   in revAux l nil
   end;
> val 'a reverseEff = fn : 'a list -> 'a list

- reverseEff [1,2,3];
> val it = [3, 2, 1] : int list

fun insert a l = a::l;
> val 'a insert = fn : 'a -> 'a list -> 'a list


- fun powerset nil = [nil]
|  powerset (h::t) =
      let val p = powerset t in append p (map (insert h) p) end;
> val 'a powerset = fn : 'a list -> 'a list list

# con funzione anonima
- fun powerset nil = [nil]
|  powerset (h::t) =
      let val p = powerset t in append p (map (fn x => h::x) p) end;
> val 'a powerset = fn : 'a list -> 'a list list

# mergesort:
# per dividere in due una lista uso queste due funzioni mutuamente
ricorsive
- fun dividi1 nil = (nil, nil)
   |  dividi1 (h::t) =  
         let val (p1,p2) = dividi2 t
         in (h::p1,p2)   
         end
  and dividi2 nil = (nil, nil)
   |  dividi2 (h::t) =
         let val (p1,p2) = dividi1 t
         in (p1,h::p2)
         end;
> val 'a dividi1 = fn : 'a list -> 'a list * 'a list
  val 'a dividi2 = fn : 'a list -> 'a list * 'a list

# fusione ordinata di liste ordinate:
- fun merge m nil = m
   |  merge nil l = l
   |  merge (h1::t1) (h2::t2) = 
            if (h1<h2) then h1::(merge t1 (h2::t2)) 
                       else h2::(merge (h1::t1) t2);

> val merge = fn : int list -> int list -> int list

## errata! non termina. Perche'?
- fun mergesort nil = nil
   |  mergesort l   = 
         let val (p1,p2) = dividi1 l
         in merge (mergesort p1) (mergesort p2)
         end;
val 'a mergesort = fn : 'a list -> int list
 
- fun mergesort nil = nil
   |  mergesort [h] = [h]
   |  mergesort l =  
         let val (p, q) = dividi1 l
         in merge (mergesort p) (mergesort q)
         end;
> val mergesort = fn : int list -> int list