Bemærkninger til vintereksamen 2000
Dette er ikke en standardbesvarelse, men blot nogle
bemærkninger til besvarelsen af opgaverne. Alle forbehold tages.
Opgave 1
Spørgsmål a:
map2 :: [a -> b] -> [[a] -> [b]]
mapd :: (a -> b) -> [[a]] -> [[b]]
Spørgsmål b:
(i) X = 1
X = 2
(ii) X = 1 Y = 1
X = 1 Y = 2
X = 2 Y = 1
X = 2 Y = 2
(iii) X = 1 Y = 1
X = 1 Y = 2
Opgave 2
Fortræffelige løsninger kan beses på siderne 345 og 365
i Thompson. :-(
Opgave 3
Spørgsmål a:
levelsWith _ [] = []
levelsWith j l = p : levelsWith (2*j) r
where (p,r) = splitAt j l
Spørgsmål b:
addLayer [] _ = []
addLayer (x:xs) [] = Fork x Null Null : addLayer xs []
addLayer (x:xs) (t:[]) = Fork x t Null : addLayer xs []
addLayer (x:xs) (t0:t1:ts) = Fork x t0 t1 : addLayer xs ts
Spørgsmål c:
mkHtree = head . mkHtrees . levels
Opgave 4
Spørgsmål a:
maxtree(OldTree,NewTree) :-
maxnode(OldTree,M),forcevalue(OldTree,M,NewTree).
maxnode([],0).
maxnode(n(V,L,R),M) :-
maxnode(L,ML),maxnode(R,MR),max_list([V,ML,MR],M).
forcevalue([],_,[]).
forcevalue(n(_,OL,OR),M,n(M,NL,NR)) :-
forcevalue(OL,M,NL),forcevalue(OR,M,NR).
Hvor max_list/2
antages at finde det største element i en liste.
Funktionen findes pudsigt nok i
GNU Prolog, men er
ellers simpel at skrive.
Spørgsmål b:
maxtree2(OldTree,NewTree) :- mt(OldTree,NewTree,M,0,M).
mt(n(V,A,B),n(H,A1,B1),H,AC,N) :-
V < AC,
mt(A,A1,H,AC,ACA),
mt(B,B1,H,ACA,N).
mt(n(V,A,B),n(H,A1,B1),H,AC,N) :-
V>= AC,
mt(A,A1,H,V,ACA),
mt(B,B1,H,ACA,N).
mt([],[],_,A,A).
Opgave 5
Spørgsmål a:
p(x)
p(y) # ~q(x,Z) # p(Z)
~p(f(x,y)) # ~q(x,Z) # p(Z)
Skolem-konstanter for eksistentielt kvantificerede variabler er konsekvent valgt
som de tilsvarende små bogstaver.
Spørgsmål b:
Forklaring af hjemmestrikket notation: C1 & C2 |== C3
,
hvor C
'erne er clauses, betyder, at man udleder
C3
fra C1
og C2
ved resolution.
!!
angiver resultatet af den umiddelbart foregående udledning.
~r & (~p # ~q # r) |== ~p # ~q
!! & (~t # p) |== ~q # ~t
!! & (~u # q) |== ~u # ~t
!! & (~s # u) |== ~s # ~t
!! & (~s # t) |== ~s
!! & s |==