从一个列表中创建子列表，给定索引和元素数量。Prolog。

Question

我想解决一个简单的Prolog问题，但我无法解决它。从一个列表中，我需要根据给定的索引I创建子列表，然后从I开始获取N个元素。如果索引大于列表长度，则会得到空的子列表。如果N（元素数量）大于列表中剩余的元素，则会获取从I到结尾的所有元素。

在这里，我已经完成了任务的一部分，可以从索引I获取下一个元素N。现在我要问的是任务中的另一部分：

1）当I（索引）大于列表长度时，我必须在子列表中获取一个空列表。

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

L=[]

2) 当N（下一个元素）的数量大于我们所剩余的元素数量时，我需要获取从该位置到末尾的所有元素。

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

L=[d]      

我已经有的代码是下面这个，它可以正常工作：

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).

- user3006475

---

看起来你已经有了一个很好的开端。需要注意的是你的第三个子句：你正在减少 K，你需要问问自己在这种情况下为什么要这样做，以及（如果你真的认为应该这样做）在什么条件下。此外，考虑到你想要一个“截断”的答案，如果 N 太大，你可能需要另一个（或不同的）基本情况子句来处理输入列表为空的情况。 - lurker

@mbratch：你的评论看起来是一个愿意学习的学生最好的答案...为什么不把它转换成一个答案呢？ - CapelliC

谢谢@CapelliC，我会这样做的。 - lurker

@user3006475，我的回答是否足够帮助你解决剩下的问题了？ - lurker

是的，谢谢，但我没有Prolog经验，也无法解决它。 我需要将我描述的两种情况写出来...我认为这不是很困难...但我无法解决它...但感谢您的解释...我更好地理解了。 - user3006475

你真正想要的是 sublist([], _, _, []). 否则你可能会得到一个未实例化的结果。例如，使用你展示的代码，如果查询 sublist([a,b,c,d], 4, 2, L). 你将得到 [d|_] 而不是 [d]。但是如果你使用 sublist([], _, _, []). 你将得到正确的结果 [d]，因为这个子句的意思是，“如果我从一个空列表中选择一个子列表，那么我将得到一个空列表”。 - lurker

Answer 1

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

这是一个很好的条款。它说，从列表[X|_]中以1为起始位置取长度为1的子列表是[X]。

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

这也是一个好的条款。它表示从[X|Xs]中以1开始的长度为K的子列表以X开头，并且有一个尾部Ys，该尾部是从第一个列表（Xs）的尾部开始的长度为K-1的子列表。

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

这句子有一个问题。如果您有一个列表[_|Xs]并希望从位置I（对于大于1的I）开始取长度为K 的子列表，则需要从其尾部以 I-1 位置开始取长度为K-1的子列表。问题是：为什么现在子列表需要长度K-1？这个句子的目的应该是将问题简化为处理起始索引为1的情况，然后让第二个句子来处理其余情况。

接着，在你所期望的行为定义中，你说：如果N（元素数量）大于列表中剩余的元素，我将得到从I到结尾的所有元素。 这个概念目前不在任何一个句子中。当前的基本情况是您的第一个句子，它明确要求长度为1以生成长度为1的列表。您需要另一个基本情况句子来处理第一个列表为空但K可能仍为任何值的情况。

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

只需用合理的内容填写?即可。 :)

- lurker

---

终于搞定了...现在它按照我的要求工作了，这个解释帮了我很多！！ - user3006475

@user3006475，太棒了！ - lurker

当我测试基本情况时，我遇到了一些问题。在SWI Prolog中，对于我在问题中描述的第一个情况，我得到了一个true作为答案，而不是空列表。在第二种情况下，我得到了正确的结果，但我的答案却不同：与这个答案L=[d]相比，我得到了这个L=[d|_G440]...你能帮我解决这个问题吗？ - user3006475

@user3006475，在您更新的答案中，您仍然缺少我建议的额外基本情况：sublist([], ?, _, ?)（在这里您需要决定?应该是什么）。换句话说，您需要一个情况来处理如果输入列表为空会发生什么。如果您需要更多关于该情况的帮助，请告诉我。因此，当您完成后，您将拥有4个子句而不仅仅是3个。 - lurker

@user3006475 这是因为规则 sublist([], I, _, L). 没有实例化 L 或 I。它们是单例的，所以你目前的子句是无效的。它当前的意思是，“如果输入列表为空，则不使用 I 并且输出是未定义的列表 L”。要找出 ? 的正确值，请问自己一个问题：如果输入列表为空，L 应该是什么？I 应该是什么（或者它是否重要？可以只用 _ 吗？） - lurker

Answer 2

仅为展示类似nth1/3这样的不确定性内置函数如何帮助...

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

编辑一条注释，说明这个“单行”实际上比精心制作的sublist/4更不高效。

事实上，

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].

我打算看看是否可以在findall谓词中加入某种剪枝来解决这个问题，但这是不太可能的。以下方案更好:

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].

- CapelliC

---

+1，因为能够使用内置函数进行一行解决方案的大师级表现。非常棒。 :) - lurker

这个程序现在按照我的意愿运行了...问题是我不能使用内置函数...真遗憾！ - user3006475

@mbratch：谢谢！我认为你的详细解释非常好。 - CapelliC

@user3006475：谢谢！当然，你可以不使用内置函数，但请注意is是一个内置函数... - CapelliC

Answer 3

这里有一个解决方案（虽然可能不是你的教授想要的）：

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!

这是一种方法，让Prolog的内置函数为您完成工作。

这里有另一种方法，不使用任何内置函数。这个方法使用一个帮助谓词，它只是将列表分成指定长度的前缀和剩余部分组成的后缀。

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!

- Nicholas Carey

---

第一个似乎很不对：“？-sublist([a，b，c，d]，2，2，L)。L = [a，b]。”和“？-sublist([a，b，c，d]，2，3，L)false。” - CapelliC

@CapelliC：修正了拼写错误。 - Nicholas Carey