Muster passen ein Array

Question

Ich habe eine Funktion, die das Minimum eines Arrays zurückgibt.

Die Funktion hat Typ:

min : int array -> int 

Seine Umsetzung ist:

let rec min a = match a with 
    | [] -> 1000000000 
    | x :: [] -> x 
    | x :: xs -> let ms = min xs in if x < ms then x else ms;; 

Allerdings erhalte ich diese Fehlermeldung:

Found min with unexpected type: 
Wrong type int list -> int. 

So wie kann ich Muster ein Array entsprechen ?

Answer 1

Sie verwenden Listennotation in Ihren Mustern, die das Problem verursacht. Ein Array Konstante sieht wie folgt aus: [| 3; 4; 5 |]

Ein Array Muster gleich aussieht, wie man erwarten würde:

let f = function 
| [| |] -> "empty" 
| [| _ |] -> "one" 
| [| _; _ |] -> "two" 
| _ -> "many" 

Jedes Array Muster entspricht einer Anordnung einer bestimmten Größe. Es gibt keine Übereinstimmung für ein Array von mindestens einer bestimmten Größe. Dies steht im Gegensatz zu Listen, in denen diese Flexibilität zur Verfügung steht.

Anstatt Mustererkennung zu verwenden, könnte eine sinnvollere Methode zur Verarbeitung Ihres Arrays darin bestehen, Array.fold_left oder Array.fold_right zu verwenden.

Möglicherweise sind Sie an eine Sprache gewöhnt, in der Arrays und Listen mehr oder weniger das Gleiche sind. In OCaml müssen Sie auswählen, welche Sie verwenden möchten.

Answer 2

Im Gegensatz zu Listen sind Arrays nicht induktiv definiert. Zum Beispiel ist eine Liste entweder eine leere Liste oder ein Paar eines Elements und eine andere Liste. Induktive Datendefinitionen sind nett, da sie erlauben, Daten induktiv, d. H. Rekursiv zu betrachten. Das Array ist eine sehr unterschiedliche Datenstruktur, die als eine feste Anzahl von Elementen des gleichen Typs definiert ist. Also, Ihr Algorithmus wird nicht für Arrays funktionieren. Und das Problem besteht nicht nur in der Syntax. Sie können den Mindestwert nicht durch Induktion auf dem Array ausdrücken. Sie müssen einen anderen Weg finden, um das Minimum auszudrücken, z. B. ein Minimum eines Arrays A der Größe N ist ein solches Element, m, das für alle i, 0 <= i < N haben wir m <= A(i). Wenn Sie dieser Definition folgen, können Sie sie direkt implementieren. Beginnen Sie mit dem ersten Element als Approximation des Minimums, fahren Sie dann mit dem nächsten Element fort, und wenn es kleiner als Ihr aktuelles Minimum ist, aktualisieren Sie Ihre Approximation. Sobald Sie alle Elemente überprüft haben, wird Ihr Minimum die gewünschte Eigenschaft erfüllen.

Was den leeren Fall betrifft, dann können Sie entweder entscheiden, dass das Minimum für das leere Array nicht definiert ist. Tha wird Ihre Funktion nicht-total machen, die Sie explizit darstellen können, indem Sie den Rückgabetyp int option oder implizit durch Auslösen einer Ausnahme machen und im Kommentar angeben, dass diese Funktion nur für nicht leere Arrays definiert ist. Alternativ können Sie das max_int als minimales Element für ein leeres Array zurückgeben, da die maximale Untergrenze einer leeren Menge ein Maximalwert des Universums ist (in unserem Fall max_int).