Trattare con (i rischi di) sequenze infinite in Haskell

Question

Trattare con (i rischi di) sequenze infinite in Haskell

#1 da (5 voti)
#2 da (3 voti)
#3 da (-1 voti)

7

Sono un paio di settimane da dilettarsi con haskell e ho fatto una bella ammaccatura in Learn You A Haskell. Mi sento come se molte delle classi di tipi e le implementazioni comuni fino agli applicativi e alle monadi abbiano molto senso per me e capisco come funzionano, ma mi manca ancora molta esperienza pratica.

Una cosa che mi infastidisce, derivante da uno sfondo prevalentemente imperativo / OOP, è il concetto di valori / funzioni che valutano le liste infinite. Ovviamente posso vedere come possono essere usati per scrivere alcune definizioni in modo molto teso e sono sicuramente utili in molti casi che non riesco nemmeno a immaginare. Mi chiedo quale sia l'approccio comune per mitigare i loro rischi. Se in qualsiasi punto del tuo codice valuta casualmente un elenco infinito "completamente", il tuo programma si bloccherà. Questo è possibile anche nelle lingue imperative (alcune implementazioni delle interfacce IEnumerable / Iterator da C # / Java per esempio), ma è la mia esperienza che le persone raramente fanno questo perché è ... beh, pericoloso.

Uno dei grandi vantaggi di Haskell è il controllo dei tempi di compilazione. Possiamo fare controlli sulla compilazione per gestire questo rischio? O scriviamo test per questo? O siamo semplicemente "mai così stupidi da farlo, e se lo facciamo, lo notiamo dopo 1 secondo quando lo eseguiamo nel REPL"? O ci sono convenzioni di denominazione?

Mi rendo conto che probabilmente è un po 'soggettivo, ma sicuramente esistono idiomi comuni?

haskell

posta sara 27.04.2016 - 09:30

fonte

3 risposte

Leggi altre domande sui tag haskell

Rompere l'applicazione ASP .NET MVC in microservizi .Net Best Practices: errori comuni introdotti da refactoring, incuria e neofiti

score 5 · Answer 1

Questo rischio di produrre accidentalmente una lista infinita è lo stesso di un loop infinito. L'unica differenza è che nelle impostazioni pigre potrebbe non manifestarsi affatto (se non si valuta l'intera struttura), e se lo fa, sarà in un posto diverso, che potrebbe essere più difficile eseguire il debug.

Un'opzione consiste nell'usare strutture di dati forzatamente finite come Vector o Seq . Se desideri utilizzare gli elenchi collegati, puoi definirne uno con una colonna vertebrale rigida come

data List a = Nil | Cons a !(List a)

Mentre attualmente Haskell non lo fa, esiste un concetto di Programmazione funzionale totale che consente di garantire per sintattica controlla che tutti i calcoli terminino. In particolare, impedisce la creazione di strutture di dati infiniti (dati), o in alternativa consente loro ma scartando sempre un livello finisce sempre ( codata ).

score 3 · Answer 2

Penso che una buona regola pratica sia: stai lontano da operazioni che divergono su strutture infinite . Ciò non significa non usarli mai, ma piuttosto rimandarli il più possibile nel tuo programma.

Ci vuole un po 'di esperienza per imparare a riconoscere queste operazioni, ma questo arriva con il tempo. Alcuni esempi sono length , sum e foldl' ; e un fatto utile è che spesso è possibile evitare le divergenze passando da queste alle operazioni basate su scanl . Ad esempio, la funzione di prendere la somma di tutti i numeri in una lista divergerà per gli elenchi infiniti:

sum :: Num a => [a] -> a
sum = foldl' (+) 0

-- 'sum [1..]' diverges...

Ma la funzione per calcolare le somme di tutti i prefissi di una lista funziona bene con liste infinite:

sums :: Num a => [a] -> a
sums = scanl' (+) 0

-- 'take 10 (sums [1..])' => '[0,1,3,6,10,15,21,28,36,45]'

Tuttavia, come sottolinea jozefg in un commento, un altro modo comune per evitare questi problemi è solo quello di utilizzare tipi di dati che supportano solo le raccolte finite. Gli elenchi di Haskell sono ampiamente utilizzati, ma lo sono anche Map , Set , Vector , ByteString e Text , tutti garantiti-finiti, e ognuno offre alcune caratteristiche o compromessi diversi da ciò che fanno gli elenchi. Questo arriva alla tua ultima domanda:

One of the big advantages of Haskell is the compile time checks you get. Can we do any compile time checks to deal with this risk?

Sì, puoi farlo usando un altro tipo di dati che garantisce la finitezza. Non esitare a provare qualcuno di quelli che ho menzionato prima.

score -1 · Answer 3

In un linguaggio pigro, è molto più difficile valutare completamente un elenco infinito, a meno che non si utilizzino funzioni che sono esplicitamente rigide (ad esempio seq o funzioni implementate, come foldl '). Se rimani lontano da questi, verranno generati solo gli input rilevanti per il calcolo dell'output. Quindi, se ti limiti a elaborare elenchi potenzialmente infiniti con foldr, map e take, probabilmente non avrai mai un problema.