以非递归的方式在Prolog中获取列表的长度

Question

我有以下代码用于在Prolog中获取列表的长度，它使用递归方式实现。 是否有其他获取长度的方法？

len([], 0).
len([H|T], N) :-
    len(T, NT), N is NT + 1.

任何建议都将不胜感激。

- user4406062

---

你可以使用内置谓词length(List, N)。 :) 为什么需要它是非递归的？ - lurker

我正在学习Prolog，我想知道除了递归之外，在Prolog中完成简单任务的其他方法是否存在。内置谓词本身是否再次使用递归？ - user4406062

Prolog内置是否使用递归或其他语言，取决于Prolog的实现。有许多操作列表的方法可以不使用递归，但通常需要使用其他谓词，例如append、maplist或length。它们在特定的Prolog实现中可能会被递归地编写，也可能不会。递归对于遍历列表中所有元素是必要的。如果你只想要第一个元素，可以像这样做：[H|T]=List，它会获取头（第一个）元素H或尾部列表T。 - lurker

Answer 1

你问错问题了 :)

但是说真的：找到列表长度的唯一明智方法是使用内置的length/2。它是如何实现的并不重要--更重要的是它的语义：

?- length([a,b], 2).
true.

?- length([a,b], 4).
false.

?- length([a,b,c], Len).
Len = 3.

?- length(List, 3).
List = [_G937, _G940, _G943].

?- length(List, Len).
List = [],
Len = 0 ;
List = [_G949],
Len = 1 ;
List = [_G949, _G952],
Len = 2 . % and so on

无论如何，这都没有比使用length/2更简单的方式来查找列表的长度、检查列表的长度、创建指定长度的列表或枚举递增长度的列表。

然后：学习Prolog意味着学习如何使用length/2和其他漂亮的声明式内置函数。 重复一个元素N次 将列表分成一些长度的片段 列表中恰好有一对 旋转一个列表

我相信你能想到许多其他使用 length/2 的方法。

- user1812457

---

在许多实现中，“length/2”使用Brent算法来确定长度并检测循环 - 这是极其巧妙的。 - false

Answer 2

这里有一个使用repeat/0谓词的迭代解决方案，具体如下：

getlength(L,N) :-
    retractall(getlength_res(_)),
    assert(getlength_res(0)),
    retractall(getlength_list(_)),
    assert(getlength_list(L)),
    repeat,
        (
            getlength_list([]), !, getlength_res(N)
        ;
            retract(getlength_res(V)), W is V + 1, assert(getlength_res(W)),
            retract(getlength_list([_|T])), assert(getlength_list(T)), fail
        ).

这个解决方案创建和撤回事实“getlength_res/1”和“getlength_list/1”，当遍历列表时，用一个更短的列表替换旧列表，并在每次repeat/0迭代中使旧数字增加一。从某种意义上说，这两个动态维护的事实的行为非常像命令式语言中可分配的变量。

演示。

通常情况下，在Prolog中，迭代的解决方案比递归的解决方案难以阅读。考虑到任何具有类似于命令式编程语言赋值语句效果的东西都与Prolog的设计哲学不符，这应该不足为奇。

- Sergey Kalinichenko

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - lurker

@lurker 不用说，我强烈反对这种解决方案，因为它没有任何优势，执行速度更慢，语句计数增加了7倍（是的，七倍）。感谢您的评论！ - Sergey Kalinichenko

确实。我只是想强调这个问题，因为我不确定OP在Prolog方面的经验水平。有许多可能不太明显的情况，其中列表处理优于使用assert和retract。不过，我确实喜欢这个答案，因为它展示了Prolog的这一方面。 - lurker

不，那只是玩弄文字游戏。 - false

Answer 3

抱歉，我忍不住要尝试这个“挑战”：

Input=[a,b,b,b,b,b,b,b,b,a,b,c,d,f], between(1,inf,K),findall( _,between(1,K,_),FreeList), ( FreeList=Input,!,true).

findall/3正在执行后台递归，代码正在对列表FreeList和Input进行统一，直到它们统一为止。

- re Paul