Gemeinsames Rekursionsmuster

Question

Ich gewöhne mich an die höheren Funktionen von Haskell. Normalerweise kann ich explizite Rekursionsmuster durch Funktionen wie Map, Fold und Scan ersetzen. Allerdings laufe ich oft in die folgende Rekursion Muster, das ich nicht verstehen, wie Funktionen höherer Ordnung mit auszudrücken:

f (x:[]) = k x 
    f (x:xs) = g x (f xs) 

Zum Beispiel nehme ich an analytischen Tableaus bin darstellt. Dann habe ich einen Datentyp erstellen, wie:

data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau) 

Wenn ich eine Liste von Expr s in einem Tableau Struktur umwandeln will, ich will ein Funktionsteil davon ähneln könnten:

f (x:[]) = N x 
    f (x:xs) = S x (f xs) 

Jetzt, Ich sehe drei Optionen: (1) Erstellen Sie eine Funktion, die bei einem Tableau und einer Liste entscheidet, ob der nächste Zweig im Tableau ein S oder N (oder B sein soll, aber wir ignorieren diesen Fall); (2) Verwenden einer Funktion höherer Ordnung zum Einkapseln des Rekursionsmusters von f; (3) Verwenden Sie eine Funktion wie f.

Was wäre die beste Option?

Answer 1

Ich würde höchstwahrscheinlich die folgenden Befehle verwenden:

f xs = foldr g (k (last xs)) (init xs) 

Im Grunde bedeutet es, dass das Ende der Liste durch k x ersetzt wird, wenn Falten. Dank der allgegenwärtigen Lazy Evaluation funktioniert es sogar für unendliche Listen.

Es gibt zwei andere Lösungen - leere Hülle hinzufügen und Maybe verwenden.

A) Hinzufügen leer Fall:

Es wäre am besten, wenn f [] war gut definiert.Dann könnten Sie die Definition als

f [] = c 
f (x:xs) = g x (f xs) 

schreiben, die f = foldr g c ist. Wenn Sie zum Beispiel, ändern

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau 

zu

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau 

dann können Sie Einzelelement-Tableaus als S expr N darstellen, und die Funktion ist definiert als Einzeiler

f = foldr S N 

Es ist die beste Lösung solange der leere Fall sinnvoll ist.

B) verwendet Vielleicht:

Auf der anderen Seite, wenn f [] nicht sinnvoll definiert werden kann, ist es noch schlimmer. Teilfunktionen werden oft als hässlich angesehen. Um es vollständig zu machen, können Sie Maybe verwenden. Definieren

f [] = Nothing 
f [x] = Just (k x) 
f (x:xs) = Just (g x w) 
      where Just w = f xs 

Es ist eine Gesamtfunktion - das ist besser.

Aber jetzt können Sie die Funktion in umschreiben:

f [] = Nothing 
f (x:xs) = case f xs of 
       Nothing -> Just (k x) 
       Just w -> Just (g x w) 

, die eine richtige Falte ist:

addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux 
addElement x Nothing = Just (N x) 
addElement x (Just w) = Just (S x w) 

f = foldr addElement Nothing 

Im Allgemeinen Falten ist idiomatisch und sollte verwendet werden, wenn Sie die Rekursion Muster passen. Andernfalls verwenden Sie explizite Rekursion oder versuchen Sie, vorhandene Kombinatoren erneut zu verwenden. Wenn es ein neues Muster gibt, machen Sie einen Kombinator, aber nur, wenn Sie das Muster oft verwenden - sonst ist es übertrieben. In diesem Fall ist das Muster für nicht leere Listen gefaltet, die definiert sind durch: data List a = End a | Cons a (List a).

Answer 2

Wenn ich die Frage richtig verstanden habe, dann ist hier meine Bewertung Ihrer Optionen:

1. Es ist wahrscheinlich ein bisschen böse zu haben, die passen Tableau aus unter dem Konstruktor (vermutlich beliebig komplex?) um diese Funktion zu schreiben. Dieser Ansatz erscheint etwas brüchig, obwohl es wahrscheinlich gut funktionieren würde.

2. Ich sehe nicht die Notwendigkeit, das Muster zu verallgemeinern, da es eine rekursive Funktion ist, die auf einer rekursiven Struktur arbeitet. Das Einführen eines Musters höherer Ordnung würde (glaube ich) die tatsächliche Logik hinter dem Ausführen einer rekursiven Traversierung dieser Datenstruktur verschleiern.

3. Ich denke, das macht sehr viel Sinn. Wie Sie gesehen haben, handelt es sich um ein einigermaßen anerkanntes "Muster", aber ich denke, es passt gut zur Beschreibung des Algorithmus, um es genau so aufzuschreiben. Es mag nicht so verallgemeinerbar oder wiederverwendbar sein, aber da es im Wesentlichen der Kern des algorithmischen Ansatzes ist, denke ich, dass es sinnvoll ist, die Fälle direkt zu schreiben, wie Sie es in einer Funktion wie f getan haben. Dies wäre mein bevorzugter Ansatz.

Leider eine besonders konkrete Antwort auf nicht bieten, aber es ist eine ziemlich subjektive Antwort, so angesichts die drei oben genannten Optionen, ich würde Option 3 aus Gründen der Übersichtlichkeit und Lesbarkeit wählen.