Neu bei OCaml: Wie würde ich die Gaußsche Eliminierung implementieren?

Question

Ich bin neu in OCaml und möchte die Gaußsche Eliminierung als Übung implementieren. Ich kann es leicht mit einem zustandsabhängigen Algorithmus machen, d.h. eine Matrix im Speicher halten und rekursiv darauf arbeiten, indem ich eine Referenz darauf weitergebe.

Diese Zustandsabhängigkeit hat jedoch den Beigeschmack der imperativen Programmierung. Ich weiß, dass es in OCaml Möglichkeiten gibt, dies zu tun, aber ich würde gerne wissen, ob es einen cleveren funktionalen Weg gibt, an den ich noch nicht gedacht habe.

Answer 1

Sie können eine Map um eine Matrix zu emulieren. Der Schlüssel wäre ein Paar Ganzzahlen, die auf die Zeile und die Spalte verweisen. Sie sollten Ihre eigene get x y Funktion zur Sicherstellung x < n y y < n jedoch, anstatt auf die Map direkt. (edit) Sie können die Vergleichsfunktion in Pervasives direkt.

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

Tatsächlich ist es so, dass eine allgemeine Gruppe von Funktionen ( get x y y set x y zumindest), ohne Angabe der Implementierung, wäre eine noch bessere Option. Die Funktionen können dann an die Funktion übergeben werden oder in einem Modul durch einen Funktor implementiert werden (eine bessere Lösung, aber eine Reihe von Funktionen zu haben, die genau das tun, was Sie brauchen, wäre ein erster Schritt, da Sie neu in OCaml sind). Auf diese Weise können Sie eine Map , Array , Hashtbl oder eine Reihe von Funktionen zum Zugriff auf eine Datei auf der Festplatte, um die Matrix zu implementieren. Das ist der wirklich wichtige Aspekt der funktionalen Programmierung: dass man der Schnittstelle mehr vertraut als der Ausnutzung von Seiteneffekten und sich nicht um die zugrunde liegende Implementierung kümmert, da man davon ausgeht, dass sie rein ist.

Answer 2

OCaml-Arrays sind veränderbar, und es ist schwer zu vermeiden, sie wie Arrays in einer imperativen Sprache zu behandeln.

Haskell hat unveränderliche Arrays, aber aus meiner (begrenzten) Erfahrung mit Haskell, Sie am Ende auf monadische, veränderbare Arrays in den meisten Fällen wechseln. Unveränderliche Arrays sind wahrscheinlich erstaunlich für bestimmte spezifische Zwecke. Ich habe mir immer vorgestellt, dass man eine schöne Implementierung der dynamischen Programmierung in Haskell schreiben könnte, bei der die Abhängigkeiten zwischen den Array-Einträgen vollständig durch die Ausdrücke in ihnen definiert werden. Der Schlüssel dazu ist, dass man den Inhalt jedes Array-Eintrags wirklich nur einmal angeben muss. Ich glaube nicht, dass die Gaußsche Eliminierung diesem Muster folgt, und daher scheint sie für unveränderliche Arrays nicht geeignet zu sein. Es wäre jedoch interessant zu sehen, wie es funktioniert.

Answer 3

Die bisherigen Antworten sind die Verwendung/Emulation veränderlicher Datentypen, aber wie sieht ein funktionaler Ansatz aus?

Um das zu sehen, zerlegen wir das Problem in einige funktionale Komponenten:

Da die Gaußsche Elimination eine Folge von Zeilenoperationen erfordert, ist es sinnvoll, zunächst eine Funktion zu definieren, die 2 Zeilen und Skalierungsfaktoren annimmt und das resultierende Ergebnis der Zeilenoperation zurückgibt.

Die gewünschten Zeilenoperationen sollten eine Variable (Spalte) aus einer bestimmten Zeile eliminieren. Definieren wir also eine Funktion, die ein Paar von Zeilen und einen Spaltenindex annimmt und die zuvor definierte Zeilenoperation verwendet, um die geänderte Zeile mit dem Spalteneintrag Null zurückzugeben.

Dann definieren wir zwei Funktionen, eine zur Umwandlung einer Matrix in die Dreiecksform und eine weitere zur Rücksubstitution einer Dreiecksmatrix in die Diagonalform (unter Verwendung der zuvor definierten Funktionen), indem wir nacheinander jede Spalte eliminieren. Wir können über die Spalten iterieren oder rekursieren, und die Matrix kann als Liste, Vektor oder Array von Listen, Vektoren oder Arrays definiert werden. Die Eingabe wird nicht verändert, aber es wird eine modifizierte Matrix zurückgegeben, so dass wir schließlich tun können:

let out_matrix = to_diagonal (to_triangular in_matrix);

Es ist nicht entscheidend, ob die Datentypen (Array oder Liste) veränderbar sind, sondern wie sie verwendet werden. Dieser Ansatz ist vielleicht nicht besonders "clever" oder der effizienteste Weg, um Gaußsche Eliminationen in OCaml durchzuführen, aber durch die Verwendung reiner Funktionen können Sie den Algorithmus sauber ausdrücken.