CODEWITHSUNDEEP
listprologprefix
Danick
Danick

Reputation: 135

Prefix in Prolog

I'm new in Prolog. I have a problem about predicate prefix but a little bit different.

I want to get a prefix of a list but until an element The list can have repeat elements.

An example: 

prefix(Element, List, Prefix)
prefix(c, [a,b,c,d,e,f], [a, b])

The element is not included.

What I have so far is this

prefix(X, [X|T], []).
prefix(X, [Y|T], [Y|Z]):-
    prefix(X, T, Z).

But it does not work.

L = [a,b,c] ? prefix(b, L, Prefix).

no
?-

Thanks

Upvotes: 4

Views: 5108

Answers (3)

Kijewski
Kijewski

Reputation: 26022

With dif/2 you can explicitly state that for any member X preceding Element, X \== Element:

prefix(Element, [Element|_], []).
prefix(Element, [Head|List], [Head|Prefix]) :-
    dif(Element, Head),
    prefix(Element, List, Prefix).

or equally, because I wanted to use append/3 in the first iteration of my answer:

prefix(Element, List, Prefix) :-
    append(Prefix, [Element|_Suffix], List),
    maplist(dif(Element), Prefix).

For the suffix it is basically the same:

suffix(Element, List, Suffix) :-
    append(_Prefix, [Element|Suffix], List),
    maplist(dif(Element), Suffix).

If you don't want to use maplist(dif(Element), List):

all_dif(_, []).
all_dif(X, [H|T]) :- dif(X, H), all_dif(X, T).

Upvotes: 3

false
false

Reputation: 10102

Here is a solution using Definite Clause Grammars and the non-terminal all_seq//2:

prefix(X, Xs, Ys) :-
   phrase( ( all_seq(dif(X), Ys), [X], ... ), Xs).

... --> [] | [_], ... .

So the grammar (within phrase/2) reads:

There is 1. an initial sequence Ys with all elements different to X, followed by 2. X, followed by 3. anything.

There is still a downside, which is often the case when using DCGs: The implementation is not as determinate as it could be and thus leaves superfluous choicepoints around.

Upvotes: 2

houssam
houssam

Reputation: 1873

prefix(X,[X|T],[]).
prefix(X,[Y|T],Z) :- prefix(X,T,M)  , Z = [Y|M].

output:

?- L = [a,b,c,d,e,f] , prefix(d,L,G).
L = [a, b, c, d, e, f],
G = [a, b, c] .

?- L = [a,b,c,d,e,f] , prefix(e,L,G).
L = [a, b, c, d, e, f],
G = [a, b, c, d] .

EDIT #1
the original code is working , use (,) instead of (?) as following.

prefix(X,[X|T],[]).
prefix(X,[Y|T],[Y|Z]) :- prefix(X,T,Z).

output:

?- prefix(d , [a,b,c,d,e] , G).
G = [a, b, c]
?- L = [a,b,c] , prefix(b, L, Prefix).
L = [a, b, c],
Prefix = [a] .

EDIT #2 as user false mentioned in comment, I can confirm that you are right, but in my solution, I assume that the list contains unique elements:
prefix(d,[d,d],[d]) succeeds - it should fail ,

Upvotes: 0

Related Questions