How do I rewrite the following so it uses if_?
(Sorry, I somewhat skipped this)
- Please refer to P07. It clearly states that it flattens out
[a, [b, [c, d], e]]
, but you and @Willem produce:
?- my_flatten([a, [b, [c, d], e]], X).
X = [a,b,[c,d],e]. % not flattened!
- And the solution given there succeeds for
?- my_flatten(non_list, X).
X = [non_list]. % unexpected, nothing to flatten
- Your definition of
is_list/1
succeeds foris_list([a|non_list])
. Commonly, we want this to fail.
What you need is a safe predicate to test for lists. So let's concentrate on that first:
What is wrong with is_list/1
and if-then-else? It is as non-monotonic, as many other impure type testing predicates.
?- Xs = [], is_list([a|Xs]).
Xs = [].
?- is_list([a|Xs]). % generalization, Xs = [] removed
false. % ?!? unexpected
While the original query succeeds correctly, a generalization of it unexpectedly fails. In the monotonic part of Prolog, we expect that a generalization will succeed (or loop, produce an error, use up all resources, but never ever fail).
You have now two options to improve upon this highly undesirable situation:
Stay safe with safe inferences, _si
!
Just take the definition of list_si/1
in place of is_list/1
. In problematic situations, your program will now abort with an instantiation error, meaning "well sorry, I don't know how to answer this query". Be happy for that response! You are saved from being misled by incorrect answers.
In other words: There is nothing wrong with ( If_0 -> Then_0 ; Else_0 )
, as long as the If_0
handles the situation of insufficient instantiations correctly (and does not refer to a user defined program since otherwise you will be again in non-monotonic behaviour).
Here is such a definition:
my_flatten(Es, Fs) :-
list_si(Es),
phrase(flattenl(Es), Fs).
flattenl([]) --> [].
flattenl([E|Es]) -->
( {list_si(E)} -> flattenl(E) ; [E] ),
flattenl(Es).
?- my_flatten([a, [b, [c, d], e]], X).
X = [a,b,c,d,e].
So ( If_0 -> Then_0 ; Else_0 )
has two weaknesses: The condition If_0
might be sensible to insufficient instantiations, and the Else_0
may be the source of non-monotonicity. But otherwise it works. So why do we want more than that?
In many more general situations this definition will now bark back: "Instantiation error"! While not incorrect, this still can be improved. This exercise is not the ideal example for this, but we will give it a try.
Use a reified condition
In order to use if_/3
you need a reified condition, that is, a definition that carries it's truth value as an explicit extra argument. Let's call it list_t/2
.
?- list_t([a,b,c], T).
T = true.
?- list_t([a,b,c|non_list], T).
T = false.
?- list_t(Any, T).
Any = [],
T = true
; T = false,
dif(Any,[]),
when(nonvar(Any),Any\=[_|_])
; Any = [_],
T = true
; Any = [_|_Any1],
T = false,
dif(_Any1,[]),
when(nonvar(_Any1),_Any1\=[_|_])
; ...
So list_t
can also be used to enumerate all true
and false
situations. Let's go through them:
T = true, Any = []
that's the empty listT = false, dif(Any, []), Any is not [_|_]
note how this inequality useswhen/2
T = true, Any = [_]
that's all lists with one elementT = true, Any = [_|_Any1] ...
meaning: we start with an element, but then no list
list_t(Es, T) :-
if_( Es = []
, T = true
, if_(nocons_t(Es), T = false, ( Es = [_|Fs], list_t(Fs, T) ) )
).
nocons_t(NC, true) :-
when(nonvar(NC), NC \= [_|_]).
nocons_t([_|_], false).
So finally, the reified definition:
:- meta_predicate( if_(1, 2, 2, ?,?) ).
my_flatten(Es, Fs) :-
phrase(flattenl(Es), Fs).
flattenl([]) --> [].
flattenl([E|Es]) -->
if_(list_t(E), flattenl(E), [E] ),
flattenl(Es).
if_(C_1, Then__0, Else__0, Xs0,Xs) :-
if_(C_1, phrase(Then__0, Xs0,Xs), phrase(Else__0, Xs0,Xs) ).
?- my_flatten([a|_], [e|_]).
false.
?- my_flatten([e|_], [e|_]).
true
; true
; true
...
?- my_flatten([a|Xs], [a]).
Xs = []
; Xs = [[]]
; Xs = [[],[]]
...
?- my_flatten([X,a], [a]).
X = []
; X = [[]]
; X = [[[]]]
; X = [[[[]]]]
...
?- my_flatten(Xs, [a]).
*** LOOPS *** at least it does not fail