5 Lijsten en symbolische data

5.1 Box-and-pointer representatie

5.2 Voorspel

Deze oefening is gebaseerd op oefening 2.53 van Structure and Interpretation of Computer Programs

De atom? procedure is als volgt gedefinieerd:

(define (atom? x)   (not (pair? x)))

5.3 Lijsten met procedures en symbolen

5.4 Recursie/iteratie op lijsten: modeloplossing

Het volgende stukje "code" beschrijft een standaardpatroon voor recursieve procedures op lijsten. De meeste recursieve procedures op lijsten kunnen geschreven worden volgens dit patroon, of volgens een zeer gelijkaardig patroon.

(define (list-procedure-rec lst)

(if (null? lst)

base-result

(combine-car/res (do-something-with (car lst))

(list-procedure-rec (cdr lst)))))

(define (list-procedure-it lst)

(define (iter lst res)

(if (null? lst)

res

(iter (cdr lst)

(combine-car/res (do-something-with (car lst))

res))))

(iter lst base-result))

5.5 Element toevoegen achteraan een lijst: add-to-end

Defineer (zonder gebruik te maken van append) een procedure (add-to-end e l) die een nieuwe lijst teruggeeft met dezelfde elementen als de lijst l maar met het object e aan het einde toegevoegd.

> (add-to-end 999 '(1 2 3 4 5))

(1 2 3 4 5 999)

> (add-to-end 999 '())

(999)

> (add-to-end 999 '(1))

(1 999)

5.6 Lijsten aaneen plakken: my-append (iteratief)

Schrijf de procedure my-append op iteratieve wijze. Doe dit zo efficiënt mogelijk.

> (my-append '(1 2 3) '(4 5))
(1 2 3 4 5)
> (my-append '(1 2 3) '())
(1 2 3)
> (my-append '() '(1 2 3))
(1 2 3)
> (my-append '() '())
()

5.7 Lijsten omdraaien: my-reverse (Recursief & Iteratief)

Deze oefening is gebaseerd op oefening 2.17 van Structure and Interpretation of Computer Programs

Schrijf de procedure (rec-reverse l) die een lijst teruggeeft met dezelfde elementen als l maar in de omgekeerde volgorde.

Maak 2 versies: één die een recursief proces en één die een iteratief proces genereert. Noem de recursieve versie (rec-reverse l) en de iteratieve versie (iter-reverse l).

> (rec-reverse '(1 2 3))

(3 2 1)

> (rec-reverse '(1))

(1)

> (rec-reverse '())

()

> (iter-reverse '(1 2 3))

(3 2 1)

> (iter-reverse '(1))

(1)

> (iter-reverse '())

()

5.8 Laatste element van een lijst bepalen: last

Deze oefening is gebaseerd op oefening 2.16 van Structure and Interpretation of Computer Programs

Schrijf een procedure last die het laatste element van een lijst teruggeeft.

> (last '(1 2 3))

3

> (last '(1))

1

> (last '())

#f

5.9 Elementen in een lijstvervangen: replace

Schrijf de functie (replace e1 e2 l) die een lijst teruggeeft, gelijk aan lijst l, maar waarin alle elementen gelijk aan e1 vervangen zijn door e2. Gebruik (eq? e1 e2) om twee elementen te vergelijken. De procedure mag een recursief proces genereren.

> (replace 1 999 '(1 2 1 3 1 4 1 5 1))
(999 2 999 3 999 4 999 5 999)
> (replace 1 999 '(2 3 4 5 6 7))
(2 3 4 5 6 7)
> (replace 1 999 '(1))
(999)
> (replace 1 999 '())
()

5.10 Gelijkheid van twee lijsten bepalen: my-equal?

Deze oefening is gebaseerd op oefening 2.54 van Structure and Interpretation of Computer Programs

Schrijf de procedure (my-equal? l1 l2) die nagaat of twee lijsten van symbolen l1 en l2 gelijk zijn. Gebruik (eq? e1 e2) om twee elementen te vergelijken.

> (my-equal? '(1 2 3) '(1 2 3))

#t

> (my-equal? '(1 2 3) '(4 5 6))

#f

> (my-equal? '(1 2 3) '(1 2))

#f

> (my-equal? '(1 2 3) '())

#f

> (my-equal? '() '(1 2 3))

#f

5.11 Element tussenvoegen in een lijst: intersperse

Definieer een procedure (intersperse e l) die een nieuwe lijst teruggeeft met dezelfde elementen als de lijst l, maar met het object e tussengevoegd tussen elk van de originele elementen.

> (intersperse 1 '(3 4 5))

(3 1 4 1 5)

> (intersperse 1 '(9))

(9)

> (intersperse 1 '())

()

5.12 Sommatie van elementen in lijsten: sum-lists

De procedure (sum-lists l1 l2) heeft als argumenten 2 lijsten met getallen, en geeft een lijst terug met de sommen van de overeenkomstige elementen van de input-lijsten.

Merk op dat de twee input-lijsten niet dezelfde lengte hoeven te hebben. In dat geval worden de resterende elementen van de langste lijst gewoon overgenomen.

5.12.1 Recursieve versie

Schrijf een recursieve versie, noem het (rec-sum-lists l1 l2).

> (rec-sum-lists '(1 2 3 4) '(5 6 7))

(6 8 10 4)

> (rec-sum-lists '(1 2 3 4) '())

(1 2 3 4)

> (rec-sum-lists '() '(1 2 3))

(1 2 3)

5.12.2 Iteratieve versie

Schrijf een iteratieve versie, noem het (iter-sum-lists l1 l2).

> (iter-sum-lists '(1 2 3 4) '(5 6 7))

(6 8 10 4)

> (iter-sum-lists '(1 2 3 4) '())

(1 2 3 4)

> (iter-sum-lists '() '(1 2 3))

(1 2 3)

5.13 Lijsten samenvoegen

5.13.1 Samenvoegen van twee lijsten: merge-n

Schrijf een procedure die 2 lijsten samenvoegt tot 1 enkele lijst door telkens n elementen van de eerste lijst te laten volgen door n elementen van de tweede lijst, enzovoort. Indien er minder dan n elementen overblijven in een lijst, neem je alles wat er overblijft. Doe dit zowel op recursieve als iteratieve wijze. Noem de recursieve versie (rec-merge-n lst1 lst2 n). Noem de iteratieve versie (iter-merge-n lst1 lst2 n).

> (rec-merge-n '(1 2 3 4 5) '(6 7 8 9) 2)

(1 2 6 7 3 4 8 9 5)

> (rec-merge-n '(1 2 3 4 5) '(6 7 8 9) 3)

(1 2 3 6 7 8 4 5 9)

> (rec-merge-n '(1 2) '(3 4 5 6) 4)

(1 2 3 4 5 6)

> (iter-merge-n '(1 2 3 4 5) '(6 7 8 9) 2)

(1 2 6 7 3 4 8 9 5)

> (iter-merge-n '(1 2 3 4 5) '(6 7 8 9) 3)

(1 2 3 6 7 8 4 5 9)

> (iter-merge-n '(1 2) '(3 4 5 6) 4)

(1 2 3 4 5 6)

5.13.2 Samenvoegen van een willekeurig aantal lijsten: super-merge-n

Veralgemeen de procedure uit Samenvoegen van twee lijsten: merge-n tot een procedure (super-merge-n lsts n) die een willekeurig aantal lijsten samenvoegt door achtereenvolgens n elementen van elke lijst te nemen. De lijsten zitten samen in de formele parameter lsts.

> (super-merge-n '((a b c d e f)                    (g h i j k)                    (l m n o p q)                    (r s t u v w))                  3)

(a b c g h i l m n r s t d e f j k o p q u v w)

5.14 Extra Oefeningen

5.14.1 Pairs als procedures

Deze oefening is gebaseerd op oefening 2.4 van Structure and Interpretation of Computer Programs

Het is mogelijk om pairs, net zoals getallen en andere vormen van data, voor te stellen als procedures:

(define (my-cons x y)  (lambda (m) (m x y)))   (define (my-car z)   (z (lambda (p q) p)))

> (my-car (my-cons 1 2)) 1

5.14.1.1 Definitie van my-cdr

Vervolledig de definities van hierboven door my-cdr te implementeren.

5.14.2 replace d.m.v. map

Implementeer de procedure replace-dmv-map, door middel van de ingebouwde procedure map.

> (replace-dmv-map 1 999 '(1 2 1 3 1 4 1 5 1))
(999 2 999 3 999 4 999 5 999)
> (replace-dmv-map 1 999 '(2 3 4 5 6 7))
(2 3 4 5 6 7)
> (replace-dmv-map 1 999 '(1))
(999)
> (replace-dmv-map 1 999 '())
()

5.14.3 Combine over list

> (som-van-de-kwadraten '(1 2 3))

14

> (uitsluitend-oneven? '(2 3))

#f

> (uitsluitend-oneven? '(1 3))

#t

5.14.4 Examen Informatica eerste zit 1999

5.14.4.1 Dissectie van een lijst

Schrijf een procedure die een lijst dissecteert in een nieuwe lijst door afwisselend n elementen dan weer wel en dan weer niet te behouden. Indien er minder dan n elementen overblijven in de lijst, neem je alles wat er overblijft. Doe dit zowel op recursieve als iteratieve wijze. Noem de recursieve versie (rec-dissect-n lst n). Noem de iteratieve versie (iter-dissect-n lst n).

> (rec-dissect-n '(1 2 3 4 5) 2)

(1 2 5)

> (rec-dissect-n '(1 2 3 4 5 6 7 8) 3)

(1 2 3 7 8)

> (rec-dissect-n '(1 2) 4)

(1 2)

> (iter-dissect-n '(1 2 3 4 5) 2)

(1 2 5)

5.14.4.2 Splitsen van een lijst

Schrijf een procedure (split lst n) die niet alleen de gedissecteerde lijst uit Dissectie van een lijst teruggeeft, maar ook een lijst die opgebouwd is uit de resten van de oorspronkelijke lijst.

> (split '(1 2 3 4 5 6 7 8 9 10) 2)

((1 2 5 6 9 10) (3 4 7 8))

5.14.4.3 Splitsen van meerdere lijsten

Veralgemeen de procedure uit Splitsen van een lijst tot een procedure (super-split lsts n) die een willekeurig aantal lijsten split. De lijsten zitten samen in de formele paramater lsts. Als resultaat worden twee lijsten van lijsten teruggegeven. De eerste lijst bestaat uit alle gedissecteerde lijsten uit Dissectie van een lijst, de tweede lijst bevat de restjes.

> (super-split '((a b c d e f) (g h i j k) (l m n o p q) (r s t u v w)) 3)

(((a b c) (g h i) (l m n) (r s t)) ((d e f) (j k) (o p q) (u v w)))

5.14.5 Examen Informatica Partieel januari 1994

5.14.5.1 Kopie van een lijst, zonder elementen in een interval

Schrijf een lineair recursieve procedure all-but-interval die een kopie neemt van een geordende lijst getallen, uitgezonderd die getallen binnen een bepaald interval. Je mag ervan uitgaan dat elk getal in de lijst strikt groter is dan zijn voorganger (er komen geen dubbels voor in de lijst). Er worden twee parameters doorgegeven om het interval aan te duiden, en de eerste is kleiner of gelijk aan de tweede.

> (all-but-interval '(1 2 3 4 5) 2 4)

(1 5)

> (all-but-interval '(1 2 3 4 5) 0 7)

()

> (all-but-interval '(1 2 3 4 5) 1 1)

(2 3 4 5)

5.14.5.2 Iteratieve versie

Schrijf een iteratieve versie van dezelfde procedure. Noem het (iter-all-but-interval l start stop).

> (iter-all-but-interval '(1 2 3 4 5) 2 4)

(1 5)

> (iter-all-but-interval '(1 2 3 4 5) 0 7)

()

> (iter-all-but-interval '(1 2 3 4 5) 1 1)

(2 3 4 5)

5.14.5.3 Zelfde oefening voor een lijst waar dubbels in voorkomen.

Moet je de procedure veranderen als er wel dubbels in de lijst mogen voorkomen? Zo ja, herschrijf de eerste versie. Zo nee, waarom niet?

> (all-but-interval '(1 2 2 2 3 4 4 5 5) 2 4)

(1 5 5)

5.14.6 Examen Informatica Partieel januari 1996

Veronderstel dat we woorden voorstellen als lijsten van symbolen. Bijvoorbeeld het woordje "computer" wordt voorgesteld door de lijst (c o m p u t e r). Veronderstel bovendien dat je beschikt over een predicaat klinker? dat #t geeft indien een symbool een klinker voorstelt, en #f in alle andere gevallen.

(define (klinker? x)   (or (eq? x 'a) (eq? x 'e) (eq? x 'i)       (eq? x 'o) (eq? x 'u)))

5.14.6.1 Procedure p-taal

Schrijf een procedure die als invoer zo’n woord neemt, en dit "vertaalt" in de "p-taal" door elke klinker te vervangen door diezelfde klinker, gevolgd door een 'p, en dan nog eens die klinker. Doe dit zowel op recursieve als iteratieve wijze. Noem de recursieve versie (rec-p-taal woord). Noem de iteratieve versie (iter-p-taal woord). Welke van de twee versies is het snelst?

> (rec-p-taal '(c o m p u t e r))

(c o p o m p u p u t e p e r)

> (rec-p-taal '(w e t e n s c h a p p e n))

(w e p e t e p e n s c h a p a p p e p e n)

> (iter-p-taal '(c o m p u t e r))

(c o p o m p u p u t e p e r)

5.14.7 Examen Informatica Partieel januari 1997

Veronderstel dat we een woord voorstellen als een opeenvolging van symbolen in een lijst. Bijvoorbeeld "hottentottententen" wordt voorgesteld als '(h o t t e n t o t t e n t e n t e n).

5.14.7.1 Tel opeenvolging van letters

Schrijf een procedure die telt hoeveel keer 2 gegeven letters onmiddellijk na elkaar in een gegeven woord voorkomen. Doe dit zowel op recursieve als iteratieve wijze. Noem de recursieve versie (rec-count-2-consecutive woord). Noem de iteratieve versie (iter-count-2-consecutive woord).

> (rec-count-2-consecutive 'n 't '(h o t t e n t o t t e n t e n t e n))

3

> (rec-count-2-consecutive 'e 'n '(h o t t e n t o t t e n t e n t e n))

4

> (iter-count-2-consecutive 'n 't '(h o t t e n t o t t e n t e n t e n))

3

> (iter-count-2-consecutive 'e 'n '(h o t t e n t o t t e n t e n t e n))

4

5.14.7.2 Veralgemening

Veralgemeen naar keuze één van je procedures uit Tel opeenvolging van letters tot een procedure count-n-consecutive die als invoer een lijst van letters en een woord krijgt, en telt hoeveel keer de gegeven sequentie van letters in het woord voorkomt.

Let op! Hou rekening met het feit dat in een woord zoals "barbapapa" de combinatie van letters "apa" twee keer voorkomt, maar dat de combinaties elkaar overlappen. De letter "a" die in de ene combinatie (barbapapa) als laatste letter wordt gebruikt, wordt in de tweede combinatie (barbapapa) als eerste letter gebruikt.

> (count-n-consecutive '(t e n)                        '(h o t t e n t o t t e n t e n t e n))

4

> (count-n-consecutive '(o t t e n)                        '(h o t t e n t o t t e n t e n t e n))

2

5.14.8 Examen Informatica januari 1999

5.14.8.1 Splits resultaten van een examen

Op het secretariaat van de vakgroep computerwetenschappen wil men op het einde van de examenperiode op een eenvoudige wijze een overzicht bekomen van de behaalde resultaten. De professoren dienen resultaten in door ze voor te stellen als een lijst: '("algoritmen en datastructuren" 12 8 17 15 6 15).

Het overzicht dat gevraagd wordt, splitst de puntenlijst ten opzichte van het gemiddelde. Er worden dus twee sublijsten gevormd met in de ene lijst de cijfers onder het gemiddelde en in de andere lijst de cijfers boven het gemiddelde.

Schrijf Hiervoor een procedure. Voor het vak algoritmen en datastructuren zal het overzicht er als volgt uitzien: '("algoritmen en datastructuren" (12 8 6) (17 15 15)). Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-splits resultaten). Noem de iteratieve versie (iter-splits resultaten).

> (rec-splits '("algoritmen en datastructuren" 12 8 17 15 6 15))

("algoritmen en datastructuren" (12 8 6) (17 15 15))

> (iter-splits '("algoritmen en datastructuren" 12 8 17 15 6 15))

("algoritmen en datastructuren" (12 8 6) (17 15 15))

5.14.8.2 Overzicht voor meerdere vakken

Schrijf een procedure (splits-alle lijst-resultaten) die een overzicht berekent voor alle vakken. Merk op dat er voor de verschillende vakken niet noodzakelijk evenveel cijfers zijn.

> (splits-alle '("1ste BA CW"                  ("algoritmen en datastructuren" 12 8 17 15 6 15)                  ("structuur van computerprogramma's" 15 18 6 12 11)))

("1ste BA CW"  ("algoritmen en datastructuren" (12 8 6) (17 15 15))  ("structuur van computerprogramma's" (6 12 11) (15 18)))

5.14.9 Examen Informatica augustus 2009

5.14.9.1 Vergelijken van twee lijsten

Schrijf een functie die twee niet-geneste lijsten lijst1 en lijst2 als invoer neemt, en als resultaat een getal (eventueel 0) teruggeeft dat uitdrukt tot waar beide lijsten dezelfde elementen bevatten (te beginnen vanaf het eerste element). Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-compare lijst1 lijst2). Noem de iteratieve versie (iter-compare lijst1 lijst2).

> (rec-compare '(a b c d e f g) '(a b c x y))

3

> (rec-compare '(x a b) '(a b c d e f g))

0

> (rec-compare '(a b c e f g) '(a b))

2

> (iter-compare '(a b c d e f g) '(a b c x y))

3

> (iter-compare '(x a b) '(a b c d e f g))

0

> (iter-compare '(a b c e f g) '(a b))

2

5.14.9.2 Vergelijk twee lijsten met een bepaalde test

Schrijf een variant van de functie compare die drie argumenten als invoer neemt, namelijk lijst1, lijst2 en een willekeurige vergelijkingstest. Deze test wordt gebruikt om de elementen van de twee lijsten te vergelijken. Het resultaat van deze variant is net zoals bij de functie uit Vergelijken van twee lijsten een getal dat uitdrukt tot waar beide lijsten voldoen aan de vergelijkingstest. Noem deze versie (algemene-compare lijst1 lijst2 test).

5.14.9.3 Elementen groter?

Maak gebruik van de functie die je in Vergelijk twee lijsten met een bepaalde test geschreven hebt om na te gaan tot welke positie lijst1 groter is dan lijst2. Noem de procedure (compare-greater lijst1 lijst2).

> (compare-greater '(3 5 6 1 2 5) '(2 1 0 8 5 5))

3

5.14.10 Examen Informatica januari 2005

Gegeven zijn 2 vlakke lijsten van dezelfde lengte. De eerste lijst is een alfabetische namenlijst, die alle namen bevat van de studenten die het vak Structuur I volgen. De tweede lijst is een puntenlijst, die uitsluitend uit getallen bestaat. Een getal op een bepaalde positie uit deze lijst is het cijfer behaald voor Structuur I door de student die op dezelfde positie in de namenlijst staat.

5.14.10.1 Geslaagd

Schrijf een functie in Scheme die met behulp van deze twee lijsten, een lijst construeert met alle namen van die studenten die 10 of meer behaalden op het vak Structuur I. Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-geslaagd namen punten). Noem de iteratieve versie (iter-geslaagd namen punten).

Bijvoorbeeld:

> (rec-geslaagd '(wendy dirk kris jan eef) '(12 7 10 9 18))

(wendy kris eef)

> (iter-geslaagd '(wendy dirk kris jan eef) '(12 7 10 9 18))

(wendy kris eef)

5.14.10.2 Algemener

Veronderstel dat de puntenlijst uitgebreid wordt naar een lijst van lijstjes. Elk deellijstje op een bepaalde positie bevat nu de cijfers voor respectievelijk de vakken Structuur I, AlgoData I, Grondslagen I en Discrete I. Deze cijfers behoren tot de student die je in de namenlijst vindt op dezelfde positie.

Schrijf een algemene functie show die gegeven de namenlijst, de uitgebreide puntenlijst en een test, een lijst construeert van alle studenten die aan deze test voldoen.

> (show '(wendy dirk kris jan eef)         '((12 13 15 18) (7 10 14 17) (10 8 7 11)                        (9 12 11 10) (18 14 17 19))         (lambda (punten)           (and (>= (car punten) 10)                (>= (cadr punten) 10)                (>= (caddr punten) 10)                (>= (cadddr punten) 10))))

(wendy eef)

5.14.10.3 Hergebruik

Gebruik je oplossing voor show om een functie one te schrijven die alle namen teruggeeft van die studenten die slechts 1 buiscijfer (< 10) behaalden. Bijvoorbeeld:

> (one '(wendy dirk kris jan eef)        '((12 13 15 18) (7 10 14 17) (10 8 7 11)                        (9 12 11 10) (18 14 17 19)))

(dirk jan)

5.14.11 Examen Informatica januari 2006

5.14.11.1 Comprimeer

Schrijf een procedure die een lijst temperatuursmetingen als parameter neemt en een nieuwe lijst teruggeeft waarin opeenvolgende gelijke metingen verkort worden voorgesteld. Dit gebeurt door een lijstje van 2 getallen. Het eerste getal is de eigenlijke temperatuursmeting, het tweede getal is het aantal maal dat deze meting achtereenvolgens werd waargenomen. Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-comprimeer metingen). Noem de iteratieve versie (iter-comprimeer metingen).

> (rec-comprimeer '(37.5 37.5 37.2 38.0 38.0 38.0 38.3))

((37.5 2) (37.2 1) (38.0 3) (38.3 1))

> (iter-comprimeer '(37.5 37.5 37.2 38.0 38.0 38.0 38.3))

((37.5 2) (37.2 1) (38.0 3) (38.3 1))

5.14.11.2 Algemene versie voor comprimeren

Veralgemeen één van de procedures uit Comprimeer tot een procedure (comprimeer-algemeen lst op) die dezelfde compressie-operatie doet, maar nu een extra parameter op neemt, d.i. de operator waarmee de elementen op gelijkheid getest moeten worden.

5.14.11.3 Herschrijf

Herschrijf m.b.b. de procedure comprimeer-algemeen de procedure comprimeer uit Comprimeer. Schrijf eveneens d.m.v. comprimeer-algemeen een procedure (comprimeer-zonder-decimalen metingen) die dezelfde compressie-operatie uit Comprimeer uitvoert, maar nu 2 temperatuursmetingen als gelijk beschouwt als het gehele deel voor de komma gelijk is.

5.14.12 Examen Informatica januari 2008

Het is solden in de winkelketen Z&M. Bij aankoop van een jas krijg je 50% korting, bij aankoop van een kleedje 50%, bij aankoop van een rok 30% en bij aankoop van een trui 20% en voor al de rest 25%. De ontwikkelaar die de nodige software voor het kassasysteem van de winkelketen moet schrijven, stelt deze kortingen als volgt voor '((jas 50) (kleed 50) (rok 30) (trui 20)).

De aankoop van een bepaalde klant wordt eveneens in een geneste lijststructuur voorgesteld. Bvb. Jan koopt een jas van 100 euro, een trui van 25 euro, een rok van 70 euro en een T-shirt van 20 euro: '((jas 100) (trui 25) (rok 70) (t-shirt 20)).

5.14.12.1 Bereken totaal

Schrijf nu een procedure die voor de aankoop van een klant het totale bedrag berekent. Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-totaal aankopen kortingen). Noem de iteratieve versie (iter-totaal aankopen kortingen).

> (rec-totaal '((jas 100) (trui 25) (rok 70) (t-shirt 20))           '((jas 50) (kleed 50) (rok 30) (trui 20)))

134

> (iter-totaal '((jas 100) (trui 25) (rok 70) (t-shirt 20))                '((jas 50) (kleed 50) (rok 30) (trui 20)))

134

5.14.12.2 Herschrijf procedure totaal

Veronderstel dat er reeds een procedure korting bestaat die gegeven een artikel, de korting voor dit artikel teruggeeft. Schrijf de procedure totaal uit Bereken totaal zodanig dat de parameter korting in (totaal aankoop korting) die procedure bevat.

5.14.12.3 Korting

Implementeer ook de procedure korting voor de winkelketen Z&M (m.a.w. bij aankoop van een jas rijg je 50% korting, bij aankoop van een kleedje 50%, bij aankoop van een rok 30%, bij aankoop van een trui 20% en voor al de rest 25%).

> (totaal '((jas 100) (trui 25) (rok 70) (t-shirt 20)) korting)

134

5.14.13 Examen Informatica Partieel januari 1994

5.14.13.1 Filteren van elementen in een lijst

Schrijf een hogere-orde procedure filter die een gegeven predicaat loslaat op alle elementen van een lijst. Ze geeft een nieuwe lijst terug met alle elementen waarvoor het predicaat waar is.

> (filter (lambda (x) (= (modulo x 2) 1)) '(1 2 3 4 5 6 7 8))

(1 3 5 7)

5.14.13.2 Lijst van alle niet-getallen

Gebruik de bovenstaande filter en het standaard-predicaat number? (#t als de parameter een getal is, #f in alle andere gevallen) om een procedure (filter-not-nbrs lst) te schrijven die alle NIET-getalen van een lijst teruggeeft.

> (filter-not-nbrs '(1 a b 33 7 c))

(a b c)

5.14.13.3 Deep-filter

Herwerk filter tot een nieuwe hogere-orde procedure deep-filter die werkt op een geneste lijst. Ze maakt een nieuwe lijst met dezelfde structuur als de gegeven lijst, maar de elementen waarvoor het predicaat vals is worden vervangen door een lege lijst, de elementen waarvoor het predicaat waar is blijven staan.

> (deep-filter (lambda (x) (odd? x))                '(1 2 3 (4) (5 (6 7) 8) (9) (10 (11) 12) 13 14))

(1 () 3 (()) (5 (() 7) ()) (9) (() (11) ()) 13 ())

> (deep-filter number? '(1 (a b (1)) 5))

(1 (() () (1)) 5)

5.14.13.4 Deep-filter zonder lege lijsten

Tijdens het uittesten merken we op dat bovenstaande deep-filter teveel lege lijsten produceert. Als we bijvoorbeeld deep-filter oproepen met parameters number? en '(1 (a b (1)) 5) bekomen we (1 (() () (1)) 5). Herwerk daarom deep-filter tot een deep-filter2 zodat lege lijsten waar mogelijk verwijderd worden. Als we deep-filter2 oproepen met bovenstaande parameters moeten we (1 ((1)) 5) bekomen.

> (deep-filter2 number? '(1 (a b (1)) 5))

(1 ((1)) 5)