Perché la comprensione delle liste "multi-infinite" non funziona con la valutazione lazy?

È certamente possibile definire un ordine di iterazione per x1 <- [1..], x2 <- [1..], ..., xK <- [1..] che raggiunga qualsiasi tupla (c1, c2, ..., cK) dopo una certa quantità di passaggi e prova ogni tupla una sola volta. Prendi una qualsiasi bijection computabile tra i numeri naturali N e le k-tuple dei numeri naturali, N ^ k. Esiste una tale bijection, in quanto il prodotto cartesiano di insiemi numerabili è nuovamente numerabile. Un esempio potrebbe applicare ripetutamente la funzione Cantor . La bijection precisa utilizzata dovrebbe essere specificata dal report Haskell, perché influisce sull'ordine in cui vengono trovati i risultati.

Tuttavia, questo è di utilità limitata, perché coprirebbe solo il modello molto specifico con [1..] . Ci sono innumerevoli altri modi per produrre liste infinte, e non solo è molto più coinvolto nella definizione di un ordine di iterazione adatto per quei casi, ma è anche impossibile per il compilatore di rilevare liste infinite in tutti i casi ( Teorema di Rice). Quindi dovresti definire un certo euristico per quando si applica questa trasformazione. Nell'interesse di essere fattibile per descrivere e implementare tra più interpreti e compilatori, questa sarebbe probabilmente un'euristica molto semplicistica.

Quindi quello che ti rimane è un sottile cambiamento nella semantica di un programma, senza alcuna indicazione nel codice sorgente del programma, che accade solo quando alcuni incendi euristici arcani e limitati. Grazie, passerò. Scrivi in modo esplicito il programma per fare ciò che vuoi.

Una risposta breve: devi solo usare una monade diversa ( omega ), per gli elenchi questo è funzionante come previsto .

Per elaborare: per le list comprehensions, vuoi avere i risultati in un ordine specifico. E mentre per il tuo caso d'uso vuoi un ordine diverso, per gli altri questo ordine è ciò di cui hanno bisogno e vogliono.

Il problema è che se si esegue la diagonalizzazione, come fa l'omega monad, è piuttosto difficile decidere come eseguirne la sequenza. Considera che:

• Gli elenchi potrebbero contenere sequenze complesse, come le potenze di due. In che modo darai la priorità alle sequenze aritmetiche e geometriche?
• Gli elenchi potrebbero contenere valori di qualsiasi tipo, che potrebbero anche non essere ordinati.

Considerato quanto sopra, anche se hai la garanzia che alla fine troverai tutte le combinazioni in un tempo finito, in pratica questo vorrà dire che uno in particolare potrebbe richiedere molto a lungo per trovarlo.

Con le funzioni omega e monad puoi facilmente esprimere il tuo problema come

test :: [(Integer, Integer, Integer)]
test = take 100 $ runOmega [(a, b, c) | a <- each [1..]
                                      , b <- each [1..]
                                      , c <- each [1..]
                                      , a^2 == b^2 + c^2]

Tuttavia vedrai che anche se alla fine trova tutti i tripli, non troverà i "bravi" in un tempo ragionevole.

Per un caso d'uso reale, suggerirei di usare LogicT monad. Esiste un controllo esplicito sulla diagonalizzazione utilizzando interleave e >>- .

Beh, la risposta più semplice e pratica, che richiede esperienza per apprezzare, è che questa situazione è al massimo un fastidio minore. Una risposta più elaborata, che richiede ancora più esperienza per apprezzare, comprende le prime due osservazioni e una conclusione.

Prima osservazione: la comunità di Haskell vede le comprensioni delle liste come un'applicazione concreta delle monadi. Le funzionalità offerte dalla comprensione delle liste coincidono con quelle fornite da MonadPlus istanza per le liste e GHC ha un'estensione MonadComprehensions che ti consente di utilizzare la sintassi di comprensione con qualsiasi monade.

Seconda osservazione: esiste una tecnica classica per interlacciare liste infinite, dovuta alla famosa matematica la prova di Georg Cantor che il set di numeri naturali ha la stessa cardinalità ("dimensione") dell'insieme di numeri razionali . Questo può essere facilmente tradotto in Haskell:

{-# LANGUAGE DeriveFunctor, TupleSections #-}

import Control.Applicative

cantor :: [a] -> [b] -> [(a, b)]
cantor [] _ = []
cantor _ [] = []
cantor (a:as) (b:bs) =
    (a,b) : interleave (map (a,) bs) (interleave (map (,b) as) (cantor as bs))

interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

E potremmo provare a definire un'istanza alternativa Monad basata su quello. Per prima cosa definiamo un tipo di wrapper Cantor :

newtype Cantor a = Cantor [a]
    deriving (Eq, Functor)

Monad è una sottoclasse di Applicative , quindi per prima cosa definiamo un'istanza Applicative per Cantor :

instance Applicative Cantor where
    pure a = Cantor [a]
    Cantor fs <*> Cantor as = Cantor (map (uncurry ($)) (cantor fs as))

... ma qui abbiamo già sbagliato, perché risulta che questo viola le leggi ("contratto", in termini OO) della classe Applicative . In Applicative , il seguente test unitario deve essere eseguito indipendentemente da quali valori vengono passati come argomenti:

-- | One of the consequences of the associative law for 'Applicative'.
-- This function must return true no matter what arguments are passed
-- in.  Haskell's QuickCheck unit testing library runs tests in this
-- format, and this one will fail if we run it on 'Cantor'.
associativity
    :: (Applicative f, Eq (f (a, (b, c)))) => f a -> f b -> f c -> Bool
associativity as bs cs = 
    as 'pair' (bs 'pair' cs) == fmap assoc ((as 'pair' bs) 'pair' cs)

pair :: Applicative f => f a -> f b -> f (a, b)
pair = liftA2 (,)

assoc :: ((a, b), c) -> (a, (b, c))
assoc ((a, b), c) = (a, (b, c))

Che questo test fallisca può essere verificato molto facilmente semplicemente eseguendo alcuni semplici esempi. Tieni presente che pair nel tipo Cantor è uguale alla funzione cantor come sopra, quindi possiamo semplificare questo test a questo:

associativity' :: (Eq a, Eq b, Eq c) => [a] -> [b] -> [c] -> Bool
associativity' as bs cs =
    as 'cantor' (bs 'cantor' cs) == map assoc ((as 'cantor' bs) 'cantor' cs)

Quindi Cantor non è un Applicative rispettoso della legge. Ne consegue che non può nemmeno essere un Monad rispettoso della legge.

Ora la conclusione è la seguente: queste due osservazioni, messe insieme, sono una risposta alla tua domanda. Rendere le list comprehensions usare cantor o qualche tecnica simile per lavorare nelle liste infinite significherebbe abbandonare l'idea che le list comprehensions siano un'applicazione delle monadi. Ma Haskellers pensa che le monadi siano una tecnica troppo preziosa da trascurare per un caso d'angolo come questo.