Perché Hasrock foldr non stackoverflow mentre la stessa implementazione Scala fa?

Question

Sto leggendo FP in Scala.

L'esercizio 3.10 dice che foldRight trabocca (vedere le immagini sotto). Per quanto ne so, tuttavia lo foldr in Haskell non lo fa.

http://www.haskell.org/haskellwiki/

-- if the list is empty, the result is the initial value z; else 
-- apply f to the first element and the result of folding the rest 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else 
-- we recurse immediately, making the new initial value the result 
-- of combining the old initial value with the first element. 
foldl f z []  = z     
foldl f z (x:xs) = foldl f (f z x) xs 

Come è questo comportamento diverso possibile?

Qual è la differenza tra i due linguaggi/compilatori che causano questo comportamento diverso?

Da dove viene questa differenza? La piattaforma ? La lingua? Il compilatore?

È possibile scrivere un foldRight sicuro in stack in Scala? Se sì, come?

Answer 1

Haskell è pigro. La definizione

foldr f z (x:xs) = f x (foldr f z xs) 

ci dice che il comportamento di foldr f z xs con una lista non vuota xs è determinata dal pigrizia della funzione combinare f.

In particolare chiamata foldr f z (x:xs) alloca un solo thunk sul mucchio, {foldr f z xs} (crei {...} per un thunk possesso un'espressione ...) e chiede f con due argomenti - x e il thunk. Quello che succede dopo è la responsabilità di f.

In particolare, se si tratta di un costruttore di dati artificiale (come ad esempio (:)), esso sarà immediatamente restituito al chiamante della foldr chiamata (con due slot del costruttore riempiti da (riferimenti a) i due valori).

E se f fa chiedere il suo valore sulla destra, con le ottimizzazioni del compilatore minimi non thunk devono essere create a tutti (o uno, al massimo - quello attuale), in quanto è immediatamente necessario il valore della foldr f z xs e il solito stack-based di valutazione può usato:

foldr f z [a,b,c,....,n] == 
    a `f` (b `f` (c `f` (... (n `f` z)...))) 

Così foldr può infatti causare SO, quando viene utilizzato con la funzione che combina rigorosi sulle liste di ingresso estremamente lunghi.Ma se la funzione di combinazione non richiede subito il suo valore sulla destra, o richiede solo una parte di essa, la valutazione verrà sospesa in un thunk e il risultato parziale come creato da f verrà immediatamente restituito. Lo stesso vale per l'argomento a sinistra, ma sono già presenti come thunk, potenzialmente, nella lista di input.

Answer 2

Haskell è pigro. Quindi foldr alloca sull'heap, non sullo stack. A seconda della severità della funzione argomento, può allocare un singolo risultato (piccolo) o una struttura grande.

Stai ancora perdendo spazio, rispetto a un'implementazione rigida, ricorsiva alla coda, ma non sembra ovvio, dal momento che hai scambiato lo stack per l'heap.

Answer 3

Si noti che gli autori qui non si riferiscono a nessuna definizione di foldRight nella libreria standard di scala, come quella definita in Elenco. Si riferiscono alla definizione di foldRight che hanno fornito nella sezione 3.4.

La libreria standard scala definisce foldRight in termini di foldLeft invertendo l'elenco (che può essere eseguito nello spazio di stack costante) quindi chiamando foldLeft con gli argomenti della funzione passata invertiti. Questo funziona per gli elenchi, ma non funziona per una struttura che non può essere invertito in modo sicuro, per esempio:

scala> Stream.continually(false) 
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?) 

scala> res0.reverse 
java.lang.OutOfMemoryError: GC overhead limit exceeded 

Ora lascia pensare a ciò che dovrebbe essere il risultato di questa operazione:

Stream.continually(false).foldRight(true)(_ && _) 

La risposta dovrebbe essere falsa, non importa quanti falsi valori sono nel flusso o se è infinita, se li combineremo con una congiunzione, il risultato sarà falso.

Haskell ovviamente ottiene questo senza alcun problema:

Prelude> foldr (&&) True (repeat False) 
False 

E questo è a causa di due cose importanti: foldr Haskell attraverserà il flusso da sinistra a destra, non da destra a sinistra, e Haskell è pigro da predefinito. Il primo elemento qui, che foldr attraversa effettivamente la lista da sinistra a destra potrebbe sorprendere o confondere alcune persone che pensano a una piega giusta come partendo da destra, ma l'importante caratteristica di una piega a destra non è quale parte finale di una struttura inizia su, ma in quale direzione è l'associatività. Quindi dare una lista [1,2,3,4] e un op nome op, una piega a sinistra è

((1 op 2) op 3) op 4) 

e un diritto fold è

(1 op (2 op (3 op 4))) 

Ma l'ordine di valutazione non dovrebbe importa. Quindi, ciò che gli autori hanno fatto qui nel capitolo 3 è di darti una piega che attraversa la lista da sinistra a destra, ma poiché scala è di default severa, non saremo ancora in grado di attraversare il nostro flusso di falsi infiniti, ma alcuni pazienza, ci arriveremo nel capitolo 5 :) Vi darò un'anteprima, guardiamo alla differenza tra foldRight così come è definita nella libreria standard e come è definita nella classe di caratteri Pieghevole in scala:

Ecco l'implementazione della libreria standard Scala:

def foldRight[B](z: B)(op: (A, B) => B): B 

Ecco la definizione da scalaz di pieghevole:

def foldRight[B](z: => B)(f: (A, => B) => B): B 

La differenza è che le B sono tutti pigri, e ora otteniamo piegare nuovamente nostro flusso infinito, purché diamo una funzione che è sufficientemente pigro nel suo secondo parametro:

scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _) 
res0: Boolean = false 

Answer 4

One facile Il modo per dimostrarlo in Haskell è utilizzare il ragionamento equo per dimostrare una valutazione lenta.Scriviamo la funzione find in termini di foldr:

-- Return the first element of the list that satisfies the predicate, or `Nothing`. 
find :: (a -> Bool) -> [a] -> Maybe a 
find p = foldr (step p) Nothing 
    where step pred x next = if pred x then Just x else next 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

In un linguaggio ansioso, se hai scritto find con foldr sarebbe attraversare la lista e l'uso intero O (n) spazio. Con valutazione pigra, si ferma al primo elemento che soddisfa il predicato, e utilizza solo O (1) spazio (modulo garbage collection):

find odd [0..] 
    == foldr (step odd) Nothing [0..] 
    == step odd 0 (foldr (step odd) Nothing [1..]) 
    == if odd 0 then Just 0 else (foldr (step odd) Nothing [1..]) 
    == if False then Just 0 else (foldr (step odd) Nothing [1..]) 
    == foldr (step odd) Nothing [1..] 
    == step odd 1 (foldr (step odd) Nothing [2..]) 
    == if odd 1 then Just 1 else (foldr (step odd) Nothing [2..]) 
    == if True then Just 1 else (foldr (step odd) Nothing [2..]) 
    == Just 1 

Questa valutazione ferma in un numero finito di passi, nonostante la Infatti l'elenco [0..] è infinito, quindi sappiamo che non stiamo attraversando l'intera lista. Inoltre, vi è un limite superiore alla complessità delle espressioni ad ogni passo, che si traduce in un limite superiore costante sulla memoria richiesta per valutare questo.

La chiave qui è che la funzione step che stiamo pieghevole con ha questa proprietà: non importa ciò che i valori di x e next sono, sarà o:

1. Valutare per Just x, senza invocare il next thunk o
2. Coda chiamata next thunk (in effetti, se non letteralmente).