Vraag Luie evaluatie van termen op een oneindige lijst in Haskell


Ik ben benieuwd naar de runtime-prestaties van een oneindige lijst zoals die hieronder:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Hiermee wordt een oneindige lijst van de fibonacci-reeks gemaakt.

Mijn vraag is dat als ik het volgende doe:

takeWhile (<5) fibs

hoe vaak doet fibs elke term in de lijst evalueren? Het lijkt dat sindsdien takeWhile controleert de predikaatfunctie voor elk item in de lijst, de fibs lijst zal elke term meerdere keren evalueren. De eerste 2 voorwaarden worden gratis gegeven. Wanneer takeWhile wil evalueren (<5) op het derde element krijgen we:

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3

Nu, een keer takeWhile wil evalueren (<5) op het 4de element: het recursieve aard van fibs zal de lijst opnieuw opbouwen zoals de als vervolg op:

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

Het lijkt erop dat het derde element opnieuw moet worden berekend wanneer we wil de waarde van het 4e element evalueren. Verder, als het predicaat in takeWhile is groot, het zou aangeven dat de functie is meer werk doen dat nodig is omdat het elk voorgaande evalueert element in de lijst meerdere keren. Is mijn analyse hier correct of is dat zo Haskell doet wat caching om meerdere evaluaties hier te voorkomen?


41
2018-06-10 21:15


oorsprong


antwoorden:


Dit is een zelfreferentiële, luie gegevensstructuur, waarbij 'latere' delen van de structuur eerdere delen bij naam noemen.

Aanvankelijk is de structuur slechts een berekening met ongeëvalueerde wijzers terug naar zichzelf. Terwijl het wordt geopend, worden er waarden in de structuur gemaakt. Latere verwijzingen naar reeds-berekende delen van de structuur zijn in staat om de waarde te vinden die daar al op hen wacht. Het is niet nodig om de stukken opnieuw te evalueren en er is geen extra werk te doen!

De structuur in het geheugen begint als slechts een ongeëvalueerde aanwijzer. Zodra we naar de eerste waarde kijken, ziet het er als volgt uit:

> take 2 fibs

enter image description here

(een wijzer naar een cons-cel, wijzend naar '1', en een staart met de tweede '1', en een wijzer naar een functie die referenties terughoudt naar leugens, en de staart van leugens.

Als u nog een stap verder evalueert, wordt de structuur uitgebreid en worden de referenties verschoven:

enter image description here

En dus gaan we de structuur ontvouwen, telkens met een nieuwe ongeëvalueerde staart, wat een sluiting is met referenties terug naar het eerste en tweede element van de laatste stap. Dit proces kan oneindig doorgaan :)

En omdat we eerdere waarden met naam noemen, bewaart GHC ze graag in het geheugen voor ons, dus elk item wordt maar één keer geëvalueerd.


80
2018-06-10 22:26



Illustratie:

module TraceFibs where

import Debug.Trace

fibs :: [Integer]
fibs = 0 : 1 : zipWith tadd fibs (tail fibs)
  where
    tadd x y = let s = x+y
               in trace ("Adding " ++ show x ++ " and " ++ show y
                                   ++ "to obtain " ++ show s)
                        s

Welke produceert

*TraceFibs> fibs !! 5
Adding 0 and 1 to obtain 1
Adding 1 and 1 to obtain 2
Adding 1 and 2 to obtain 3
Adding 2 and 3 to obtain 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Adding 3 and 5 to obtain 8
8
*TraceFibs> fibs !! 16
Adding 5 and 8 to obtain 13
Adding 8 and 13 to obtain 21
Adding 13 and 21 to obtain 34
Adding 21 and 34 to obtain 55
Adding 34 and 55 to obtain 89
Adding 55 and 89 to obtain 144
Adding 89 and 144 to obtain 233
Adding 144 and 233 to obtain 377
Adding 233 and 377 to obtain 610
Adding 377 and 610 to obtain 987
987
*TraceFibs>

31
2018-06-10 21:31



Wanneer iets in Haskell wordt geëvalueerd, blijft het geëvalueerd, zolang er naar wordt verwezen met dezelfde naam1.

In de volgende code, de lijst l wordt slechts eenmaal geëvalueerd (wat voor de hand ligt):

let l = [1..10]
print l
print l -- None of the elements of the list are recomputed

Zelfs als iets gedeeltelijk wordt geëvalueerd, blijft dat deel geëvalueerd:

let l = [1..10]
print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _]
print l          -- 1 to 5 is already evaluated; only evaluates 6..10

In uw voorbeeld, wanneer een element van de fibs lijst wordt geëvalueerd, het blijft geëvalueerd. Sinds de argumenten om zipWith referentie van de werkelijke fibs lijst betekent dit dat de zipping uitdrukking de al gedeeltelijk berekende zal gebruiken fibs lijst bij het berekenen van de volgende elementen in de lijst. Dit betekent dat geen enkel element twee keer wordt geëvalueerd.

1Dit is natuurlijk niet strikt vereist door de taalsemantiek, maar in de praktijk is dit altijd het geval.


19
2018-06-10 22:39



Zie het op deze manier. De variabele fib is een aanwijzing voor een luie waarde. (Je kunt hieronder een luie waarde zien als een gegevensstructuur zoals (geen echte syntaxis) Lazy a = IORef (Unevaluated (IO a) | Evaluated a); d.w.z. het begint als ongeëvalueerd met een thunk; vervolgens wordt het geëvalueerd wanneer het wordt "gewijzigd" in iets dat de waarde onthoudt.) Omdat de recursieve uitdrukking de variabele gebruikt fib, ze hebben een aanwijzer naar dezelfde luie waarde (ze "delen" de gegevensstructuur). De eerste keer dat iemand evalueert fib, het loopt de dunk om de waarde te krijgen en die waarde wordt onthouden. En omdat de recursieve uitdrukking verwijst naar de dezelfde luie gegevensstructuur, wanneer ze deze evalueren, zullen ze de geëvalueerde waarde al zien. Terwijl ze de luie "oneindige lijst" doorlopen, zal er slechts één "gedeeltelijke lijst" in het geheugen zijn; zipWith zal twee verwijzingen naar "lijsten" hebben die eenvoudigweg verwijzingen zijn naar eerdere leden van dezelfde "lijst", vanwege het feit dat het begon met verwijzingen naar dezelfde lijst.

Merk op dat dit niet echt "memoizing" is; het is gewoon een gevolg van het verwijzen naar dezelfde variabele. Er is over het algemeen geen "memoizing" van de resultaten van de functie (het volgende zal inefficiënt zijn):

fibs () = 0 : 1 : zipWith tadd (fibs ()) (tail (fibs ()))

4