[Caml] Insieme delle parti

[ZfreS]

Buongiorno a tutti. Ho trovato questa funzione in ocmal che ricava l'nsieme della parti, però non riesco a capire come funzioni:

Codice:

let rec subSets l =
    match l with
    | [] -> [[]]
    | x :: xs -> let l = subSets xs in
                   l @ (List.map (fun y -> x :: y) l)


Non mi è chiaro cosa avvenga nella chiamata ricorsiva sulla coda della lista. Se riusciste a spiegarmelo a parole quello che avviene ve ne sarei davvero grato!

[apatriarca]

Nessuna idea? Che cosa non capisci esattamente?

In parole povere implementa l'idea che se l'insieme (lista) $l$ ha almeno un elemento $x$, allora i suoi sottoinsiemi sono l'unione tra i sottoinsiemi di $xs = l - \{x\}$ e quegli stessi sottoinsiemi a cui è stato aggiunto $x$.

[ZfreS]

Non credo di aver capito beinissimo.
Supponiamo io passi la lista [1,2,3], l'insieme delle parti è [[],[1],[2],[3],[1,2][1,3],[2,3],[1,2,3]]

Al prima chiamata ricorsiva, qual'è la lista restituita? Probabilmente non mi è del tutto chaiaro il costrutto let...in

[apatriarca]

Il costrutto let .. in è in pratica equivalente ad una assegnazione in un linguaggio procedurale. Stai dando un nome al risultato di una espressione, in questo caso la chiamata ricorsiva. Come per molte chiamate ricorsive è "difficile" dare direttamente il risultato ad un livello casuale perché dipende dal risultato della chiamata ricorsiva successiva. In ogni caso hai la seguente

Codice:

subSets [1, 2, 3]
> subSets [2, 3]
> > subSets [3]
> > > subSets [] = [[]]
> > [[]] @ (List.map (fun y -> 3 :: y) [[]]) = [[], [3]]
> [[], [3]] @ (List.map (fun y -> 2 :: y) [[], [3]]) = [[], [3], [2], [2, 3]]
[[], [3], [2], [2, 3]] @ (List.map (fun y -> 1 :: y) [[], [3], [2], [2, 3]]) = [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]


[ZfreS]

Oh finalmente mi è tutto chiaro! Ti ringrazio davvero tanto!