Funktionell programmering

Jag föreslår att ni löser uppgifterna 1 - 3 och tänker igenom uppgifterna 4 och 5.

Med utgångspunkt från definitionen av binära träd (se anteckningarna), ska följande uppgifter lösas med vår vanliga arbetmetodik.

1. Mycket lätt uppgift Skriv en funktion noder[tr], där tr är ett binärt träd. Fn returnerar antalet noder i ett träd.

2. Lätt uppgift Skriv en funktion inorder[tr], där tr är ett binärt träd. Funktionen returnerar en lista som innehåller alla noder ur tr i den ordning de skulle ges av en inorder-traversering.

Exempel:


              A
inorder[    /   \   ]     ==>  (B A D C)
           B     C
                /
               D

3. Ganska lätt Skriv en funktion isomorf[tr1;tr2], där tr1 och tr2 är binära träd. Funktionen avgör om träden är isomorfa

Två träd är isomorfa om de har samma struktur, oavsett vad noderna innehåller. Detta kan formaliseras på följande sätt:

Två träd är isomorfa omm
(i) Båda är tomma
(ii) Båda är konstruerade ochde vänstra delträden är isomorfa och de högra delträden är isomorfa

Ledning Jobba systematiskt, börja med att göra exempel.

4 och 5, bakgrund. Vi har infört den abstrakta datatypen släktträd (som binära träd) och har definierat följande primitiver:

is-empty[p]
is-same-person[p1,p2] som avgör om två släktträd är samma person
father[p], mother[p] returnerar en persons fader respektive moder
name[p] returnerar en persons namn
born-year[p] returnerar en persons födelesår
make-empty returnerar ett tomt släktträd
make-children[n,y,f,m] returnerar ett kontruerat träd

Träden är tänkta att för varje person ge moder och fader, deras föräldrar och deras förföräldrar etc. Med dessa struktur är det lätt att hitta äldre släkting och svårt (omöjligt?) att hitta någons avkomlingar.

4. Skriv en funktion find-some-persons som tar två argument, ett släktträd och ett årtal. Funktionen returnerar en lista av namnen på alla personer som är födda före detta årtal. Ingen hänsyn behöver tas till effektivitetsaspekter.

5. Skriv ett predikat related som tar två släktträd och avgör om de personer de båda träden representerar är släkt. Två personer är släkt om de har någon gemensam äldre släkting. Ingen hänsyn behöver tas till effektivitetsaspekter.

Ledning: Inför en abstrakt datatyp släktträd. Implementera den på de vanliga binära träden

 Anders Berglund Office: Room 1254 Department of
Computer Systems E-mail: Anders.Berglund@docs.uu.se
Box 325 Phone (work): +46 18 18 31 67 S-751 05 Uppsala Mobile phone:
+46 70 582 45 80 Sweden Fax (work): +46 18 55 02 25