Io non capisco perché il seguente codice Haskell termina sotto GHCi:Perché questo filtro Haskell termina?
let thereExists f lst = (filter (==True) (map f lst)) /= []
thereExists (\x -> True) [1..]
non mi aspettavo la chiamata di filtrare a mai completa, dato che il suo secondo argomento è infinito, e non pensavo che il confronto potrebbe aver luogo fino a quando il lhs è stato calcolato completamente. Cosa sta succedendo?
Il confronto può ha luogo prima che il LHS sia calcolato completamente. Appena ha prodotto un elemento, /= è in grado di concludere che l'elenco non può essere uguale a [] e restituire immediatamente True.
/= sulle liste è implementato qualcosa di simile:
(/=) :: Eq a => [a] -> [a] -> Bool
[] /= [] = False
[] /= (y:ys) = True
(x:xs) /= [] = True
(x:xs) /= (y:ys) = (x /= y) || (xs /= ys)
Dal Haskell è pigro, valuteremo solo gli argomenti per quanto è necessario scegliere quale lato destro useremo. La valutazione del vostro esempio più o meno così:
filter (== True) (map (\x -> True) [1..]) /= []
==> (True : (filter (== True) (map (\x -> True) [2..]))) /= []
==> True
Appena sappiamo che il primo argomento di /= è (1 : something), che corrisponda alla terza equazione per /= nel codice di cui sopra, in modo che possa tornare True.
Tuttavia, se si prova thereExists (\x -> False) [1..], in effetti non si risolverà, perché in tal caso lo filter non compirà mai alcun progresso verso la produzione di un costruttore con cui si possa confrontare.
e così via all'infinito.
In conclusione, thereExists in un elenco infinito può restituire True in un tempo limitato, ma mai False.
Grazie. Puoi dirmi qualcosa su come questa magia è implementata?/= È incorporato in Haskell o può essere scritto in Haskell? –
@espertus Può essere scritto in Haskell - e lo è. È definito come 'xs/= ys = not (xs == ys)', e '(==)' è dato da '[] == [] = True; (x: xs) == (y: ys) = x == y && xs == ys; _ == _ = False'. –
@espertus È solo una valutazione non rigorosa. Non c'è niente di particolarmente speciale in questo caso. È proprio come Haskell funziona in generale. – Ben
A proposito, 'thereExists' si trova nella libreria standard, tranne che si chiama' any'. – hammar
Ho chiesto agli studenti di scrivere la propria versione di thereExists come una domanda di prova. Ho detto a uno studente che la sua versione (sopra) non è terminata, e mi ha detto che lo faceva. Aveva ragione, e ora capisco perché. –
Si noti inoltre che [1 ..] è * non * deve essere infinito. Con il tipo predefinito di [Intero] lo è, ma può anche essere [Int] che normalmente include elementi 2^31-1 o 2^63-1. – Tener