Create a sublist from a list given an index and a number of elements. Prolog

Question

I am trying to solve a simple prolog question but I am not able to solve it. From a list a need to create a sublist given the index I and then from I the next elements given as N. If the index is greater than the list lenght I will get the sublist empty. If N (number of elements) is greater than the rest of elements in the list I will get all the elements from I until the end.

Here, I got one part of the assignment, I can get from the index I, the next elements N. Now I ask about the other parts in the assignment:

1) When I (index) is longer than the list length, I have to get an empty list in the sublist.

?- sublist([a,b,c,d],5,2,L)

L=[]

2) When N (Next elements) is greater than the number of elements we have rest, I need to get all the elements from that position till the end.

?- sublist([a,b,c,d],4,4,L)

L=[d]

The code I already have is the next one, this one is working:

sublist([X|_],1,1,[X]).
sublist([],_,_,[]).% I use this one for the case bases
sublist([X|Xs],1,K,[X|Ys]):-
       K>1, 
       K1 is K-1,
       sublist(Xs,1,K1,Ys).
sublist([_|Xs],I,K,Ys):-
       I > 1, 
       I1 is I-1,
       sublist(Xs,I1,K,Ys).

That looks like a great start. One issue to look at is your third clause: you are decrementing `K`, and you need to ask yourself why you are doing so in this context and (if you really think you should) under what conditions. In addition, given your condition that you want a "truncated" answer if `N` is too large, you may need another (or a different) base case clause to deal with the case when the input list runs empty. — lurker, Dec 24 '13 at 19:42
@mbratch: your comment looks like the best possible answer for a student willing to learn... Why not convert it to an answer ? — CapelliC, Dec 24 '13 at 21:19
@user3006475, did my answer provide enough help for you to figure the rest out? — lurker, Dec 25 '13 at 19:06
Yes thanks, but I have no expierence with prolog and I cant solve it. I need to write the two cases I describe up...I think it is not very difficult...but I cant solve it...but thanks for your explanation...I understand it better — user3006475, Dec 25 '13 at 19:08
Really what you want is `sublist([], _, _, []).` otherwise you might get an uninstantiated result. For example, with the code you show, if you query `sublist([a,b,c,d], 4, 2, L).` you'll get `[d|_]` instead of `[d]`. But if you use `sublist([], _, _, []).` you get the correct result `[d]` because the clause says, *If I select a sublist from an empty list I get an empty list*. — lurker, Dec 25 '13 at 22:07

score 3 · Accepted Answer · answered Dec 24 '13 at 21:51

3

sublist([X|_], 1, 1, [X]).

This is a good clause. It says that a sublist of length 1 starting at 1 taken from the list [X|_] is [X].

sublist([X|Xs], 1, K, [X|Ys]) :-
    K > 1, 
    K1 is K - 1,
    sublist(Xs, 1, K1, Ys).

This is also a good clause. It says that the sublist of length K starting at 1 taken from [X|Xs] starts with X and has a tail Ys which is the sublist of length K-1 from the tail of the first list (Xs) starting at 1.

sublist([_|Xs], I, K, Ys) :-
    I > 1, 
    I1 is I - 1,
    K1 is K - 1,
    sublist(Xs, I1, K1, Ys).

This clause has an issue. If you have a list [_|Xs] and want to take a sublist of length K start at I (for I greater than 1), you take the sublist of length K-1 from its tail starting at position I-1. The question is: why would the sublist now need to be length K-1? The purpose of this clause should be to reduce the problem to the case where you're dealing with a starting index of 1, then let the second clause take care of the rest.

Then in your definition of the desired behavior, you have: If N (number of elements) is greater than the rest of elements in the list I will get all the elements from I until the end. This notion currently isn't in any of the clauses. The base case is currently your first clause which specifically requires a length of 1 to produce a list of length 1. You need another base case clause that handles the case where the first list goes empty but K might still be any value:

sublist([], ?, _, ?).

Just fill in the ? with something logical. :)

answered Dec 24 '13 at 21:51

lurker

56,987
9
69
103

Finally I got it...Now is working as I want, this explanation helps a lot!! – user3006475 Dec 25 '13 at 19:38
@user3006475 that's great! – lurker Dec 25 '13 at 19:41
I am getting some problems when I am testing the base cases. In the first case I described up in the question in SWI prolog I got a true as an answer instead of the empty list. And in the second case I get it well, but I get something else in my answer: insted this answer L=[d] I get this one L = [d|_G440] ... Can you help me with this? – user3006475 Dec 25 '13 at 19:54
1

@user3006475, in your updated answer you're still missing the additional base case that I suggested: `sublist([], ?, _, ?).` (where you decide what `?` should be). In other words, you need a case to handle what happens if the input list is empty. If you need more assistance with that case, let me know. So when you're done, you'll have 4 clauses rather than just 3. – lurker Dec 25 '13 at 20:17
I upload the question with the new code and I described the issues I am getting. I am getting a warning about singleton variables [I,L], maybe this is the cause. – user3006475 Dec 25 '13 at 20:56
1

@user3006475 That's because the rule `sublist([], I, _, L).` doesn't instantiate `L` or `I`. They are singleton and the clause isn't valid as you have it stated. It currently says, "If the input list is empty, don't use `I` and the output is an undefined list, `L`". To figure out the right things for the `?`, ask the question: What should `L` be if the input list is empty? What should `I` be (or does it even matter? Can it be just `_`?)? – lurker Dec 25 '13 at 21:04
Ok thanks, now working, I post the correct code in the question – user3006475 Dec 25 '13 at 21:18

CapelliC · Answer 2 · 2013-12-26T10:44:37.997

just to show how nondeterministic builtins like nth1/3 can help...

sublist(List, From, Count, SubList) :-
    findall(E, (nth1(I, List, E), I >= From, I < From + Count), SubList).

edit a note to say that this 'one liner' is actually a lot less efficient than a crafted sublist/4.

Indeed,

2 ?- N=1000000,length(L,N),time(sublist(L,N,1,V)).
% 3,000,014 inferences, 2.129 CPU in 2.134 seconds (100% CPU, 1409024 Lips)
N = 1000000,
L = [_G28, _G31, _G34, _G37, _G40, _G43, _G46, _G49, _G52|...],
V = [_G3000104].

3 ?- N=1000000,length(L,N),time(sublist(L,1,1,V)).
% 4,000,012 inferences, 2.549 CPU in 2.553 seconds (100% CPU, 1569076 Lips)
N = 1000000,
L = [_G28, _G31, _G34, _G37, _G40, _G43, _G46, _G49, _G52|...],
V = [_G3000104].

I'm going to see if some kind of cut inside findall' predicate could solve this problem, but it's unlikely. This one is better:

sublist(List, From, Count, SubList) :-
    To is From + Count - 1,
    findall(E, (between(From, To, I), nth1(I, List, E)), SubList).

18 ?- N=1000000,length(L,N),time(sublist(L,3,3,V)).
% 28 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 201437 Lips)
N = 1000000,
L = [_G682, _G685, _G688, _G691, _G694, _G697, _G700, _G703, _G706|...],
V = [_G3000762, _G3000759, _G3000756].

+1 for being the master of one line solutions using built-ins. Very nice. :) — lurker, Dec 25 '13 at 00:39
This one is working as I want....the point is I cannot use built-ins...What a pitty! — user3006475, Dec 25 '13 at 09:59
@mbratch: thanks! I think your detailed explanation is great. — CapelliC, Dec 25 '13 at 19:01
@user3006475: thanks! Of course, you *could* do without builtins, but note that **is** is a builtin... — CapelliC, Dec 25 '13 at 19:02

Nicholas Carey · Answer 3 · 2013-12-27T23:44:03.567

Here's one solution (though it's probably not what your professor wants):

sublist( Xs , Offset , Count , Ys ) :- %
  length(Prefix,Offset ) ,             % construct a list of variables of length 'offset'
  length(Ys,Count) ,                   % construct a list of variables of length 'count'
  append(Prefix,Suffix,Xs) ,           % strip the first first 'offset' items from the source list ,
  append(Ys,_,Suffix)                  % extract the first 'count' items from what's left.
  .                                    % easy!

That's one approach, letting Prolog's built-ins do the work for you.

Here's another approach that doesn't use any built-ins. This one uses one helper predicate that simply splits a list into a prefix of the specified length, and a suffix, consisting of whatever is left over.

sublist( Xs , Offset , Count , Ys ) :-
  split(Xs,Offset,_,X1) ,               % extract the first 'offset' items from the lsit and toss them
  split(X1,Count,Ys,_)                  % extract the first 'count' items from the remainder to get the result.
  .

split( []     , 0 , []     , []     ) .  % splitting a zero-length prefix from an empty list yields a zero-length prefix and a zero length suffix.
split( [X|Xs] , 0 , []     , [X|Xs] ) .  % splitting a zero-length prefix from a non-empty list yields a zero-length prefix and the non-empty list.
split( [X|Xs] , N , [X|Ps] , Qs     ) :- % Otherwise...
  N > 0 ,                                % - if the count is positive
  N1 is N-1 ,                            % - we decrement count
  split( Xs , N1 , Ps , Qs )             % - and recurse down, prepending the head of the source list to the prefix
  .                                      % Easy!

the first one seems badly wrong: `?- sublist([a,b,c,d],2,2,L). L = [a, b].` and `?- sublist([a,b,c,d],2,3,L). false. ` — CapelliC, Dec 25 '13 at 00:11

Create a sublist from a list given an index and a number of elements. Prolog

3 Answers3

Linked