12 Stromen
Je kan het bestand met alle code voor streams hier downloaden. Om de code te kunnen gebruiken in een ander bestand, moet je het eerst inladen. Dit doe je door het volgende statement bovenaan je code te zetten:
(load "streams.rkt")
Let op! Je moet er wel voor zorgen dat het bestand met je code en het streams.rkt bestand in dezelfde directory opgeslagen zijn.
In dit bestand zijn de volgende procedures gedefinieerd: cons-stream, head, tail, empty-stream?, stream-accumulate, stream-accumulate-n, stream-map, stream-filter, stream-for-each, stream-append, enumerate-int, enumerate-tree, stream-print, take, pairs, stream-flatten, stream-interleave, stream-flatten/interleaved, stream-accumulate-delayed, stream-interleave-delayed en stream-values. Ook the-empty-stream is in dit bestand gedefinieerd.
Deze procedures mag je gebruiken in de volgende oefeningen. Indien je niet goed weet wat een bepaalde procedure doet, kijk dan zeker eens naar de slides, of gewoon naar de code. Sommige definities wijken ook af met die gezien tijdens de HOCs.
12.1 Reeksontwikkelingen
Maak gebruik van streams om de volgende reeksontwikkelingen tot op n termen te berekenen:
\[e = \frac{1}{0!} +\frac{1}{1!} +\frac{1}{2!} +\frac{1}{3!} + ...\]
> (exact->inexact (calc-e 10)) 2.7182818011463845
\[sin(x)=\frac{x}{1!} - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + ...\]
> (sinus (/ 3.1415 2) 10) 0.9999999989269138
12.2 Som kwadraten oneven elementen
Schrijf een procedure sum-odd-squares die de som van de kwadraten van de oneven elementen uit een stream berekent door gebruik te maken van stream-map, stream-filter en accumulate.
> (sum-odd-squares (stream-values 1 2 3 4 5 6)) 35
12.3 Triples
Schrijf een procedure (odd-sum-triples max) die een stream teruggeeft van alle lijsten van lengte 3 waarvan de eerste twee elementen oneven en kleiner dan max zijn en de som ervan gelijk is aan het derde element.
> (stream-print (odd-sum-triples 10)) [ (1 1 2) (3 1 4) (1 3 4) (5 1 6) (1 5 6) (3 3 6) (1 7 8) (7 1 8) (1 9 10) (3 5 8) (5 3 8) (3 7 10) (9 1 10) (3 9 12) (5 5 10) (7 3 10) (5 7 12) (9 3 12) (5 9 14) (7 5 12) (9 5 14) (7 7 14) (9 7 16) (7 9 16) (9 9 18) ]
ok
12.4 Delayed evaluation
Indien streams geïmplementeerd worden met "delayed evaluation" (d.m.v. delay en force), voorspel dan wat er op het scherm verschijnt als de volgende expressies in de opgegeven volgorde geëvalueerd worden.
(define (fac n) (display "->")(display n)(newline) (if (= n 0) 1 (* n (fac (- n 1)))))
(define ds (cons-stream (fac 3) (cons-stream (fac 2) (cons-stream (fac 1) the-empty-stream))))
(head ds)
(head (tail ds))
(tail ds)
(head (tail (tail ds)))
12.5 Oefening 3.51 uit Abelson&Sussman
Indien streams geïmplementeerd worden met "delayed evaluation", voorspel en verklaar het resultaat van de volgende expressies, waarbij show als volgt gedefinieerd is:
(define (show x) (display x)(newline) x)
(define x (stream-map show (enumerate-int 0 10)))
(head (tail x))
(head (tail x))
(define x (stream-map show (enumerate-int 0 10)))
(head (tail (tail (tail x))))
12.6 Integers
Vervolledig de volgende definitie van de integers stream: (define integers (cons-stream 1 (stream-map ??? integers)))
> (take integers 5) (1 2 3 4 5)
12.7 Streamfilter
Gebruik stream-filter om een stream van alle integers die niet deelbaar zijn door 2, 3 of 5 te bekomen. Definieer hiervoor een procedure (integers-special stream).
> (take (integers-special integers) 5) (1 7 11 13 17)
12.8 Triplets
Schrijf een procedure triplets die een (oneindige) stream genereert van triplets (lijsten met drie getallen) i, j, k die voldoen aan de eigenschap dat i + j > k (m.a.w. waarvan de som van de eerste twee elementen strikt groter is dan het derde element).
Hint: Maak gebruik van het feit dat k in het interval [1, i+j] ligt!
> (take (triplets) 4) ((1 1 1) (2 1 1) (1 1 2) (1 2 1))
12.9 Accumulate-n
Implementeer de procedure (stream-accumulate-n op ne streams) waarbij streams een stroom van stromen is, allen met dezelfde lengte. stream-accumulate-n zal op (met neutraal element ne) loslaten op de elementen van de eerste stroom uit streams, vervolgens op de elementen van de tweede stroom uit streams, enz. De resultaten worden in een nieuwe stroom teruggegeven.
(define (print-m matrix) (display "[") (stream-print (head matrix)) (newline) (stream-for-each (lambda (x) (display " ") (stream-print x) (newline)) (tail matrix)) (display "]\n")) (define matrix (cons-stream (enumerate-int 1 3) (cons-stream (enumerate-int 4 6) (cons-stream (enumerate-int 7 9) (cons-stream (enumerate-int 10 12) the-empty-stream)))))
> (print-m matrix)
[[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
[ 10 11 12 ]
]
> (stream-print (stream-accumulate-n + 0 matrix)) [ 22 26 30 ]
ok
12.10 Transpose
Veronderstel dat elke matrix wordt voorgesteld als een stream van streams (elke stream stelt een rij van de matrix voor). Implementeer dan de volgende operatie (transpose m) die een matrix n teruggeeft waarbij: n[i,j] = m[j,i].
Hiervoor kan je gebruik maken van stream-accumulate-n:
(define (stream-accumulate-n op ne streams) (if (empty-stream? (head streams)) the-empty-stream (let ((heads (stream-map head streams)) (tails (stream-map tail streams))) (cons-stream (stream-accumulate op ne heads) (stream-accumulate-n op ne tails)))))
(define (print-m matrix) (display "[") (stream-print (head matrix)) (newline) (stream-for-each (lambda (x) (display " ") (stream-print x) (newline)) (tail matrix)) (display "]\n")) (define matrix (cons-stream (enumerate-int 1 3) (cons-stream (enumerate-int 4 6) (cons-stream (enumerate-int 7 9) (cons-stream (enumerate-int 10 12) the-empty-stream)))))
> (print-m matrix)
[[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
[ 10 11 12 ]
]
> (print-m (transpose matrix))
[[ 1 4 7 10 ]
[ 2 5 8 11 ]
[ 3 6 9 12 ]
]
12.11 Examen Informatica eerste zit 1997
12.11.1 Cut
Schrijf een procedure (cut stream) die een stroom van getallen, gesorteerd in stijgende volgorde en waarin elk getal meerdere malen kan voorkomen, als invoer neemt en deze omvormt in een stroom van stromen, waarbij elke deelstroom bestaat uit alle voorkomens van 1 enkel getal. Zie figuur ter verduidelijking.
> (print-m (cut (stream-values 1 1 1 2 2 3 5 5 6 6 6)))
[[ 1 1 1 ]
[ 2 2 ]
[ 3 ]
[ 5 5 ]
[ 6 6 6 ]
]
12.11.2 Merge
Schrijf een procedure (merge str1 str2) die twee gesorteerde stromen als invoer neemt, en er een nieuwe gesorteerde stroom van maakt. Het merge-algoritme mag echter geen dubbels verwijderen!
> (stream-print (merge (stream-values 1 4 5 6 8 9) (stream-values 1 2 2 3 5 7 7 9))) [ 1 1 2 2 3 4 5 5 6 7 7 8 9 9 ]
ok
12.11.3 Merge-n
Maak nu gebruik van deze procedure merge om een procedure merge-n te definiëren die een eindige stroom van gesorteerde stromen als invoer neemt en deze sorteert door stapsgewijs de deelstroom te combineren met de procedure merge.
> (stream-print (merge-n (stream-values (stream-values 1 1 1 2 2 3 4 4 5 6 6 7) (stream-values 1 2 2 2 3 4 4 4 5 6 6 7) (stream-values 3 3 4 4 5 5 6 6 7)))) [ 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 6 6 6 6 6 6 7 7 7 ]
ok
12.11.4 Traffiek in een pretpark
In een pretpark zijn de ingangen afgezet met poortjes om slechts 1 persoon (per poortje) tegelijk door te laten. Veronderstel nu dat elk poortje, op het moment dat er persoon passeert, het huidige tijdstip (uur) op een stroom zet. Zo’n stroom ziet er dan bvb. als volgt uit (3 personen om 9 uur, 4 personen om 10 uur, 2 personen om 11 uur, enz.):
Om nu te weten te komen op welke uren het pretpark de meeste bezoekers ontvangt wensen we deze gegevens te analyseren. We plaatsen daartoe alle stromen van tijstippen (voor elk poortje 1 stroom) op 1 grote (maar eindige) stroom van stromen, en geven deze als input aan een procedure pretpark-traffiek. Deze procedure genereert een stroom van koppeltjes bestaande uit een tijdstip, en het totaal aantal bezoekers op dat tijdstip. Voorbeeld:
Maak gebruik van de procedures cut en merge-n om de procedure pretpark-traffiek te definiëren.
> (stream-print (pretpark-traffiek (stream-values (stream-values 1 1 1 2 2 3 4 4 5 6 6 7) (stream-values 1 2 2 2 3 4 4 4 5 6 6 7) (stream-values 3 3 4 4 5 5 6 6 7)))) [ (1 . 4) (2 . 5) (3 . 4) (4 . 7) (5 . 4) (6 . 6) (7 . 3) ]
ok
12.12 Examen januari 2008: Streams vraag
12.12.1 Prune
Schrijf een procedure prune die een eventueel oneindige stroom van elementen een een getal n als invoer neemt en als uitvoer een stroom produceert waarin afwisselend n elementen van de inputstroom doorgelaten of weggelaten worden. Op de resultaatstroom staan dus getallen 1 tot n, 2n+1 tot 3n, 4n+1 tot 5n, enz. uit de oorspronkelijke stroom.
> (stream-print (prune (stream-values 1 2 3 4 5 6 7 8 9) 2)) [ 1 2 5 6 9 ]
ok
12.12.2 Split
Schrijf een procedure split die een eventueel oneindige stroom van elementen en een getal n als invoer neemt en als uitvoer een stroom produceert van stromen van n lang. Op de resultaatstroom staan dus kleine eindige stroompjes van n elementen.
> (print-m (split (stream-values 1 2 3 4 5 6 7 8 9) 2))
[[ 1 2 ]
[ 3 4 ]
[ 5 6 ]
[ 7 8 ]
[ 9 ]
]
12.12.3 Daggemiddelden
Het weerstation in Ukkel zendt om het uur een temperatuur door (dag in dag uit) op een stroom. Op de temperaturenstroom staan dus afwisselend 12 dagtemperaturen en 12 nachttemperaturen. De stroom begint met 12 dagtemperaturen. Construeer een stroom (daggemiddelden) van gemiddelden tijdens de dag. Teken eerst een gedetailleerd schema van je oplossing.
> (define temperaturen (enumerate-int 1 48)) > (stream-print (daggemiddelden temperaturen)) [ 13/2 61/2 ]
ok
12.12.4 Nachtgemiddelden
Doe ditzelfde voor nachtgemiddelden.
> (define temperaturen (enumerate-int 1 48)) > (stream-print (nachtgemiddelden temperaturen)) [ 18.5 42.5 ]
ok
12.13 Extra Oefeningen
12.13.1 Stream met benaderingen van e
Ontwerp een oneindige stream e-stream van reële getallen die steeds een betere benadering van e teruggeeft:
> (take e-stream 7)
(1
2.0
2.5
2.6666666666666665
2.708333333333333
2.7166666666666663
2.7180555555555554)
12.13.2 Examen Informatica tweede zit 1999: Streams vraag
12.13.2.1 Raam
Schrijf een functie (raam data n) die als input een datastroom data neemt en hiervan een stroom van stromen maakt door elke n opeenvolgende data-elementen in een stroompje samen te nemen. Veronderstel dat de inputstroom oneindig is.
> (print-m (raam (stream-values 1 2 3 4 5 6 7 8 9 1 2 3 4 6 3) 2))
[[ 1 2 ]
[ 2 3 ]
[ 3 4 ]
[ 4 5 ]
[ 5 6 ]
[ 6 7 ]
[ 7 8 ]
[ 8 9 ]
[ 9 1 ]
[ 1 2 ]
[ 2 3 ]
[ 3 4 ]
[ 4 6 ]
[ 6 3 ]
[ 3 ]
]
> (print-m (raam (stream-values 1 2 3 4 5 6 7 8 9 1 2 3 4 6 3) 5))
[[ 1 2 3 4 5 ]
[ 2 3 4 5 6 ]
[ 3 4 5 6 7 ]
[ 4 5 6 7 8 ]
[ 5 6 7 8 9 ]
[ 6 7 8 9 1 ]
[ 7 8 9 1 2 ]
[ 8 9 1 2 3 ]
[ 9 1 2 3 4 ]
[ 1 2 3 4 6 ]
[ 2 3 4 6 3 ]
[ 3 4 6 3 ]
[ 4 6 3 ]
[ 6 3 ]
[ 3 ]
]
12.13.2.2 Test stroom
Schrijf een functie (test-n stream pred n) die een stroom stream van stromen als input neemt en voor elk van deze stromen nagaat of n van de elementen van deze stroom voldoen aan de voorwaarde pred. Een stroom van booleans wordt teruggegeven. Wanneer de stroom minder dan n elementen bevat wordt #f teruggegeven.
> (stream-print (test-n (stream-values (stream-values 1 1 1 1) (stream-values 1 2 1 1) (stream-values 3 5 7 9)) odd? 4)) [ #t #f #t ]
ok
> (stream-print (test-n (stream-values (stream-values 1 1 1 1) (stream-values 1 1 1 1 1) (stream-values 3 5 7 9)) odd? 4)) [ #t #t #t ]
ok
12.13.2.3 Extremen in neerslagmetingen
Volgens de definitie van het K.M.I. spreekt men van een droogte-periode als binnen een periode van 3 weken er 2- dagen minder dan 1 mm regen valt. Een periode wordt extreem nat genoemd als binnen een periode van 1 week er 4 dagen meer dan 10 mm regen valt. Schrijf m.b.v. streamoperatoren een functie (extreme data) die nagaat voor een gegeven stroom van neerslagmetingen of er doorgte of natte periodes in voorkomen. Teken een diagram voor je oplossing m.b.v. de gebruikte streamoperatoren.
12.13.3 Examen januari 2003: Streams vraag
12.13.3.1 Cut delimiter
Schrijf een procedure cut-delimiter die één (eventueel oneindige) stroom van elementen en een delimiter als invoer neemt en als uitvoer een stroom van kleine stromen produceert. De invoerstroom zal dus door deze procedure opgesplitst worden volgens de delimiter.
Voorbeeld:
> (define space #\space)
> (print-m (cut-delimiter (apply stream-values (string->list "hello world it is")) space))
[[ h e l l o ]
[ w o r l d ]
[ i t ]
[ i s ]
]
12.13.3.2 Filter tekstbestand
We kunnen nu deze procedure gaan gebruiken om vieze woorden uit een tekst te halen. Veronderstel dat we een tekstbestand hebben. Dit tekstbestand wordt in dit geval voorgesteld als een stroon van karakters. Verder hebben we ook nog een eindig bestand met vieze woorden die in deze tekst kunnen voorkomen. Schrijf nu een procedure (kuis-tekst stream-words stream-not-ok) die aan de hand van cut-delimiter en de gekende operaties op stromen alle vieze woorden die in de tekst voorkomen uit de tekst verwijdert en vervangt door een eindige stroom die het woordje "biep" bevat in de plaats van dit vies woord. Het eindresultaat is dus een stroom van stromen die de gekuiste tekst voorstelt.
Hint: schrijf (en gebruik) een procedure die de inhoud van twee stromen met elkaar vergelijkt.
Voorbeeld:
> (print-m (kuis-tekst (apply stream-values (string->list "hello world sex and drugs")) (cut-delimiter (apply stream-values (string->list "sex drugs")) space)))
[[ h e l l o ]
[ w o r l d ]
[ b i e p ]
[ a n d ]
[ b i e p ]
]
12.13.4 Examen januari 2004: Streams vraag
12.13.4.1 Gradient
Schrijf gradient die een stream van getallen als invoer neemt en als uitvoer een stream van getallen produceert. Deze geproduceerde stream van getallen bevar de absolute waarden van de verschillen van elke twee opeenvolgende getallen op de invoerstream (of gradiënt). Voorbeeld:
> (stream-print (gradient (stream-values 3 17 18 5 13 16 5 13 16 5 8 14 7))) [ 14 1 13 8 3 11 8 3 11 3 6 7 X ]
ok
12.13.4.2 Alarm
Schrijf alarm die een stream van getallen en een predikaat neemt als invoer. Hetgeen alarm doet, is een signaal geven als aan het predikaat voldaan is (door het woordje "alarm " en het overeenkomende getal af te drukken op het scherm). Voorbeeld:
> (alarm (stream-values 3 17 18 5 13 16 5 8 14 7) (lambda (n) (> n 10)))
alarm 17
alarm 18
alarm 13
alarm 16
alarm 14
done
12.13.4.3 Check
In een constant draaiende fabriek is een stuk software vereist dat controleert of het productieproces onder controle is. Schrijf check die een stream van temperatuursmetingen en een drempelwaarde binnenkrijgt. check gaat nakijken of het verschil tussen twee opeenvolgende temperatuursmetingen beneden de gegeven drempelwaarde blijft en zal een alarm geven indien dit niet het geval is. Voorbeeld:
> (check (stream-values 129 93 111 87 85 103 100 134 121) 20)
alarm 36
alarm 24
alarm 34
done
12.13.5 Examen januari 2010
De NMBS wil de tevredenheid van zijn treinreizigers in kaart brengen. Hiervoor hebben ze een systeem ontwikkeld waarbij treinreizigers dagelijks hun tevredenheid (een cijfer tussen 0 en 10) kunnen invullen. Deze dagelijkse tevredenheidscijfers kunnen worden voorgesteld als een oneindige stream van getallen met een # als scheidingsteken tussen de dagen (zie figuur voor een voorbeeldstream). Van deze tevredenheidsgetallen wil de NMBS per dag het minimum, maximum en gemiddelde weten.
12.13.5.1 Dagcijfers
Schrijf een procedure geef-dagcijfers die gegeven een oneindige stream van tevredenheidscijfers een oneindige stream van streams teruggeeft door de opeenvolgende dagcijfers same te nemen (de dagen worden gescheiden door een #).
> (print-m (geef-dagcijfers (stream-values 1 2 3 4 5 "#" 2 3 4 5 "#" 5 6 7)))
[[ 1 2 3 4 5 ]
[ 2 3 4 5 ]
[ 5 6 7 ]
]
12.13.5.2 Bereken resultaten
Schrijf voor de NMBS een procedure bereken-resultaten die gegeven een oneindige stream van tevredenheidscijfers een oneindige stream van streams teruggeeft. Deze resultaat-stream zal per dag een stream bevatten met 3 elementen (het minimum, maximum en gemiddelde).
Deze operatoren staan alvast tot je beschikking: stream-filter, stream-map, accumulate, append-stream, stream-flatten, stream-accumulate-n, cons-stream.
> (print-m (bereken-resultaten (stream-values 1 2 3 4 5 "#" 2 3 4 5 "#" 5 6 7)))
[[ 1 5 3 ]
[ 2 5 7/2 ]
[ 5 7 6 ]
]