Institut for Matematik og Datalogi Odense Universitet April 19, 1995

JFB

DM15 – F95 – Week 26

Lecture, April 10

We will began on chapter 2 in Mitchell’s monograph, and covered up through the fix axiom on page 63.

Lecture, April 24

We will continue on the second chapter of Mitchell’s monograph.

Lecture, May 1

We will continue on the second chapter of Mitchell’s monograph.

Problems to be discussed in week 18

• Do exercises 2.2.4, 2.2.5, 2.2.7 and 2.2.8 on page 58 of Mitchell.

• Do exercises 2.2.11 and 2.2.12 on page 60 of Mitchell.

• Do exercise 2.2.14 on page 64 of Mitchell.

• Do the following question from a past DM15 exam: Denne opgave handler om PCF, og hvordan man kan implementere et binært træ i PCF. Antag, at man har defineret følgende funktioner i PCF:

– En funktion less af type nat→nat→bool, sådan at less x y er true, hvis og kun hvis x < y. Ellers er resultatet false.

– En funktion pairnums af type nat→nat→nat, sådan at pairnums er en injektiv afbildning fra N I × N I til N I − {0}. (En mulig definition er pairnums n m = (n + m) ∗ (n + m + 1)/2 + m + 1.)

– En funktion projnum_{1} af type nat→nat, sådan at projnum_{1} (pairnums n m) = n.

– En funktion projnum_{2} af type nat→nat, sådan at projnum_{2} (pairnums n m) = m.

Nu kan man implementere et binært søgetræ med nøgler, der er naturlige tal. Et tomt træ repræsenteres af tallet 0. Et binært træ med nøglen x i roden, med venstre undertræ repræsenteret af l, og med højre undertræ repræsenteret af r, kan repræsenteres af pairnums (pairnums l r) x.

spørgsmål a

Hvordan repræsenterer man træet, der består af en rod med to sønner, hvor roden har nøglen 2, den venstre søn har nøglen 1, og den højre søn har nøglen 3?

spørgsmål b

Definer en funktion find af type nat → nat → bool. Det første argument er en repræsentation af et binært søgetræ, og det andet er en nøgle. Hvis nøglen findes i træet, så skal resultatet være true. Ellers skal det være false.

spørgsmål c

Definer en funktion insert af type nat → nat → nat. Det første argument er en repræsentation af et binært søgetræ, og det andet er en nøgle. Hvis nøglen findes i træet, så skal resultatet være førsteargumentet. Ellers skal det være repræsentationen af træet med den nye nøgle indsat, sådan at træet stædigvæk er et binært søgetræ.