Übertragung eines Imperativs for-Schleife in idiomatischen Haskell

Question

Ich habe einige Schwierigkeiten, imperative Algorithmen in einen funktionalen Stil zu übertragen. Das Hauptkonzept, mit dem ich mich nicht herumschlagen kann, ist, wie man Sequenzen mit Werten entsprechend ihrer Position in der Sequenz füllt. Wie würde eine idiomatische Lösung für den folgenden Algorithmus in Haskell aussehen?

A = unsigned char[256] 
idx <- 1 
for(i = 0 to 255) 
    if (some_condition(i)) 
     A[i] <- idx 
     idx++ 
    else 
     A[i] = 0; 

Der Algorithmus erstellt im Grunde eine Nachschlagetabelle für die Zuordnungsfunktion eines Histogramms.

Kennen Sie irgendwelche Ressourcen, die mir helfen könnten, diese Art von Problem besser zu verstehen?

Answer 1

Eine der Kernideen in der funktionalen Programmierung ist Algorithmen zum Ausdruck bringen als Daten Transformationen. In einer faulen Sprache wie Haskell können wir sogar einen Schritt weiter gehen und faule Datenstrukturen als verdinglichte Berechnungen betrachten. In einem sehr realen Sinn sind die Listen von Haskell eher Schleifen als normale verkettete Listen: Sie können inkrementell berechnet werden und müssen nicht auf einmal im Speicher vorhanden sein. Gleichzeitig erhalten wir viele der Vorteile eines Datentyps wie die Fähigkeit, ihn zu übergeben und ihn mit einem Mustervergleich zu überprüfen.

In diesem Sinne besteht der "Trick" für das Ausdrücken einer for-Schleife mit einem Index darin, eine Liste aller möglichen Werte zu erstellen. Ihr Beispiel ist wahrscheinlich die einfachste Fall: i nimmt alle Werte 0-255, so können wir Haskells Einbau-Notation für Bereiche verwendet werden:

[0..255] 

Auf einem hohen Niveau, das ist Haskells Äquivalent for (i = 0 to 255); Wir können dann die tatsächliche Logik in der Schleife ausführen, indem wir diese Liste entweder durch eine rekursive Funktion oder eine Funktion höherer Ordnung aus der Standardbibliothek durchlaufen. (Die zweite Option ist sehr bevorzugt.)

Diese besondere Logik eignet sich gut für eine fold. Mit einer Falte können wir eine Liste nach Elementen aufnehmen und ein Ergebnis erstellen. Bei jedem Schritt erhalten wir einen Listenpunkt und den Wert unseres bisherigen Ergebnisses. In diesem speziellen Fall wollen wir die Liste von links nach rechts verarbeiten, während wir einen Index inkrementieren, also können wir foldl; Der eine schwierige Teil ist, dass es die Liste rückwärts produziert.

Hier ist die Art von foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b 

So ist unsere Funktion in unserem Zwischenwert nimmt und ein Listenelement und erzeugt einen aktualisierten Zwischenwert. Da wir eine Liste erstellen und einen Index verfolgen, ist unser Zwischenwert ein Paar, das beides enthält. Dann, wenn wir das Endergebnis haben, können wir den idx Wert ignorieren und umgekehrt die endgültige Liste erhalten wir:

a = let (result, _) = foldl step ([], 1) [0..255] in reverse result 
    where step (a, idx) i 
      | someCondition i = (idx:a, idx + 1) 
      | otherwise  = (0:a, idx) 

In der Tat, das Muster eine Liste der Transformation, während Spur einiger Zwischenzustand zu halten (idx in diesem Fall) ist üblich genug, so dass es eine eigene Funktion in Bezug auf die State Art hat. Die Kern Abstraktion ist ein bisschen mehr beteiligt (lesen Sie durch ["Sie hätten Monaden erfunden"] [Sie] für eine gute Einführung), aber der resultierende Code ist eigentlich recht angenehm zu lesen (außer für die Importe, ich denke: P) :

import Control.Applicative 
import Control.Monad 
import Control.Monad.State 

a = evalState (mapM step [0..255]) 1 
    where step i 
      | someCondition i = get <* modify (+ 1) 
      | otherwise  = return 0 

die Idee ist, dass wir über [0..255] Karte während irgendeinen Staates (der Wert von idx) im Hintergrund zu verfolgen. evalState ist, wie wir alle Rohrleitungen zusammenbringen und nur unser Endergebnis bekommen. Die Funktion step wird auf jedes Element der Eingabeliste angewendet und kann auch auf den Status zugreifen oder diesen ändern.

Der erste Fall der step Funktion ist interessant. Der Operator <* sagt ihm, das Ding auf der linken Seite zuerst zu tun, das Ding auf der rechten zweiten , aber den Wert auf der linken Seite zurückgeben. Dadurch können wir den aktuellen Status abrufen, ihn inkrementieren, aber immer noch den Wert zurückgeben, bevor inkrementiert wurde. Die Tatsache, dass unser Staatsbegriff eine erstklassige Entität ist und wir Bibliotheksfunktionen wie <* haben können, ist sehr mächtig - ich habe festgestellt, dass dieses spezielle Idiom wirklich nützlich für das Traversieren von Bäumen ist und andere ähnliche Idiome für anderen Code recht nützlich waren.

Answer 2

Loops können normalerweise mit verschiedenen fold Funktionen ausgedrückt werden. Hier ist eine Lösung, die foldl verwendet (Sie foldl' wechseln können, wenn Sie in ein Stackoverflow-Fehler führen):

f :: (Num a) => (b -> Bool) -> a -> [b] -> [a] 
f pred startVal = reverse . fst . foldl step ([], startVal) 
    where    
     step (xs, curVal) x 
      | pred x = (curVal:xs, curVal + 1) 
      | otherwise = (0:xs, curVal) 

Wie es zu benutzen? Diese Funktion verwendet ein Prädikat (someCondition in Ihrem Code), den Anfangswert eines Indexes und eine Liste von Elementen, die durchlaufen werden sollen. Das heißt, Sie können f someCondition 1 [0..255] aufrufen, um das Ergebnis für das Beispiel aus Ihrer Frage zu erhalten.

Answer 3

Je nachdem, welche Datenstruktur Sie verwenden möchten, gibt es mehrere Möglichkeiten, dieses Problem anzugehen. Das einfachste wäre wohl mit Listen und die Grundfunktionen in Prelude:

a = go 1 [] [0..255] 
    where 
     go idx out [] = out 
     go idx out (i:is) = 
      if condition i 
       then go (idx + 1) (out ++ [idx]) is 
       else go idx (out ++ [0]) is 

Dies verwendet die Arbeiter Muster mit zwei Akkumulatoren, idx und out, und es durchläuft nach unten den letzten Parameter, bis keine weiteren Elemente sind links, gibt dann out zurück. Dies könnte sicherlich in eine Art von fold umgewandelt werden, aber in jedem Fall wird es nicht sehr effizient sein, das Anhängen von Elementen an eine Liste mit ++ ist sehr ineffizient. Sie könnten es besser machen mit idx : out und 0 : out, dann mit reverse am Ausgang go, aber es ist immer noch keine ideale Lösung.

Eine andere Lösung könnte sein, die State Monade zu verwenden:

a = flip runState 1 $ forM [0..255] $ \i -> do 
     idx <- get 
     if condition i 
      then do 
       put $ idx + 1 -- idx++ 
       return idx  -- A[i] = idx 
      else return 0 

die sicherlich viel mehr zwingend notwendig aussieht. Die 1 in flip runState 1 zeigt an, dass Ihr Ausgangszustand idx = 1 ist, dann verwenden Sie forM (die aussieht wie eine for-Schleife, aber wirklich nicht) über [0..255], die Loop-Variable ist i, und dann ist es nur eine Frage der Implementierung des Rests die Logik.

Wenn Sie viel fortgeschrittener gehen möchten, könnten Sie die StateT und ST Monaden verwenden, um eine tatsächliche veränderbare Array mit einem Zustand zur gleichen Zeit zu haben. Die Erklärung, wie dies funktioniert, ist weit über den Rahmen dieser Antwort, aber:

import Control.Monad.State 
import Control.Monad.ST 
import qualified Data.Vector as V 
import qualified Data.Vector.Mutable as MV 


a :: V.Vector Int 
a = runST $ (V.freeze =<<) $ flip evalStateT (1 :: Int) $ do 
    a' <- lift $ MV.new 256 
    lift $ MV.set a' 0 
    forM_ [0..255] $ \i -> do 
     when (condition i) $ do 
      idx <- get 
      lift $ MV.write a' i idx 
      put $ idx + 1 
    return a' 

ich es vereinfachte ein bisschen so, dass jedes Element zu 0 von Anfang an festgelegt ist, beginnen wir mit einem Anfangszustand von idx = 1, Schleife über [0..255], wenn der aktuelle Index i die Bedingung erfüllt dann erhalten Sie die aktuelle idx, schreiben Sie es in den aktuellen Index, dann inkrementieren idx. Führen Sie dies als eine Stateful-Operation aus, dann frieren Sie den Vektor ein und führen Sie schließlich die monad-Seite der Dinge.Dies ermöglicht eine tatsächliche muable Vektor sicher in der ST Monade versteckt, so dass die Außenwelt nicht wissen, dass a Sie einige seltsame Dinge tun müssen.

Answer 4

Explicit Rekursion:

a = go 0 1 
    where go 256 _ = [] 
     go i idx | someCondition i = idx : go (i+1) (idx+1) 
        | otherwise  = 0 : go (i+1) idx 

Ausklappen: (Variante der expliziten Rekursion oben)

a = unfoldr f (0,1) 
    where f (256,_) = Nothing 
      f (i,idx) | someCondition i = Just (idx,(i+1,idx+1)) 
        | otherwise  = Just (0 ,(i+1,idx ))