Moneta trybu rekurencyjnego do gromadzenia wartości podczas budowania listy?

Question

Jestem całkowicie nowy dla Haskella, więc przepraszam, jeśli pytanie jest głupie.

Co chcę zrobić, to rekurencyjnie zbudować listę podczas w tym samym czasie budowanie skumulowanej wartości w oparciu o rekurencyjne połączenia. To jest dla problemu, który robię dla kursu Coursera, więc nie opublikuję dokładnego problemu, ale coś analogicznego.

Powiedz na przykład chciałem wziąć listę int i double każdy (ignorując dla celów przykładu, że może po prostu wykorzystać map), ale również chciał policzyć ile razy liczba ' 5 'pojawi się na liście.

więc zrobić podwojenie mogę to zrobić:

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

tej pory tak łatwo. Ale w jaki sposób mogę również sprawdzić, ile razy x ma pięć? Najlepszym rozwiązaniem mam jest użycie wyraźny akumulator jak ten, który mi się nie podoba, ponieważ odwraca listy, więc trzeba zrobić odwrotnie na koniec:

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

Ale czuję się jak to powinno być łatwiejsze do obsłużenia przez monadę State, której wcześniej nie używałem, ale kiedy próbuję skonstruować funkcję, która pasuje do wzorca, który widziałem, utknąłem z powodu rekursywnego połączenia z foo. Czy jest lepszy sposób na zrobienie tego?

EDYCJA: Potrzebuję tego do pracy na bardzo długich listach, więc wszelkie wywołania rekurencyjne muszą być również rekursywne. (Przykład, który tutaj mam, jest rekursywny w ogonach dzięki "rekursji modulo cons" Haskella).

Answer 1

Jest to prosty krotnie

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) 

lub eksprymowane przy użyciu 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) 

Skumulowana wartość jest para obu tych operacji.

Uwagi:

• Zapraszamy do obejrzenia Beautiful folding. Pokazuje to, jak sprawić, aby takie obliczenia były kompozycyjne.

• Możesz również użyć State dla tego samego, wyświetlając każdy element jako obliczenia stanowe. To trochę przesada, ale z pewnością możliwe. W rzeczywistości każdy zagięcia mogą być wyrażone jako sekwencja State obliczeń:

  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 
  

  funkcji mapM_ pierwsze mapy każdy element xs do pełnostanową obliczeń według modify . f :: b -> State a(). Następnie łączy listę takich obliczeń w jeden z typu State a() (odrzuca wyniki monadycznych obliczeń, po prostu utrzymuje efekty). Na koniec uruchamiamy to obliczenia stanowe na z.

Answer 2

Korzystanie State monady może to być coś takiego:

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