I am doing some easy exercises to get a feel for the language.
is_list([]).
is_list([_|_]).
my_flatten([],[]).
my_flatten([X|Xs],RR) :-
my_flatten(Xs,R),
(is_list(X), !, append(X,R,RR); RR = [X | R]).
Here is a version using cut, for a predicate that flattens a list one level.
my_flatten([],[]).
my_flatten([X|Xs],RR) :-
my_flatten(Xs,R),
if_(is_list(X), append(X,R,RR), RR = [X | R]).
Here is how I want to write it, but it does not work. Neither does is_list(X) = true
as the if_
condition. How am I intended to use if_
here?
(Sorry, I somewhat skipped this)
[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!
?- my_flatten(non_list, X).
X = [non_list]. % unexpected, nothing to flatten
is_list/1
succeeds for is_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:
_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 behavior).
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.
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 uses when/2
T = true, Any = [_]
that's all lists with one elementT = true, Any = [_|_Any1] ...
meaning: we start with an element, but then no listlist_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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With