Perché il seq in Haskell deve avere una regola speciale per il fondo?

Question

Haskell Report 2010 dice che seq "indebolisce le proprietà parametricity di Haskell", come "⊥ non è lo stesso di \ x -> ⊥, dal momento ss può essere usato per distinguerli" [1].

Sembra che accade esattamente a causa di una norma esplicita:

seq ⊥ b = ⊥ 

Mi chiedevo perché questo caso particolare è stato introdotto? Ci deve essere una ragione per la quale

seq a b = b 

non sarebbe sufficiente, e seq ha bisogno di una definizione più complicato con quel caso speciale:

seq ⊥ b = ⊥ 
seq a b = b, if a ≠ ⊥ 

[1] https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2

---

[ modifica] Chiarifica la domanda, ecco un altro angolo su di esso. Perché non seq può essere definito in questo modo:

seq :: a -> b -> b 
seq a b = b 

Con una regola che seq è una funzione speciale che valutare il suo primo argomento "il più possibile". Se la valutazione risulta in HNF, allora l'argomento è completamente valutato. Se risultasse in un'eccezione o un valore di fondo, questi sarebbero memorizzati e verrebbero lanciati o restituiti ogni volta che il primo argomento verrebbe effettivamente utilizzato nella valutazione del secondo argomento.

È un po 'zoppo, ma penso che dovrebbe rendere le mie domande un po' più chiare. Non si tratta di come funziona seq. Riguarda le intenzioni del design attuale.

Forse ci sono alcune ovvie ragioni, dal punto di vista dell'implementazione. O forse avrebbe delle conseguenze, come l'incapacità di fornire alcune proprietà utili che sono attualmente basate sullo seq stato definito con quel caso speciale per il fondo. O forse ci sono altre connessioni di cui non sono a conoscenza. Questo è quello che sto quirious circa :)

Answer 1

Una risposta sopra contiene una discussione che alla fine mi ha permesso di capire cosa mi mancava. Penso che quanto segue sia il succo di ciò.

La definizione proposta richiederebbe una soluzione al problema dell'arresto, se ci limitassimo a un solo thread. ⊥ significa 3 cose diverse: eccezioni, errori e non terminazione. I primi due potrebbero essere affrontati, ma il terzo è impossibile da risolvere in un caso generale.

Potrebbe essere possibile fornire un'implementazione che utilizzi un thread aggiuntivo per eseguire la valutazione di a. Ma sembra una soluzione molto più complicata, possibilmente, con le sue insidie.

Answer 2

Il punto di seq x y è quello di valutare x e poi tornare y. Haskell è pigro, quindi una definizione come

seq x y = y 

non lo farà, dal momento che x è lasciato non valutata. Se sapessimo x :: Int potremmo scrivere

seq x y = case x of 
      0 -> y 
      _ -> y 

costringendo x da valutare. Possiamo giocare lo stesso trucco per elenchi, alberi, ecc. Con un'eccezione significativa: funzioni. Se x è una funzione, non è possibile eseguire case (schemi banali a parte, che non richiedono una valutazione forzata).Le funzioni sono valutati solo su chiamata, in modo che possano tentare

seq x y = case x 12 of -- let's pretend it's an Int->Int function 
      0 -> y 
      _ -> y 

questo costringerà la valutazione dei x (bene!), Ma valuterà anche x 12 (male!).

Si scopre che sappiamo che scrivere seq nel lambda calcolo è in realtà impossibile: teoria formalizza l'intuizione intorno "Non siamo in grado di forzare una funzione a meno che non si applica, e se applichiamo stiamo anche forzando il risultato" .

Quindi, in Haskell, seq è stato aggiunto come operazione primitiva, non definibile in termini di tutto il resto. L'implementazione di seq è rigorosa sul primo argomento, anche se non è necessario valutarlo per restituire il secondo.

Dal seq fa qualcosa al di fuori del lambda-calcolo, rompe alcune cose nella teoria, come la parametrricità, ma questa perdita non è così grande da rovinare l'intera lingua, che gode ancora molte delle belle proprietà teoriche di il calcolo lambda.

Storicamente, se la memoria non m'inganna, presto Haskell stava per includere una classe per seq:

class Seq a where 
    seq :: a -> b -> b 

e questa classe è stata instantianted su ogni tipo ma le funzioni di, in modo che parametricity è stato conservato come bene. Successivamente, è stato deciso che non era pratico aggiungere tutti i vincoli Seq a nel codice, poiché un singolo utilizzo di seq avrebbe richiesto di aggiungere un numero elevato di vincoli. Quindi, seq è stato trasformato in un primitivo, a costo di rompere un po 'la teoria.