4

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

Danick
  • 135
  • 2
  • 9

3 Answers3

3

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).
Kijewski
  • 25,517
  • 12
  • 101
  • 143
2

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.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
  • Your solution seems too complex for the OP purpose and level of skill. – migfilg May 08 '15 at 16:04
  • 1
    @migfilg: You are free to give a less complex answer. – false May 08 '15 at 16:17
  • we cannot use complex solutions – Danick May 08 '15 at 16:27
  • @danick: yes, I would expect that. @false: The solution by @danick is almost ok for me, I would use a cut in the first clause to avoid for instance having a second wrong solution to `prefix(a,[a,b,a,c],L)`. I do not think I should post this as an answer. – migfilg May 08 '15 at 16:33
  • @migfilg: cut??? I cannot see a clean use here (unless you put a lot of extra effort into) – false May 08 '15 at 17:49
0
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 ,

Community
  • 1
  • 1
houssam
  • 1,823
  • 15
  • 27