Prolog：获取列表的前“N”个元素

Question

我需要编写一个 Prolog 谓词

take(L, N, L1)

，如果列表

L1

以相同的顺序包含列表

N

的第一个

L

元素，则该谓词会成功。例如：

?- take([5,1,2,7], 3, L1).
L1 = [5,1,2]
?- take([5,1,2,7], 10, L1).
L1 = [5,1,2,7] 

到目前为止，Prolog 对我来说没什么意义，而且我很难分解它。这是我到目前为止所拥有的：

take([H|T], 0, []).
take([H|T], N, L1) :-
   take(T, X, L2),
   X is N-1.

你能解释一下我在这里做错了什么吗？

Answer 1

这是一个定义，它在 Haskell

1

等函数式语言中实现了 ^take 的关系对应项。首先，参数顺序应该不同，这有利于部分应用。有一个削减，但只有在内置错误检查

(=<)/2

之后，如果参数包含变量，就会产生

instantiation_error

。

take(N, _, Xs) :- N =< 0, !, N =:= 0, Xs = [].
take(_, [], []).
take(N, [X|Xs], [X|Ys]) :- M is N-1, take(M, Xs, Ys).

?- take(2, Xs, Ys).
   Xs = [], Ys = []
;  Xs = [_A], Ys = [_A]
;  Xs = [_A,_B|_C], Ys = [_A,_B].

注意上面的查询是如何读取的：

如何从

Xs

中取出 2 个元素来得到

Ys

？

有3种不同的答案。如果

Xs

为空，则

Ys

也为空。如果

Xs

是一个包含一个元素的列表，那么

Ys

也是一个。如果

Xs

至少有 2 个元素，那么这两个就是

Ys

。

---

^{1) 唯一的区别是}

take(-1, Xs,Ys)

失败了（对于所有

Xs, Ys

）。也许最好的办法是发出类似于

domain_error

的

arg(-1,s(1),2)

Answer 2

findall/3 它有点像 Prolog 的“瑞士刀”。我会使用这个片段：

take(Src,N,L) :- findall(E, (nth1(I,Src,E), I =< N), L).

Answer 3

@CapelliC的代码可以工作if实例化是正确的；如果没有，它可能会表现出不稳定的行为：

？-取(Es, 0, Xs)。
**LOOPS** % 麻烦：目标没有终止

?- 取([A,_], 1, [x])。          
真的。                       ％麻烦：变量A仍然是未绑定

为了防止这种情况，您可以使用

iwhen/2

就像这样：

take(Src, N, L) :-
   iwhen(ground(N+Src), findall(E, (nth1(I,Src,E), I =< N), L)).

使用 SWI-Prolog 8.0.0 运行的示例查询：

？-取([a,b,c,d,e,f], 3, Ls)。
Ls = [a,b,c]。

?- 采用([a,b,c,d,e,f], N, Ls)。
错误：参数未充分实例化

?-取(Es, 0, Xs)。
错误：参数未充分实例化

?- 采用([A,_], 1, [x])。
错误：参数未充分实例化

现在更安全了！

Answer 4

显而易见的解决方案是：

take(List, N, Prefix) :-
    length(List, Len),
    (   Len =< N
    ->  Prefix = List
    ;   length(Prefix, N),
        append(Prefix, _, List)
    ).

思考越少，犯错误的机会就越少。它还使谓词更加通用。

Answer 5

你的基本情况很好

take([H|T], 0, []).

你也可以说如果 N 是 1 会怎样

take([H|T],1,[H]).

但是在递归情况下，某些变量没有像 L2 那样定义。所以我们可以把它写成

take([X|T1],N,[X|T2]):-
N>=0,
N1 is N-1,
take(T1,N1,T2).

在这种情况下，所有变量都是模式匹配的。

Answer 6

取（L，N，L1）：-长度（L1，N），附加（L1，_，L）。

Answer 7

这是高性能的、通用的和确定性的：

first_elements_of_list(IntElems, LongLst, ShortLst) :-
    LongLst = [H|T],
    (   nonvar(IntElems) -> Once = true
    ;   is_list(ShortLst) -> Once = true
    ;   Once = false
    ),
    first_elements_of_list_(T, H, 1, IntElems, ShortLst),
    (Once = true -> ! ; true).

first_elements_of_list_([], H, I, I, [H]).

first_elements_of_list_([_|_], H, I, I, [H]).

first_elements_of_list_([H|LongLst], PrevH, Upto, IntElems, [PrevH|ShortLst]) :-
    Upto1 is Upto + 1,
    first_elements_of_list_(LongLst, H, Upto1, IntElems, ShortLst).

swi-prolog 的结果：

?- first_elements_of_list(N, [a, b, c], S).
N = 1,
S = [a] ;
N = 2,
S = [a,b] ;
N = 3,
S = [a,b,c].

?- first_elements_of_list(2, [a, b, c], S).
S = [a,b].

下面是一个也支持的变体：

?- first_elements_of_list_more(10, [5, 1, 2, 7], L1).
L1 = [5,1,2,7].

first_elements_of_list_more(IntElems, [H|LongLst], [H|ShortLst]) :-
    once_if_nonvar(IntElems, first_elements_of_list_more_(LongLst, 1, IntElems, ShortLst)).

first_elements_of_list_more_([], Inc, Elems, []) :-
    (var(Elems) -> Inc = Elems
    ; Elems >= Inc).

first_elements_of_list_more_([_|_], E, E, []).

first_elements_of_list_more_([H|LongLst], Upto, IntElems, [H|ShortLst]) :-
    succ(Upto, Upto1),
    first_elements_of_list_more_(LongLst, Upto1, IntElems, ShortLst).

once_if_nonvar(Var, Expr) :-
    nonvar(Var, Bool),
    call(Expr),
    (Bool == true -> ! ; true).

nonvar(Var, Bool) :-
    (nonvar(Var) -> Bool = true ; Bool = false).

Answer 8

您可以使用

reif

和

clpfd

来挤出更多的通用性。

:- use_module(library(reif)).
:- use_module(library(clpfd)).
take(N, Xs, Xs1) :-
    N #>= 0,
    if_(;(N = 0, Xs = []),
        Xs1 = [],
        (
            [H|T]=Xs,
            [H|T1]=Xs1,
            N1 #= N - 1,
            take(N1, T, T1)
        )).

注意：如果您将代码中的

;(N = 0, Xs = [])

（顺便说一句，

;/3

来自

reif

）替换为

N = 0

，则实现不再容忍 N > X 长度的情况。

它对于原始问题中的两个示例都具有确定性。

?- take(3, [5,1,2,7], L1).
L1 = [5,1,2].
?- take(10, [5,1,2,7], L1).
L1 = [5,1,2,7] 

处理 false 答案中作为示例给出的查询

?- take(2, Xs, Ys).
Xs = Ys, Ys = [] ;
Xs = Ys, Ys = [_] ;
Xs = [_A, _B|_],
Ys = [_A, _B].

以及其他方向。 （我认为任何方向，如果我没有遗漏的话）。

?- take(N, [3,4,5], [3,4]).
N = 2 ;
false.