CODEWITHSUNDEEP
listrecursionprologappendprefix
InDaPond
InDaPond

Reputation: 572

Get "real" prefixes/suffixes/infixes in Prolog

the Prolog notation of prefix/suffix is a quite easy one: It pretty much puts all the work on append. For those who don't know:

prefix(P,L):-append(P,_,L).
suffix(S,L):-append(_,S,L).

Now this means, that the result for prefix(X,[a,b,c,d]). will be: X=[];X=[a];X=[a,b];X=[a,b,c];X=[a,b,c,d]

Here is my problem with this: I want a "real" prefix. Hence, a prefix cannot be empty, nor can the part following it be empty. So the result to the query prefix(X,[a,b,c,d]). should be

X=[a];X=[a,b];X=[a,b,c]

and that's it.

Unfortunately, the real beaty of the standard-built in prefix predicate is, that it can use the termination of append, which is append([],Y,Y). So it is pretty easy to know when to stop, picking the list apart one by one till the list is empty.

My termination means: Stop if there is exactly one element left in your list. How do I do this?

My naive result would be:

prefix(P,L):-
length(P,1),append(P,E,L),E/=[].

This feels wrong though. I'm at work so I haven't checked if this actually works, but it should:

Is there any more convenient way to do this? Same goes for suffix, which will be even harder since you do not have a way to adress the Tail as specific as the Head, I guess I'd just reverse the whole thing and then call prefix on it.

Infix will just be a combination of two.

I hope it is clear what I mean. Thanks for your input! tl;dr: How to write a predicate prefix/2 which only filters real prefixes, so the prefix itself can not be empty, nor can the list followed by it be empty.

Upvotes: 1

Views: 1557

Answers (2)

user1812457
user1812457

Reputation:

For the real prefix, you can try to do it like this:

list_prefix(List, [H|T]) :-
    append([H|T], [_|_], List).

This just says that the first argument must have at least one element, and the rest of the list must have at least one element.

And following the suggestion by @false to make it more explicit:

list_real_prefix(List, Prefix) :-
    Prefix = [_|_],
    Rest = [_|_],
    append(Prefix, Rest, List).

The "real" suffix will be exactly the same:

list_real_suffix(List, Suffix) :-
    Front = [_|_],
    Suffix = [_|_],
    append(Front, Suffix, List).

Upvotes: 4

lurker
lurker

Reputation: 58244

You can also use a DCG for this, which is descriptive:

list_prefix(P) --> non_empty_seq(P), non_empty_seq(_).
non_empty_seq([X]) --> [X].
non_empty_seq([X|Xs]) --> [X], non_empty_seq(Xs).

| ?- phrase(list_pref(P), [a,b,c,d]).

P = [a] ? a

P = [a,b]

P = [a,b,c]

no
| ?-

You can define the suffix similarly:

list_suffix(S) --> non_empty_seq(_), non_empty_seq(S).

Upvotes: 4

Related Questions