where clauses in list comprehensions

Question

Qual è la differenza tra le seguenti due formule?

cp [] = [[]] 
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss] 
---------------------------------------------- 
cp [] = [[]] 
cp (xs:xss) = [x:ys | x <- xs, ys <- yss] 
       where yss = cp xss 

uscita Esempio: cp [[1,2,3],[4,5]] => [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]

Secondo Pensando funzionalmente Haskell (Pag. 92), la seconda versione è "una definizione più efficiente ... [che] garantisce che cp xss è calcolata solo una volta ", anche se l'autore non spiega mai perché. Avrei pensato che fossero equivalenti

Answer 1

Le due definizioni sono equivalenti nel senso che indicano lo stesso valore, ovviamente.

Operativamente differiscono nel comportamento di condivisione in base alla valutazione chiamata per necessità. jcast ha già spiegato perché, ma voglio aggiungere una scorciatoia che non richieda esplicitamente il desugaring della list comprehension. La regola è: qualsiasi espressione sintatticamente in una posizione in cui potrebbe dipendere da una variabile x verrà ricalcolata ogni volta che la variabile x è associata a un valore, anche se l'espressione non dipende effettivamente da x.

Nel tuo caso, nella prima definizione, x è portata nella posizione in cui compare cp xss, così cp xss saranno rivalutati per ogni elemento di xxs. Nella seconda definizione, cp xss viene visualizzato al di fuori dell'ambito di x, quindi verrà calcolato una sola volta.

quindi applicare le solite disclaimer, vale a dire:

• Il compilatore non è tenuto a rispettare la semantica operazionale di valutazione chiamata per necessità, solo la semantica denotazionale. Quindi potrebbe calcolare le cose meno volte (floating out) o più volte (floating in) di quanto ci si aspetterebbe in base alla regola precedente.

• In generale non è vero che una maggiore condivisione è migliore. In questo caso, ad esempio, probabilmente non è migliore perché la dimensione di cp xss cresce rapidamente quanto la quantità di lavoro necessaria per calcolarlo in primo luogo. In questa situazione, il costo di lettura del valore dalla memoria può superare quello del ricalcolo del valore (dovuto alla gerarchia della cache e al GC).

Answer 2

Beh, un ingenuo de-zuccheraggio sarebbe:

cp [] = [[]] 
cp (xs:xss) = concatMap (\x -> concatMap (\ ys -> [ x:ys ]) (cp xss)) xs 
---------------------------------------------- 
cp [] = [[]] 
cp (xs:xss) = let yss = cp xss in concatMap (\x -> concatMap (\ ys -> [ x:ys ]) yss) xs 

Come si può vedere, nella prima versione della chiamata cp xss è all'interno di una lambda. A meno che l'ottimizzatore non lo sposti, significa che verrà rivalutato ogni volta che viene chiamata la funzione \x -> concatMap (\ ys -> [ x:ys ]) (cp xss). Facendolo fluttuare, evitiamo il ricalcolo.

Allo stesso tempo, GHC dispone di un passaggio di ottimizzazione per eseguire costosi cicli di computazione su loop come questo, quindi può convertire automaticamente la prima versione al secondo. Il tuo libro dice che la seconda versione 'garantisce' di calcolare il valore di cp xss solo una volta perché, se l'espressione è dispendiosa da calcolare, i compilatori in genere sono molto riluttanti a incorporarlo (convertendo la seconda versione nel primo).