Let insert(Number, List1, List2) be a ternary predicate that succeeds if and only if its third argument, a sorted list of numbers 'List2' is obtained from its second argument, also a sorted list of numbers 'List1', by inserting 'Number' in the proper place. (The lists are sorted in ascending order.)
Assume it is implemented as follows:
insert(X, [H|T1], [H|T2]) :-
X>H,
!,
insert(X, T1, T2).
insert(X, L, [X|L]).
a. Provide an appropriate query to show that this program is incorrect with respect to the given specification. b. Change the program so that it works correctly.
Can anyone help me with this assignment?
The second rule succeeds for X in front of any list, e.g. ?- insert(3, [1,2], [3|T2]). giving a third argument of [3,1,2] which is not sorted, however the specification seems to describe the modes insert(+Number, +List1, -List2) where + is an input and - is an output, so any query giving partial or full input as List2 might be outside the specification, and not valid. This feels like the least nitpicky answer I have found; others are:
a sorted list of numbers 'List1', by inserting 'Number' in the proper place
?- insert([3], [1,2], List2). succeeds with List2 = [1, 2, [3]]. The specification says that List1 and List2 must be ascending lists of numbers, but it only says that the first argument is a variable named Number, it doesn't say it must be a number. So given an input which is not a number, the predicate should fail. This is fixable by making it fail on non-numeric inputs, e.g. adding number(X) checks.
that succeeds if and only if its third argument, a sorted list of numbers 'List2' is obtained from its second argument
?- insert(3, List1, [1,2,3]). does not obtain the third argument from the second argument. With [H|_] = [H|_] we can wonder if the left-H is obtained from the right-H or the other way around? But if the specification says "succeeds if and only if List2 is obtained from List1", well, it wasn't. Again, giving List2 as input might be outside the specification.
a sorted list of numbers 'List2' is obtained from its second argument a sorted list of numbers 'List1':
?- insert(3, [1,2,3.0], List2), msort(List2, List2). fails in SWI Prolog. Number is a number, List1 is clearly a sorted list of numbers, List2 is only an output, so msort should succeed. msort fails, so List2 must not be sorted, so insert/3 should not have succeeded, something is wrong. This is satisfying nitpicking on the details of integers vs floating point numbers and stable sorting(?) (try 3 < 3.0 and 3 > 3.0 and 3 = 3.0, in SWI Prolog they are all false) while being completely inside the specification, but I would be surprised if this is actually the intended answer. It's perhaps fixable with changing the condition to (X>H | X =:= H) to evaluate that 3.0 and 3 have the same value even though they don't unify.