Pigrizia/rigore tra i dati e newtype

Question

Non riesco a capire perché questi due frammenti producano risultati diversi sotto la cosiddetta "analisi della severità dei poveri".

Il primo esempio utilizza data (ipotizzando una corretta esempio applicativo):

data Parser t a = Parser { 
     getParser :: [t] -> Maybe ([t], a) 
    } 

> getParser (pure (,) <*> literal ';' <*> undefined) "abc" 
*** Exception: Prelude.undefined 

La seconda utilizza newtype. Non c'è altra differenza:

newtype Parser t a = Parser { 
     getParser :: [t] -> Maybe ([t], a) 
    } 

> getParser (pure (,) <*> literal ';' <*> undefined) "abc" 
Nothing 

literal x è un parser che riesce consumando un gettone di ingresso se il suo argomento corrisponde al primo token. Quindi, in questo esempio, non riesce poiché ; non corrisponde a a. Tuttavia, l'esempio data vede ancora che il parser successivo non è definito, mentre l'esempio newtype non lo fa.

Ho letto this, this e this, ma non li capisco abbastanza bene da capire perché il primo esempio non è definito. Mi sembra che in questo esempio, newtype è più pigro di data, il contrario di ciò che le risposte hanno detto. (Almeno one other person è stato confuso da questo anche).

Perché il passaggio da data a newtype modifica la definizione di questo esempio?

---

Ecco un'altra cosa che ho scoperto: a questa istanza applicativa, il data parser sopra uscite undefined:

instance Applicative (Parser s) where 
    Parser f <*> Parser x = Parser h 
    where 
     h xs = 
     f xs >>= \(ys, f') -> 
     x ys >>= \(zs, x') -> 
     Just (zs, f' x') 

    pure a = Parser (\xs -> Just (xs, a)) 

che, a questa istanza, il parser data sopra non non uscita undefined (supponendo un'istanza Monad corretta per Parser s):

instance Applicative (Parser s) where 
    f <*> x = 
     f >>= \f' -> 
     x >>= \x' -> 
     pure (f' x') 

    pure = pure a = Parser (\xs -> Just (xs, a)) 

---

codice completo frammento:

import Control.Applicative 
import Control.Monad (liftM) 

data Parser t a = Parser { 
     getParser :: [t] -> Maybe ([t], a) 
    } 


instance Functor (Parser s) where 
    fmap = liftM 

instance Applicative (Parser s) where 
    Parser f <*> Parser x = Parser h 
    where 
     h xs = f xs >>= \(ys, f') -> 
     x ys >>= \(zs, x') -> 
     Just (zs, f' x') 

    pure = return 


instance Monad (Parser s) where 
    Parser m >>= f = Parser h 
    where 
     h xs = 
      m xs >>= \(ys,y) -> 
      getParser (f y) ys 

    return a = Parser (\xs -> Just (xs, a)) 


literal :: Eq t => t -> Parser t t 
literal x = Parser f 
    where 
    f (y:ys) 
     | x == y = Just (ys, x) 
     | otherwise = Nothing 
    f [] = Nothing 

Answer 1

Come probabilmente sapete, la differenza principale tra data e newtype è che con data è che data costruttori sono pigri mentre newtype è rigorosa, cioè dato i seguenti tipi

data D a = D a 
newtype N a = N a 

quindi D ⊥ `seq` x = x, ma N ⊥ `seq` x = ⊥.

Ciò che è forse meno noto, tuttavia, è che quando si pattern match su questi costruttori, i ruoli sono "invertiti", vale a dire con

constD x (D y) = x 
constN x (N y) = x 

poi constD x ⊥ = ⊥, ma constN x ⊥ = x.

Questo è ciò che accade nel tuo esempio.

Parser f <*> Parser x = Parser h where ... 

Con data, il pattern match nella definizione di <*> sarà divergere immediatamente se uno degli argomenti sono ⊥, ma con newtype costruttori vengono ignorati ed è proprio come se avessi scritto

che divergono solo per x = ⊥ se è richiesto x.

Answer 2

La differenza tra data e newtype è che data è "sollevato" e non lo è newtype. Ciò significa che lo data ha un extra ⊥ - in questo caso, significa che undefined/= Parser undefined. Se il tuo modello di codice corrisponde a Parser x, impone un valore ⊥ se il costruttore.

Quando si esegue lo schema su un costruttore data, viene valutato e smontato per assicurarsi che non sia ⊥. Per esempio:

λ> data Foo = Foo Int deriving Show 
λ> case undefined of Foo _ -> True 
*** Exception: Prelude.undefined 

Così pattern matching su un costruttore data è rigorosa, e lo spingono. Un newtype, d'altra parte, è rappresentato esattamente nello stesso modo del tipo con cui il costruttore esegue il wrapping. Così corrispondenza su un costruttore newtype non fa assolutamente nulla:

λ> newtype Foo = Foo Int deriving Show 
λ> case undefined of Foo _ -> True 
True 

Probabilmente ci sono due modi per cambiare il vostro programma data tale che non va in crash. Uno sarebbe utilizzare una corrispondenza di pattern irrefutabile nell'istanza Applicative, che avrà sempre "esito positivo" (ma l'utilizzo dei valori corrispondenti in qualsiasi momento successivo potrebbe non riuscire). Ogni partita newtype si comporta come un modello irrefutabile (dal momento che non c'è costruttore da abbinare, rigore-saggio).

λ> data Foo = Foo Int deriving Show 
λ> case undefined of ~(Foo _) -> True 
True 

L'altra sarebbe quella di utilizzare Parser undefined invece di undefined:

λ> case Foo undefined of Foo _ -> True 
True 

Questa partita avrà successo, perché non v'è un Foo valore valido che viene abbinato a. Capita di contenere undefined, ma questo non è rilevante dal momento che non lo usiamo - guardiamo solo il costruttore più in alto.

---

In aggiunta a tutti i link che hai dato, si potrebbe trovare this article rilevante.