Recursive state-Monade für die Akkumulation von Wert, während den Aufbau einer Liste?

Ich bin vollkommen neu in Haskell also entschuldigt, wenn die Frage ist dumm.

Was ich will zu tun ist, rekursiv eine Liste aufbauen, während gleichzeitig Aufbau eines akkumulierten Wertes basiert auf der rekursiven Aufrufe. Dies ist für ein problem, ich mache für einen Coursera-Kurs, damit ich nicht nach den genauen problem, aber etwas analoges.

Sagen Sie zum Beispiel, wollte ich eine Liste von ints und Doppel jeweils (ohne Berücksichtigung der für die Zwecke des Beispiels, dass ich konnte einfach map), aber ich auch wollte zählen, wie viele Male die Zahl '5' in der Liste erscheint.

Damit zu tun, die Verdoppelung könnte ich dies tun:

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

So weit, So einfach. Aber wie kann ich auch pflegen Sie eine zu zählen, wie viele Male x ist eine fünf? Die beste Lösung, die ich habe, ist die Verwendung eines expliziten Akkumulators wie diese, die ich nicht mag, wie es kehrt die Liste, also müssen Sie tun, ein reverse-am Ende:

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 dieser sollte in der Lage sein, um behandelt werden schöner durch die State Monade, die ich nicht verwendet haben, bevor, aber wenn ich versuche, eine Funktion zu konstruieren, passen die Muster, die ich gesehen habe, bekomme ich stecken bleiben, weil der rekursiven Aufruf foo. Gibt es eine schönere Art, dies zu tun?

EDIT: muss ich diese Arbeit für sehr lange Listen, so dass jede rekursive Aufrufe werden müssen tail-recursive zu. (Das Beispiel habe ich hier verwaltet werden tail-rekursive Dank Haskell 's" tail recursion modulo cons').

Verwandte Frage: "Tail-Optimierung - Garantie- loop-Codierung in Haskell".
In welchem Sinne ist dein Beispiel tail-rekursiv? Ich glaube, dass es sich thunks und bewirkt, dass ein "memory leak". Selbst ein einfacher Aufruf reverse genug zu sein scheint, um einen Speicherverlust verursachen.
Wenn ich sage, es ist tail-rekursive, ich meinte die einfache Karte Beispiel, nicht die zweite code-fragment. TBH ich habe eine harte Zeit, herauszufinden, was ist und was nicht effizienten code in Haskell - es scheint zu funktionieren völlig anders als jede andere Sprache, die ich verwendet habe! Glaube, ich brauche zu tun, etwas mehr darüber zu Lesen 🙂

InformationsquelleAutor Russell | 2013-07-07

8

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 ausgedrückt mit 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)
```
Den kumulierten Wert ist, ist ein paar der beiden Operationen.

Hinweise:
- Haben Sie einen Blick auf Schöne Falten. Es zeigt einen schönen Weg, wie man solche Berechnungen zusammensetzbar.
- Können Sie State für die gleiche Sache, als auch, durch das betrachten jedes element als eine stateful-Berechnung. Das ist ein bisschen übertrieben, aber durchaus möglich. In der Tat, jede Falte kann ausgedrückt werden als eine Sequenz von State Berechnungen:
```
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 von xs zu einer stateful-Berechnung durch modify . f :: b -> State a (). Dann verbindet es eine Liste solcher Berechnungen in einer Art State a () (er verwirft die Ergebnisse der monadischen Berechnungen, nur hält die Wirkung). Schließlich führen wir diese stateful Berechnung auf z.
- Wird, dass der Bau sich tail-rekursiv? Es ist definitiv etwas Arbeit nach den rekursiven Aufruf. Ich kenne Haskell hat einige clevere Optimierungen - ist das eine?
- Nein, es ist nicht tail-rekursiv, und es gibt Gründe dafür. Ersten auf diese Weise ist es mehr faul - Sie Lesen das erste element der Liste zugeordnet, und nur das erste element der ursprünglichen Liste ist verbraucht. Faulheit ist bevorzugt in den meisten Fällen über tail-Rekursion. Zweitens, für eine effiziente tail-rekursive Lösung, die Sie haben würden, zu konsumieren, die Liste von Anfang an, aber bauen das Ergebnis am Ende. Also, wenn Sie eine tail-rekursive map, es wird die Rückseite der Liste. (Dies kann nützlich sein, manchmal, wenn Sie kümmern sich nicht um die Reihenfolge.)
- Ich habe das Gefühl, es ist etwas bang-Muster fehlt hier. 🙂
- Fühlen Sie sich frei, um es hinzuzufügen)
- Danke, ich löste mein problem mit einer variation von diesem! Haben eine harte Zeit zu verstehen, was ist und was nicht effizienten code in Haskell - es scheint zu funktionieren in einer anderen Weise zu irgendeiner anderen Sprache, die ich verwendet habe - kann Sie empfehlen, alles zu Lesen über es?
- Ich würde nicht zu viel sorgen machen über die Optimierung beim lernen wichtiger ist, zu schreiben, schön, idiomatische und lesbaren code. Wenn Sie möchten, würde ich vorschlagen, Sie zu Lesen Profiling und-Optimierung in Real World Haskell (in der Tat würde ich vorschlagen, das ganze Buch Lesen :-)).
- Danke, werde es tun! Ich würde nicht normalerweise sorgen zu viel über Optimierung, aber den Weg habe ich gewählt um zu lernen, ist dabei ein Coursera-Kurs auf-algorithmen unter Benutzung von Haskell... so-Optimierung ist sehr wichtig für die Probleme 🙂
InformationsquelleAutor Petr Pudlák

Mit State Monade es kann auch etwas sein wie:

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

Vielen Dank, diese Antwort hat mir geholfen, in den Griff zu bekommen, wie die State-Monade funktioniert.... ein bisschen zumindest.

InformationsquelleAutor Ankur

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.