Modellierung rekursive fmap (Art) über eine Liste

Question

Ich frage mich, was der beste Weg ist, das folgende Problem in einer funktionalen Programmiersprache (in diesem Beispiel Haskell) zu implementieren:

Sie haben eine Funktion (oder ein ' Weg '), die 2 Eingänge, mit dem Typ a und b, in 2 Ausgänge des gleichen Typs (zB: Half-Addierer). Lässt es f in Haskell nennen würde es diese Art von Art Signatur a -> b -> (a, b)

Und Sie haben eine Liste mit Elementen des Typs a. (oder eine andere Art von Datenstruktur).

nun mit einer anfänglichen b Ich mag die folgende Sache passieren (Konzept erläuterte rekursive Implementierung), wenn geliefert:

f Execute mit den anfänglichen b und dem ersten Elemente, das b und das Element mit dem Ausgang ändern der Funktion und wiederholen Sie für das nächste Element.

In Haskell:

exec _ [] _  = [] 
exec f (x:xs) b = let (x',b') = f x b in x':(exec f xs b') 

Was ist der beste/effizienteste Weg wäre, diese Art von Verhalten zu modellieren.

Answer 1

Es ist mapM für die State Monade.

OK, erweitern ein wenig.

Lassen Sie uns zunächst diese in GHCI eingeben und den Typ der exec Funktion siehe:

Prelude> let {exec _ [] _ = []; exec f (x:xs) b = let (x',b') = f x b in x':(exec f xs b')} 
Prelude> :t exec 
exec :: (t2 -> t1 -> (t, t1)) -> [t2] -> t1 -> [t] 

Es ist fast wie Sie beschrieben, außer dass t und t2 müssen nicht vom gleichen Typ sein. Das ist gut.

Nun, eine andere Beobachtung: Wir verlieren tatsächlich Informationen, wenn wir tun, was Sie beschreiben. Speziell wir werfen den letzten Wert von b (oder t, wie ghci es nennt) weg. Lasst uns es für einen Moment bewahren. wir können es immer später wegzuwerfen:

exec' _ [] b = ([], b) 
exec' f (x:xs) b = 
    let (x',b') = f x b 
     (xs', b'') = exec' f xs b' 
    in (x':xs', b'') 

Und GHCI sagt

Prelude> :t exec' 
exec' :: (t2 -> t1 -> (t, t1)) -> [t2] -> t1 -> ([t], t1) 

als wir

exec f xs b = fst $ exec' f xs b 

Aber jetzt ist die Art von exec' enthält ein klares Muster definieren können.Wir können es noch deutlicher machen:

type S b c = b -> (c, b) 
exec' :: (a -> S b c) -> [a] -> S b [c] 

Und jetzt ist es klar, dass S fast genau die State Monade (na ja, es ist tatsächlich Definition in einem modernen Ambiente ein bisschen komplizierter ist, aber nicht viel: https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-State-Lazy.html#t:StateT); wirklich, es ist nur ein newtype:

newtype State b c = State {runState :: b -> (c, b)} 

Und wenn wir die Art der exec‘verallgemeinern einen beliebigen Monade zu verwenden, anstatt State, bekommen wir

Monad m => (a -> m c) -> [a] -> m [c] 

Natürlich können wir nicht wissen, für sicher, dass so etwas tatsächlich existiert, da wir nur eine Implementierung für die Monade State haben, aber ... es tut. Es ist mapM genannt (auch hier ist es aktuelle Definition in der modernen Einstellung komplizierter ist: https://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:mapM) - was Sinn macht, da ohne eine Monade wäre es nur

(a -> c) -> [a] -> [c] 

und das ist genau die Art von map sein.

Natürlich können Sie nicht sicher sein, dass exec' IS mapM ohne Prüfung der letzteren Implementierung. Aber in Haskell passiert es oft, dass Dinge, die den gleichen Typ haben, wenn es vernünftig ist, ein und derselbe sind.

Es macht auch Sinn, dass State Monad irgendwie beteiligt wäre - schließlich verwenden Sie b als ein Zustand, ändern Sie es, wie Sie durch die Liste gehen.

Also, wenn exec' ist mapM, wie kommen wir zurück zu exec? Nun, wir müssen von dem monadischen Wert State b [c] zu nur [c] gehen, es etwas b füttern. Wir können - wieder - verallgemeinern; Nehmen wir an, wir gehen von State b d zu d, ohne die Liste zu erwähnen. Und noch einmal - es gibt eine Funktion wie diese, sie heißt evalState: https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-State-Lazy.html#v:evalState.

So, endlich können wir das Endergebnis produzieren:

eval f xs b = evalState (mapM (\x -> state (\b -> f x b)) xs) b 

, die wir

eval f xs b = evalState (mapM (\x -> state (f x)) xs) b 

oder nur

eval f xs = evalState (mapM (state . f) xs) 

oder sogar

verkürzen

eval f = evalState . mapM (state . f) 

Wir können es völlig Punkt frei machen, aber das wäre sinnlos sein (und enthalten zu viele Punkte):

eval = (evalState .) . mapM . (state .)