Liste und halten Zustand

Question

Ich versuche, diesen Pseudo-Code in Haskell zu verwandeln:

function whatever(list) 
    int somestate 
    foreach list as item 
     if item === 1 
       state++ 
     else 
       state-- 
    endforeach 
    return state 

Jetzt so etwas wie dies offensichtlich falsch ist (Zustand 3):

test :: [Int] -> Int 
test item 
     | head item > 1 = 1 
     | otherwise = newItem 
     where newItem = tail item 

Was ist die beste So etwas in Haskell zu erreichen?

Answer 1

Sie können unter Verwendung eines anderen Parameter an die Funktion dies einfach tun:

test [] counter = counter 
test (x:xs) counter 
    | x == 1 = test xs (counter + 1) 
    | otherwise = test xs (counter - 1) 

Hier verwenden wir Muster (x:xs) Anpassung der Spitze der Liste zu x zu binden und den Schwanz der Liste xs. Sobald wir zu der leeren Liste kommen, geben wir den letzten Zähler zurück.

Wir müssen diese Funktion mit einem anfänglichen Zähler nennen würde, wie so

test [1..3] 0

Allerdings können wir das besser tun, indem sie nicht durch Akkumulieren der Zähler in einem ersten Zähler, passieren zu müssen als wir gehen, so.

test [] = 0 
test (x:xs) 
    | x == 1 = test xs + 1 
    | otherwise = test xs - 1 

Diesmal jedes Mal, wenn der Wert gleich eins ist, fügen wir ein zu dem Ergebnis der Funktion auf die leere Liste. Schließlich werden wir den Basisfall treffen, der 0 ist, und der Rest der Werte wird addiert, was uns den endgültigen Wert gibt.

Allerdings ist dieses Muster der Rekursion über eine Liste und etwas, was der Wert sehr häufig ist. Wir können eine Falte verwenden:

test = foldl' (\acc x -> if x == 1 then acc + 1 else acc - 1) 0 

Dies ist im Wesentlichen unsere vorherige rekursive Funktion.

Es gibt Möglichkeiten, persistenten Zustand in Haskell zu speichern, aber im Allgemeinen brauchen wir sie nicht in einfachen Fällen wie diesem.

Answer 2

Ich glaube, ich würde wahrscheinlich tun:

whatever xs = length ones - length others where 
    (ones, others) = partition (1==) xs 

Das einzige, was mich zu denken geben würde einige Überlegungen für lange Listen ist; Wenn es wichtig ist, dass die Liste nicht alle gleichzeitig im Speicher ist, würde dies nicht gut funktionieren.

Answer 3

Eine weitere Alternative:

> sum . map (bool (-1) 1 . (==1)) $ [1,2,2] 
-1 
> sum . map (bool (-1) 1 . (==1)) $ [1,2,2,1] 
0 
> sum . map (bool (-1) 1 . (==1)) $ [1,2,2,1,1,1,1,1] 
4 

Beachten Sie, dass bool (-1) 1 . (==1) auch grundlegende Syntax als

(\x -> if x==1 then 1 else -1) 

Answer 4

Sie nur zwicken und mische ein paar Worte um, wie

mit geschrieben werden können

foo (list) = 
    -- int somestate 
    -- foreach list as item 
    -- foreach item in list 
      do item <- list 
       if item == 1 
       then return incr -- state 
       else return decr -- state 
    -- return state 

incr state = state + 1 
decr state = state - 1 

und schon holen Sie sich eine Sache, mit einem Typ daraus abgeleitet!Das ist

foo :: (Num a, Num b, Monad m, Eq a) => m a -> m (b -> b) 

Wir wissen m ~ [] so ist es tatsächlich

foo :: (Num a1, Num a, Eq a) => [a] -> [b -> b] 

Also, was können wir mit dem Bündel von state-Aktualisierungsfunktionen zu tun, wie incr/decr, in einer Reihe? Ein paar Dinge:

import Control.Monad 
import Data.Monoid 
import Data.Foldable 

sequence . foo :: (Num a, Num b, Eq a) => [a] -> b -> [b] 

foldr (.) id . foo :: (Num a, Num b, Eq a) => [a] -> b -> b 

appEndo . foldMap Endo . foo 
        :: (Num a, Num b, Eq a) => [a] -> b -> b 

foldl (.) id . foo :: (Num a, Num b, Eq a) => [a] -> b -> b 

appEndo . getDual . foldMap (Dual . Endo) . foo 
        :: (Num a, Num b, Eq a) => [a] -> b -> b 

Nicht die erste, sicherlich.

Es scheint, dass der mit foldl das Ticket hier ist. Aber dann wieder geht es gegen nicht sunt multiplanda praeter necessitatem. Also wirklich, es ist

foo :: (Num t, Num a, Eq a) => [a] -> t -> t 
foo = foldr g id 
    where 
    g x r state | x==1 = r (incr state)  -- or even `r $! incr state` 
      | otherwise = r (decr state) --   `r $! decr state` 

oder einfacher,

foo :: (Num t, Num a, Eq a) => [a] -> t -> t 
foo = foldr g id 
    where 
    g x r | x==1 = r . incr 
     | otherwise = r . decr 

oder auch nur

foo :: (Num t, Num a, Eq a) => [a] -> t -> t 
foo = foldr (\x -> if x==1 then (. incr) else (. decr)) id 

das ist eigentlich das mit dem Dual wir alle zusammen hatten. Ich denke. Viel Spaß dabei, dies (oder anders) zu bestätigen. :)

---

Update:foldr (.) id . foo in eine Funktion Fusing führt zu einem noch schöneren

foo :: (Num t, Num a, Eq a) => [a] -> t -> t 
foo = flip $ foldr (\x -> if x==1 then incr else decr) 

aber es verarbeitet den Zustand in der umgekehrten Reihenfolge.