Nuovo in OCaml: come potrei implementare l'eliminazione gaussiana?

Question

Sono nuovo di OCaml e mi piacerebbe implementare l'eliminazione gaussiana come esercizio. Posso farlo facilmente con un algoritmo di stato, vale a dire mantenere una matrice in memoria e operarci ricorsivamente passando attorno ad un riferimento ad esso.

Questo stato, tuttavia, sa di programmazione imperativa. So che ci sono funzionalità in OCaml per farlo, ma vorrei chiedere se c'è un modo funzionale intelligente a cui non ho pensato prima.

Answer 1

Gli array OCaml sono mutabili ed è difficile evitare di trattarli come matrici in un linguaggio imperativo.

Haskell ha matrici immutabili, ma dalla mia (limitata) esperienza con Haskell, si finisce per passare a matrici monadiche e mutabili nella maggior parte dei casi. Gli array immutabili sono probabilmente sorprendenti per determinati scopi specifici. Ho sempre immaginato di poter scrivere una bella implementazione di programmazione dinamica in Haskell, dove le dipendenze tra le voci dell'array sono definite interamente dalle espressioni in esse contenute. La chiave è che devi solo specificare il contenuto di ciascuna voce dell'array una volta sola. Non credo che l'eliminazione gaussiana segua questo schema e quindi sembra che potrebbe non essere adatto per gli array immutabili. Sarebbe interessante vedere come funziona, comunque.

Answer 2

È possibile utilizzare un numero Map per emulare una matrice. La chiave sarebbe una coppia di numeri interi che fanno riferimento alla riga e alla colonna. Ti consigliamo di utilizzare la tua funzione get x y per garantire x < n e y < n, invece di accedere direttamente allo Map. (modifica) È possibile utilizzare direttamente la funzione di confronto in Pervasives.

module OrderedPairs = struct 
    type t = int * int 
    let compare = Pervasives.compare 
end      
module Pairs = Map.Make (OrderedPairs) 

let get_ n set x y = 
    assert(x < n && y < n); 
    Pairs.find (x,y) set 

let set_ n set x y v = 
    assert(x < n && y < n); 
    Pairs.add (x,y) set v 

realtà, avente un insieme generale di funzioni (get x y e set x y al minimo), senza specificare l'attuazione, sarebbe un'opzione ancora migliore. Le funzioni possono quindi essere passate alla funzione, o essere implementate in un modulo attraverso un functor (una soluzione migliore, ma avere un set di funzioni semplicemente facendo ciò di cui hai bisogno sarebbe un primo passo da quando sei nuovo in OCaml). In questo modo è possibile utilizzare uno Map, Array, Hashtbl o un set di funzioni per accedere a un file sul disco rigido per implementare la matrice, se lo si desidera. Questo è l'aspetto veramente importante della programmazione funzionale; che ti fidi dell'interfaccia sfruttando gli effetti collaterali e non ti preoccupare dell'implementazione sottostante, perché si presume che sia pura.

Answer 3

Le risposte finora utilizzano/emulano tipi di dati mutabili, ma che aspetto ha un approccio funzionale?

Per vedere, diciamo scomporre il problema in alcuni componenti funzionali:

eliminazione gaussiana comporta una sequenza di operazioni di riga, quindi è utile prima di definire una funzione prendendo 2 righe e fattori di scala, e restituendo la riga risultante risultato dell'operazione

Le operazioni di riga che vogliamo devono eliminare una variabile (colonna) da una particolare riga, quindi consente di definire una funzione che prende una coppia di righe e un indice di colonna e utilizza l'operazione di riga precedentemente definita per restituire la riga modificata con quello colonna zero.

Quindi definiamo due funzioni, una per convertire una matrice in forma triangolare, e l'altra per sostituire una matrice triangolare alla forma diagonale (utilizzando le funzioni definite in precedenza), eliminando a turno ciascuna colonna. Potremmo scorrere o ricorrere alle colonne e la matrice potrebbe essere definita come un elenco, vettore o array di liste, vettori o matrici.L'input non è cambiato, ma viene restituita una matrice modificata, quindi possiamo finalmente fare:

let out_matrix = to_diagonal (to_triangular in_matrix);

Ciò che lo rende funzionale non è se i tipi di dati (matrice o elenco) sono mutabili, ma in che modo vengono utilizzati. Questo approccio potrebbe non essere particolarmente 'intelligente' o essere il modo più efficiente per eseguire eliminazioni gaussiane in OCaml, ma l'uso di funzioni pure consente di esprimere l'algoritmo in modo pulito.