Pattern per lo stato di tracciamento nel codice Haskell ricorsivo

Question

Pattern per lo stato di tracciamento nel codice Haskell ricorsivo

#1 da (2 voti)
#2 da (1 voti)

1

Un pattern frequente nel mio codice Haskell è la ricorsione basata sull'elemento per la trasformazione di una lista con uno stato portato generato usando i dati nella lista. Di solito, questo appare in questo modo:

doSomething :: (SomeA a, SomeB b) => [a] -> [b]
doSomething xs = doSomethingWithState xs []
    where
        doSomethingWithState [] _ = []
        doSomethingWithState (x:xs) state
            | someTest x state = someChange x : (doSomethingWithState xs newState)
            | otherwise = someOtherChange x : (doSomethingWithState xs newState)

Ad esempio, supponiamo di voler contare quanti di ciascun elemento appaiono in un elenco, trasformando qualcosa come [1, 3, 3, 3, 4, 7, 7, 8, 8, 9] in [(9,1),(8,2),(7,2),(4,1),(3,3),(1,1)] .

Probabilmente farei qualcosa del tipo:

import Data.List
import Data.Maybe

counts :: (Eq a) => [a] -> [(a, Int)]
counts xs = countsWithState xs []
    where
        countsWithState [] state = state               -- End of list, stop here
        countsWithState (x:xs) state = countsWithState xs $ transformState state x
        transformState state x                         -- To get the state...
            | isNothing $ lookup x state = (x, 1) : state -- Add new elem if new
            | otherwise = incrElem x state             -- Increment elem if not
        incrElem x [] = []                             -- Should never be reached
        incrElem x ((index, value):elems)              -- Searching through list...
            | index == x = (index, (value+1)) : elems  -- Increment if found
            | otherwise = (index, value) : incrElem x elems -- Try next if not

In un esempio molto più semplice ma molto simile, se provassi a mantenere la media corrente di tutti gli elementi in una lista, trasformando qualcosa come [1, 7, 4, 18, 7, 1, 8, 2, 8, 6, 18, 12] in [1.0, 4.0, 4.0, 7.5, 7.4, 6.33..., 5.57..., 6.0, 6.22..., 6.2, 7.27..., 7.66...] dove ogni elemento nella lista di output è la media di quello elemento e tutti gli elementi precedenti nella lista di input, potrei fare qualcosa di simile a questo:

runningAvg :: (Fractional a) => [a] -> [a]
runningAvg xs = runningAvgWithState xs 0 1
    where
        runningAvgWithState [] _ _ = []
        runningAvgWithState (x:xs) currentSum currentElems
            = (currentSum + x) / currentElems
            : runningAvgWithState xs (currentSum + x) (currentElems + 1)

Si noti che il modello è lo stesso. Prendi una funzione ricorsiva di una lista, definiscila in termini di una versione modificata nascosta con stato aggiunto, e con ogni round trasforma lo stato e genera i risultati calcolati secondo necessità. Questo schema emerge continuamente nel mio codice Haskell .

Esiste un modo più naturale di implementare questo tipo di comportamento, senza una più complicata funzione xWithState che esegue lo spettacolo e aggiungendo inutili verbosità e complessità?

recursion design-patterns functional-programming haskell

posta TheEnvironmentalist 16.07.2018 - 00:40

fonte

2 risposte

Leggi altre domande sui tag recursion design-patterns functional-programming haskell

formato di file diff diffuso universalmente Dove memorizzare la configurazione dell'applicazione

score 2 · Answer 1

Il tuo doSomething è più o meno mapAccumL da Data.List , tranne che hai gettato via l'accumulatore (cioè, lo stato) alla fine. Cioè, potresti scriverlo come:

doSomething :: [a] -> [b]
doSomething = snd . mapAccumL step []
  where step state x = (newState, newX)
          where newX | someTest x state = someChange x
                     | otherwise        = someOtherChange x
                newState = state

In particolare, la media corrente potrebbe essere simile a:

runningAvg :: (Fractional a) => [a] -> [a]
runningAvg = snd . mapAccumL step (0,0)
  where step (total, n) x = ((total', n'), total' / fromIntegral n')
          where total' = total + x
                n' = n + 1

Il tuo esempio di conteggio è alquanto diverso, poiché non produce un elenco della stessa "forma" dell'input. Invece, lo "stato" è l'insieme dei conteggi, e si restituisce lo "stato" finale (insieme finale di conteggi) alla fine. Questo è solo un foldl , come altri hanno notato.

count :: (Eq a) => [a] -> [(a, Int)]
count = foldl step []
  where step cnts x = bumpCount x cnts

che sarebbe semplice se non fosse per il fatto che il mantenimento di un insieme di conteggi come un elenco di associazioni rende bumpCount il tipo di lordo. La versione di @ amon di bumpCount (cioè, count' ) sembra soddisfacente oppure potresti scriverla come la seguente:

bumpCount :: (Eq a) => a -> [(a, Int)] -> [(a, Int)]
bumpCount x = foldr step [(x,1)] . tails
  where step ((y,n):rest) acc | x == y    = (y,n+1) : rest
                              | otherwise = (y,n)   : acc
        step [] acc = acc

A proposito, questo bumpCount fold è in realtà piuttosto incredibile. Nonostante sia una "piega", smette di cercare l'elenco una volta trovato e mostra un conteggio corrispondente.

score 1 · Answer 2

Il modello di delegare il lavoro principale a una funzione ricorsiva annidata con uno o più argomenti dell'accumulatore è perfettamente normale nella programmazione funzionale, sia che si utilizzi Lisp, Haskell o Scala. Finché ti senti a tuo agio nell'esprimere il codice in modo ricorsivo, spesso non è necessario tenere traccia di nessuno stato mutabile.

Nota che in Haskell, la funzione interna in una funzione "pubblica" foo è spesso chiamata foo' (foo-prime).

In una certa misura, vedrai la stessa interfaccia pubblica rispetto all'attuale divisione dell'implementazione su linguaggi OOP come Java, ad esempio:

class Foo {

  public int doTheThing(int x, int y) {
    // validate x and y
    doTheThing(x, y, new HashMap<>());
  }

  private int doTheThing(int x, int y, HashMap<Integer, List<Integer>> cache) {
   ...
  }
}

Tornando a Haskell, si potrebbe comunque notare che "fare qualcosa per ogni elemento mentre si tiene traccia di alcuni stati" è un pattern ricorrente che può essere astratto, simile a un'operazione di scansione, di piegatura o riduzione. Ad esempio, la tua funzione counts potrebbe essere scritta in questo modo (notando che transformState e incrElem possono essere combinati per aggiungere semplicemente un nuovo oggetto se incrElem colpisce il caso base):

counts :: (Eq a) => [a] -> [(a, Int)]
counts = foldr counts' []
  where counts' x [] = [(x, 1)]
        counts' x ((y, n):rest) = if x == y then (x, n + 1):rest
                                            else (y, n):(counts' x rest)

Anche la funzione counts' è un tipo di piega, ma scriverlo come uno è più complicato.