prolog - How do I rewrite the following so it uses if_?

Question

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?

Answer 1

(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 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:

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:

1. T = true, Any = [] that's the empty list
2. T = false, dif(Any, []), Any is not [_|_] note how this inequality uses when/2
3. T = true, Any = [_] that's all lists with one element
4. T = 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