Rekursive Status-Monade zum Akkumulieren eines Wertes beim Erstellen einer Liste?

Question

Ich bin völlig neu zu Haskell so Entschuldigungen, wenn die Frage albern ist.

Was ich tun möchte, ist rekursiv erstellen Sie eine Liste, während gleichzeitig Aufbau eines akkumulierten Werts auf der Grundlage der rekursiven Aufrufe. Das ist für ein Problem, das ich für einen Coursera-Kurs mache, also werde ich das genaue Problem aber etwas analoges nicht posten.

Sagen Sie zum Beispiel ich eine Liste von ints und Doppeln jeden (ohne Berücksichtigung für die Zwecke des Beispiels, das ich gerade map verwenden könnte) nehmen wollte, aber ich auch wollte die Zahl "zählen, wie oft 5 'erscheint in der Liste.

So die Verdoppelung tun ich dies tun könnte:

foo []  = [] 
foo (x:xs) = x * 2 : foo xs 

So weit, so einfach. Aber wie kann ich auch zählen, wie oft x eine fünf ist? Die beste Lösung, die ich habe ist einen expliziten Speicher wie diese zu verwenden, was Ich mag es nicht, wie es die Liste umkehrt, so müssen Sie am Ende eines umgekehrt tun:

foo total acc []  = (total, reverse acc) 
foo total acc (x:xs) = foo (if x == 5 then total + 1 else total) (x*2 : acc) xs 

Aber ich fühle mich wie Dies sollte besser mit der Monade State gehandhabt werden, die ich vorher nicht benutzt habe, aber wenn ich versuche, eine Funktion zu konstruieren, die zu dem Muster passt, das ich gesehen habe, bleibe ich wegen des rekursiven Aufrufs an foo hängen. Gibt es einen schöneren Weg, dies zu tun?

EDIT: Ich brauche das für sehr lange Listen zu arbeiten, so dass alle rekursiven Aufrufe tail-recursive auch sein müssen. (Das Beispiel, das ich hier habe, schafft es dank Haskells "Tail Recursion Modulo Cons", tailrekursiv zu werden).

Answer 1

Dies ist eine einfache Falte

foo :: [Integer] -> ([Integer], Int) 
foo []  = ([], 0) 
foo (x : xs) = let (rs, n) = foo xs 
       in (2 * x : rs, if x == 5 then n + 1 else n) 

oder exprimiert unter Verwendung von foldr

foo' :: [Integer] -> ([Integer], Int) 
foo' = foldr f ([], 0) 
    where 
    f x (rs, n) = (2 * x : rs, if x == 5 then n + 1 else n) 

Der akkumulierte Wert ein Paar von den beiden Operationen.

Hinweise:

• Werfen Sie einen Blick auf Beautiful folding. Es zeigt eine schöne Möglichkeit, solche Berechnungen zusammensetzbar zu machen.

• Sie können State für die gleiche Sache auch verwenden, indem Sie jedes Element als stateful Berechnung betrachten. Das ist ein bisschen zu viel, aber sicher möglich. In der Tat kann jede Falte als eine Folge von Berechnungen State ausgedrückt werden:

  import Control.Monad 
  import Control.Monad.State 
  
  -- I used a slightly non-standard signature for a left fold 
  -- for simplicity. 
  foldl' :: (b -> a -> a) -> a -> [b] -> a 
  foldl' f z xs = execState (mapM_ (modify . f) xs) z 
  

  Funktion mapM_ ersten Karten jedes Element xs zu einer zustandsbehafteten Berechnung durch modify . f :: b -> State a(). Dann kombiniert es eine Liste solcher Berechnungen in eine vom Typ State a() (es verwirft die Ergebnisse der monadischen Berechnungen, behält nur die Effekte bei). Schließlich führen wir diese statusbehaftete Berechnung unter z aus.

Answer 2

State Monade Verwendung kann es so etwas wie sein:

foo :: [Int] -> State Int [Int] 
foo [] = return [] 
foo (x:xs) = do 
    i <- get 
    put $ if x==5 then (i+1) else i 
    r <- foo xs 
    return $ (x*2):r 

main = do 
    let (lst,count) = runState (foo [1,2,5,6,5,5]) 0 in 
     putStr $ show count