Eenvoudig voorbeeld: Steden in Belgie - Belgie bestaat uit twee delen: Vlaanderen en Wallonie
In Vlaanderen zijn er twee provincies die ons interesseren: Oost-Vlaanderen en Limburg
Idem voor Wallonie: Henegouwen en Namen
In Oost-Vlaanderen zijn Gent en Lokerenen belangrijke steden, terwijl Limburg rekent op Hasselt, Maaseik en Bree
Henegouwen heeft als belangrijke steden Bergen en Charleroi
In de provincie Namen kan je veel mooie dingen zien in zijn hoofdplaats Namen en rotsen beklimmen in Dinan
Eenvoudig voorbeeld: Steden in Belgie
- Belgie bestaat uit twee delen: Vlaanderen en Wallonie
In Vlaanderen zijn er twee provincies die ons interesseren: Oost-Vlaanderen en Limburg
Idem voor Wallonie: Henegouwen en Namen
In Oost-Vlaanderen zijn Gent en Lokerenen belangrijke steden, terwijl Limburg rekent op Hasselt, Maaseik en Bree
Henegouwen heeft als belangrijke steden Bergen en Charleroi
In de provincie Namen kan je veel mooie dingen zien in zijn hoofdplaats Namen en rotsen beklimmen in Dinant
Een voorstelling van de data (1)
De data stellen we voor in lijsten.
De naam van elke lijst is een intermediaire knoop (inclusief de wortel)
De inhoud van de lijst zijn de kinderen van de beschouwde lijst
make “Belgie [Vlaanderen Wallonie]
To land ... end
Een voorstelling van de data (2)
to land
make "Belgie [Vlaanderen Wallonie]
make "Vlaanderen [Oost-Vlaanderen Limburg]
make "Wallonie [Henegouwen Namen]
make "Oost-Vlaanderen [Gent Lokeren]
make "Limburg [Hasselt Maaseik Bree]
make "Henegouwen [Bergen Charleroi]
make "Namen [Dinant Namen]
end
Op zoek naar een blad (1)
Twee procedures: Eentje om te controleren of de knoop het gevraagde bevat, eentje om af te dalen in de boom
to zoek_knoop :stad :deel_boom ... end
to zoek_knoop_bij_kinderen :stad :nageslacht ...end
De eerste roept de tweede om knopen te expanderen, de tweede roept de eerste om de geëxpandeerde knopen te evalueren
Op zoek naar een blad (2)
to zoek_knoop :stad :deel_boom
Als de te zoeken stad overeenkomt met de de naam van deel_boom dan is de stad gevonden en geven we die terug
Als er geen variabele bestaat met de naam van de deelboom dan loopt de procedure ten einde
Aanmaken locale variabele om kinderen te onderzoeken
To zoek_knoop_bij_kinderen aanroepen om kinderen te controleren
Als de locale variable leeg is, is er niets gevonden en keren we terug
Anders voegen we vooraan de lijst van knopen onderweg naar het doel, de naam van de huidige deel_boom toe, en geven we dit terug
Op zoek naar een blad (3)
to zoek_blad_bij_kinderen :stad :nageslacht
Als nageslacht leeg is, zijn er geen nakomelingen en geven we de lege lijst terug
Maak een locale variabele aan om eerste kind uit de lijst te onderzoeken mbv zoek_blad
Roep zoek_blad op met het eerste kind
Als de variabele niet leeg is, werd het kind gevonden en wordt het pad die in de variable opgeslagen ligt teruggegeven
Anders zoeken we verder bij volgend kind (procedure roept zichzelf aan)
Op zoek naar een blad (4)
to zoek_knoop :stad :deel_boom
if equalp :stad :deel_boom [output (list :stad)]
if not namep :deel_boom [output [ ]]
localmake "afdaler zoek_knoop_bij_kinderen :stad (thing :deel_boom)
if emptyp :afdaler [output [ ]]
output fput :deel_boom :afdaler
end
Op zoek naar een blad (5)
to zoek_knoop_bij_kinderen :stad :nageslacht
if emptyp :nageslacht [output [ ]]
localmake "kind zoek_knoop :stad first :nageslacht
if not emptyp :kind [output :kind]
output zoek_knoop_bij_kinderen :stad butfirst :nageslacht
end
Problemen
Opzoeken van de Stad Namen: conflicteert met Provincie Namen
Opzoeken van alle steden in Namen moet ook kunnen
Aan de namen van variabelen het cijfer van het niveau toevoegen: make “Namen3 [Namen Dinant]: dit is omslachtig
Naar een nieuwe representatie van data
Nieuw representatie (1)
Abstracte voorstelling boom in een lijst
Constructor maak_boom :knoopnaam :kinderen
Selectors: to kinderen :knoop en to knoop_naam :knoop
to is_blad :knoop
Nieuw representatie (2)
to maak_boom :knoopnaam :kinderen
output fput :knoopnaam :kinderen
End (constructor)
to kinderen :knoop
output butfirst :knoop
end (selector)
to knoop_naam :knoop
output first :knoop
end (selector)
to is_blad :knoop
output emptyp kinderen :knoop
end (nodige hulpfunctie)
Nieuwe representatie (3)
Nog twee hulpprocedures:
to maak_blad :knoop
output maak_boom :knoop [ ]
End
Vb: maak_blad :Belgie -> [Belgie]
to maak_bladeren :bladeren
output map [maak_blad ?] :bladeren
End
Vb: maak_bladeren [Bergen Charleroi] -> [ [Bergen] [Charleroi] ]
We moeten kunnen meegeven of we op zoek gaan naar een blad (waarbij we het pad teruggeven) of naar een interne knoop (waarbij we de deel-boom onder deze knoop weergeven.
We moeten op zoek kunnen gaan naar één enkele knoop
Aanpassing zoek_knoop_mode
to zoek_knoop_mode :knoop :deel_boom :overzicht
Als we een overzicht moeten geven EN de knoop_naam van de deel_boom is de te zoeken knoop dan geven we de deelboom terug
Als de deel_boom een blad is en gelijk is aan de te zoeken :knoop dan geven we het blad terug, anders geven we de lege lijst terug
Aanmaken locale variabele om kinderen te onderzoeken
To zoek_knoop_bij_kinderen aanroepen om kinderen te controleren
Als de locale variable leeg is, is er niets gevonden en keren we terug
Bij het terugkeren met een overzicht geven we de lokale variable terug anders voegen we vooraan de lijst in de locale variabele de naam van deze deelboom toe
Aanpassing zoek_knoop_mode
to zoek_knoop_mode :knoop :deel_boom :overzicht
if and :overzicht (equalp :knoop knoop_naam :deel_boom)[output :deel_boom]
if is_blad :deel_boom ~
[ifelse equalp :knoop knoop_naam :deel_boom
[output (list :knoop)]
[output [ ] ] ]
localmake "afdaler zoek_knoop_bij_kinderen :knoop (kinderen :deel_boom) :overzicht
if emptyp :afdaler [output []]
output ifelse :overzicht [:afdaler] [fput (knoop_naam :deel_boom) :afdaler]
end
Aanpassing zoek_knoop_bij_kinderen
to zoek_knoop_bij_kinderen :knoop :nageslacht :overzicht
if emptyp :nageslacht [output[]]
localmake "kind zoek_knoop_mode :knoop first :nageslacht :overzicht
if not emptyp :kind [output :kind]
output zoek_knoop_bij_kinderen :knoop butfirst :nageslacht :overzicht
End
Oproepen van verschillende functies
to zoek_stad :stad :boom
output zoek_knoop_mode :stad :boom "false
end
to zoek_steden :knoop :boom
output zoek_knoop_mode :knoop :boom "true
end
to zoek_knoop :knoop :boom
localmake "gevonden zoek_knoop_mode :knoop :boom "true
ifelse emptyp :gevonden [output "niets] [output first :gevonden]
end
Comments