Midterm Review
CSCE 322
Name:
Instructions
Please solve the problems presented below. Show your work to receive full credit; just an
answer is not enough. No Approximations.
1
Question 1 ()
Explain the connection between short-circuit Boolean expressions and normal-order evaluation
in functional programming.
Page 2
Question 2 ()
What does the following Haskell program compute?
mystery.hs
mystery : : I n t e g e r −> I n t e g e r
mystery 0 = 0
mystery n = 2 ∗ n − 1 + ( mystery (n−1))
Page 3
Question 3 ( points)
In the code below, the query ?- classmates(jane_doe, X) will succeed three times: twice
with X = jane_doe, and once with X = ajit_chandra. Show how to modify the classmates(X, Y)
rule so that a student is not considered a classmate of him or herself.
takes ( jane doe , h i s201 ) .
takes ( jane doe , cs254 ) .
takes ( a j i t chandra , art302 ) .
takes ( a j i t chandra , cs254 ) .
c l a s smate s (X, Y) :− takes (X, Z) , takes (Y, Z ) .
Page 4
Question 4 ( points)
What does the following Prolog program compute?
mystery01.pl
% ∗∗ i s r a i s i n g to a power
mystery ( 0 , 1 ) .
mystery (A,B) :− 0 i s mod(A, 2 ) , C i s A / 2 , mystery (C,D) , B i s D ∗∗ 2 , ! .
mystery (E,F) :− 1 i s mod(E, 2 ) , G i s E − 1 , mystery (G,H) , F i s H ∗ 2 , ! .
Page 5
Question 5 (10 points)
Given the following code, what values of Nebraska will let the query
?- mystery3([u,n,l],[u,n,o],Nebraska). succeed?
mystery03.pl
mystery3 ( [ ] , A,A) .
mystery3 ( [B |C] ,D,E):−
member(B,D) , % member i s t rue i f B i s in l i s t D
! ,
mystery3 (C,D,E) .
mystery3 ( [ F |G] ,H, [ F | J ]) :−
mystery3 (G,H, J ) .
Page 6
Question 6 (10 points)
Modify the code provided below so that the goal path(X,Y) for arbitrarily already-instantiated
X and Y will succeed no more than once, even if there are multiple paths from X to Y.
edge ( a , b ) .
edge (b , c ) .
edge ( c , d ) .
edge (d , e ) .
edge (b , e ) .
edge (d , f ) .
path (X,X) .
path (X,Y):− edge (Z ,Y) , path (X, Z ) .
Page 7
Question 7 (10 points)
Given the following code, what was the input to mystery if the output was "phobiarebyc"?
mystery04.hs
mystery : : [ Char ] −> [ Char ]
mystery [ ] = [ ]
mystery (b : bs ) = he lpe r (b : bs ) 5
he lpe r : : [ Char ] −> Int −> [ Char ]
he lpe r c 0 = c
he lpe r [ ] = [ ]
he lpe r (d : ds ) e = ( he lpe r ds ( e−1)) ++ [ d ]
Page 8
Question 8 ()
Given this Haskell function, what input would produce the output (3,0,1,0,2)?
mystery02.hs
1 mystery : : I n t e g e r −> ( Integer , Integer , Integer , Integer , I n t e g e r )
2 mystery n
3 | n >= 50 = ( a+1,b , c , d , e )
4 | n >= 20 = ( f , g+1,h , j , k )
5 | n >= 10 = (m, p , q+1,r , s )
6 | n >= 5 = ( t , u , v ,w+1,x )
7 | otherwi s e = (0 , 0 , 0 , 0 , n )
8 where ( a , b , c , d , e ) = mystery (n−50)
9 ( f , g , h , j , k ) = mystery (n−20)
10 (m, p , q , r , s ) = mystery (n−10)
11 ( t , u , v ,w, x ) = mystery (n−5)
Page 9
Question 9 ()
Given this Haskell function, and the input 5 [9,8,16,16,4,10,9,13], the result is False.
How many times is d evaluated during the computation of that result?
mystery03.hs
1 mystery2 : : Ord b => b −> [ b ] −> Bool
2 −− Ord i s a type that d e f i n e s o r d i n a l i t y ( o rde r ing ) .
3 −− Ord a l l ows f o r <,>, e t c .
4 −− Bool i s the type f o r Boolean va lues
5 mystery2 [ ] = Fal se
6 mystery2 a ( x : xs )
7 | a == x = True
8 | a < x = mystery2 a c
9 | otherwi se = mystery2 a d
10 where c = [ c | c<−xs , c11 d = [ d | d<−xs , d>x ]
Page 10
Question 10 (10 points)
Given this Haskell function, if the output of the function was 15, and the input to the function
was (D, 4), what was the value of D?
mystery114501.hs
1 mystery : : ( Integer , I n t e g e r ) −> I n t e g e r
2 mystery (a , b)
3 | a == b = 1
4 | b == 1 = a
5 | otherwi s e = ( mystery ( a−1,b−1)) + ( mystery ( a−1,b ) )
Page 11
Question 11 (13 points)
Given this Haskell function, provide one combinations of values for input01 and input02 that
could cause mystery 2 input01 input02 to return the output Indinol?
1145mysteryFinal.hs
1 mystery : : Int −> Char −> [ Char ] −>[Char ]
2 mystery 0 a = a
3 mystery [ ] = [ ]
4 mystery b c (d : ds )
5 | c == d = mystery (b−1) c ds
6 | otherwi s e = [ d ] ++ ( mystery b c ds )
Page 12
Question 12 (13 points)
Given these Prolog predicates, mystery([2,0,0,2]). evaluates to true, mystery([2,0,0,4]).
evalutes to false and mystery([r,X,n,n,e,r]). will evalute to true when X is unified with e.
How many attempts are made to match helper2 during the evaluation of mystery([a,l,a,s,k,a]).?
mystery1145final01.pl
1 mystery ( [ ] ) : − ! .
2 mystery (A):−
3 l ength (A, 1 ) ,
4 ! .
5 mystery ( [B |C]) :−
6 he lpe r (C,B) ,
7 he lpe r2 (C,D) ,
8 mystery (D) .
9
10 he lpe r ( [E ] ,E) : − ! .
11 he lpe r ( [ |F] ,G):−
12 he lpe r (F ,G) .
13
14 he lpe r2 ( [ ] , [ ] ) : − ! .
15 he lpe r2 ( [ J |K] , [ J |M]):−
16 he lpe r2 (K,M) .
Page 13
Question 13 (13 points)
Given these Prolog predicates, repeat([a,b],2,[a,a,b,b]). evaluates to true,
repeat([a,b],1,[a,a,b,b]). evalutes to false and
repeat([[[g,o],[b,i,g],[r,e,d]]],3,Result). will evalute to true when Result
is unified with [[[g,o],[b,i,g],[r,e,d]],[[g,o],[b,i,g],[r,e,d]],[[g,o],[b,i,g],[r,e,d]]].
How many times is repeat([],_,[]). successfully matched during the evaluation?
mystery1145final02.pl
1 repeat ( [ ] , , [ ] ) : −
2 w r i t e l n ( repeat ) .
3 repeat ( , 0 , [ ] ) .
4 repeat ( [H |T] ,N,D):−
5 he lpe r (H,N,A) ,
6 repeat (T,N,B) ,
7 append (A,B,D) ,
8 ! .
9
10 he lpe r ( [ ] , , [ ] ) .
11 he lpe r ( , 0 , [ ] ) .
12 he lpe r (C,E,F):−
13 G i s E−1,
14 he lpe r (C,G,H) ,
15 append ( [C] ,H,F ) .
Page 14
Question 14 (10 points)
Given the following code, what would the output of mystery be if the input was
["New York","Los Angeles","Chicago","Dallas","Houston","Philadelphia","Los Alamos"]?
mystery114801.hs
mystery : : [ [ Char ] ] −> [ [ Char ] ]
mystery [ ] = [ ]
mystery ( a : b ) = c ++ [ a ] ++ d
where c = mystery [ e | e<−b , ( l ength e)<=( length a ) ]
d = mystery [ f | f<−b , ( l ength f )>( l ength a ) ]
Page 15
Question 15 (10 points)
Given the following code, what would the input of mystery02 be if the output was
["h","oooo","wwww","nn","b","r","c"]?
mystery114802.hs
mystery02 : : Eq a => [ a ] −> [ [ a ] ]
mystery02 [ ] = [ ]
mystery02 (b : c ) = [ ( b : d ) ] ++ ( mystery02 f )
where d = [ e | e<−c , e==b ]
f = [ g | g<−c , g/=b ]
Page 16
Question 16 (12 points)
Given the following code, what is one value of Input will let the query
?- mystery(Input,[s,a,s,a,t,c,e,w,a]). succeed?
mystery1148.pl
num( 4 ) .
num( 3 ) .
num( 2 ) .
num( 1 ) .
mystery ( In , Out):−
num(Number ) ,
! ,
h e lpe r ( In , Number , Out ) .
he lpe r (A,N,B):−
num(N) ,
l ength (A,LA) ,
LA < N,
A = B,
! .
he lpe r (A,N,B):−
num(N) ,
P i s N − 1 ,
a s s i s t a n t (A,P,C) ,
apprent i c e (A,N,D) ,
he lpe r (D,N,E) ,
append (C,E,B) .
a s s i s t a n t ( , 0 , [ ] ) : − ! .
a s s i s t a n t ( [A |B] ,N, [ A |C]) :−
num(N) ,
P i s N − 1 ,
a s s i s t a n t (B,P,C) .
apprent i c e (A, 0 ,A) : − ! .
apprent i c e ( [ ] , 1 , [ ] ) : − ! .
apprent i c e ( [ |A] ,N,B):−
num(N) ,
P i s N − 1 ,
apprent i c e (A,P,B) .
Page 17
Question 17 (10 points)
For the code below,
get ( [Row |Rows ] , Where , What):−
l ength (Rows , RowsLength ) ,
0 i s mod( RowsLength , 2 ) ,
l ength (Row, Cols ) ,
getFRow(Row, RowWhere , What) ,
Where i s RowWhere + RowsLength ∗ Cols .
get ( [Row |Rows ] , Where , What):−
l ength (Rows , RowsLength ) ,
1 i s mod( RowsLength , 2 ) ,
w r i t e l n ( executed ) ,
l ength (Row, Cols ) ,
getBRow(Row, RowWhere , What) ,
Where i s RowWhere + RowsLength ∗ Cols .
get ( [ |Rows ] , Where , What):−
get (Rows , Where , What ) .
getFRow ( [ What | ] , 1 ,What ) .
getFRow ( [ | Tai l ] , Where , What):−
getFRow( Tail , TailWhere , What) ,
Where i s TailWhere + 1 .
getBRow ( [ What |T] , Where , What):−
l ength ( [ What |T] , Where ) .
getBRow ( [ |T] , Where , What):−
getBRow(T, Where , What ) .
For the query ?- get([[8,9,0],[7,8,5],[2,3,8]],Location,8)., how many times is Line
10 executed?
Page 18
Question 18 (12 points)
For the code below,
get ( [Row |Rows ] , Where , What):−
l ength (Rows , RowsLength ) ,
0 i s mod( RowsLength , 2 ) ,
l ength (Row, Cols ) ,
getFRow(Row, RowWhere , What) ,
Where i s RowWhere + RowsLength ∗ Cols .
get ( [Row |Rows ] , Where , What):−
l ength (Rows , RowsLength ) ,
1 i s mod( RowsLength , 2 ) ,
w r i t e l n ( executed ) ,
l ength (Row, Cols ) ,
getBRow(Row, RowWhere , What) ,
Where i s RowWhere + RowsLength ∗ Cols .
get ( [ |Rows ] , Where , What):−
get (Rows , Where , What ) .
getFRow ( [ What | ] , 1 ,What ) .
getFRow ( [ | Tai l ] , Where , What):−
getFRow( Tail , TailWhere , What) ,
Where i s TailWhere + 1 .
getBRow ( [ What |T] , Where , What):−
l ength ( [ What |T] , Where ) .
getBRow ( [ |T] , Where , What):−
getBRow(T, Where , What ) .
For the query ?- get([[8,9,0],[7,8,5],[2,3,8]],Whe,Wha)., in what order are Whe and
Wha given values if the user presses ; to get all values that satisfy the query?
Page 19

欢迎咨询51作业君