使用手动列表迭代与通过失败递归的优缺点是什么 [英] What are the pros and cons of using manual list iteration vs recursion through fail

问题描述

我一直遇到这个问题，但我永远不知道用哪种方式来攻击它.以下是处理一些季节事实的两种方法.

I come up against this all the time, and I'm never sure which way to attack it. Below are two methods for processing some season facts.

我想弄清楚是使用方法 1 还是方法 2，以及每种方法的优缺点是什么，尤其是大量事实.

What I'm trying to work out is whether to use method 1 or 2, and what are the pros and cons of each, especially large amounts of facts.

methodone 似乎很浪费，因为事实是可用的，为什么还要构建一个列表(尤其是一个大列表).如果列表足够大，这也必须具有内存影响吗?而且它没有利用 Prolog 的自然回溯功能.

methodone seems wasteful since the facts are available, why bother building a list of them (especially a large list). This must have memory implications too if the list is large enough ? And it doesn't take advantage of Prolog's natural backtracking feature.

methodtwo 利用回溯为我做递归，我猜想内存效率会更高，但是这样做通常是好的编程习惯吗?可以说是更难看，可能还有其他副作用吗?

methodtwo takes advantage of backtracking to do the recursion for me, and I would guess would be much more memory efficient, but is it good programming practice generally to do this? It's arguably uglier to follow, and might there be any other side effects?

我看到的一个问题是，每次调用 fail 时，我们都无法将任何内容传递回调用谓词，例如.如果是 methodtwo(SeasonResults)，因为我们故意不断地使谓词失败.所以 methodtwo 需要断言事实来存储状态.

One problem I can see is that each time fail is called, we lose the ability to pass anything back to the calling predicate, eg. if it was methodtwo(SeasonResults), since we continually fail the predicate on purpose. So methodtwo would need to assert facts to store state.

大概(?)方法 2 会更快，因为它没有(大)列表处理要做?

Presumably(?) method 2 would be faster as it has no (large) list processing to do?

我可以想象，如果我有一个列表，那么 methodone 将是我要走的路..还是总是这样?在任何条件下使用 methodone 将列表断言为事实然后使用方法二处理它们是否有意义?完全疯了?

I could imagine that if I had a list, then methodone would be the way to go.. or is that always true? Might it make sense in any conditions to assert the list to facts using methodone then process them using method two? Complete madness?

但话说回来，我读到断言事实是一项非常昂贵"的业务，因此即使对于大型列表，列表处理也可能是要走的路?

But then again, I read that asserting facts is a very 'expensive' business, so list handling might be the way to go, even for large lists?

有什么想法吗?或者有时使用一种而不是另一种更好，这取决于(什么)情况?例如.对于内存优化，使用方法 2，包括断言事实，对于速度使用方法 1?

Any thoughts? Or is it sometimes better to use one and not the other, depending on (what) situation? eg. for memory optimisation, use method 2, including asserting facts and, for speed use method 1?

season(spring).
season(summer).
season(autumn).
season(winter).

 % Season handling
showseason(Season) :-
    atom_length(Season, LenSeason),
    write('Season Length is '), write(LenSeason), nl.

% -------------------------------------------------------------
% Method 1 - Findall facts/iterate through the list and process each
%--------------------------------------------------------------
% Iterate manually through a season list
lenseason([]).
lenseason([Season|MoreSeasons]) :-
    showseason(Season),
    lenseason(MoreSeasons).


% Findall to build a list then iterate until all done
methodone :-
    findall(Season, season(Season), AllSeasons),
    lenseason(AllSeasons),
    write('Done').

% -------------------------------------------------------------
% Method 2 - Use fail to force recursion
%--------------------------------------------------------------
methodtwo :-
    % Get one season and show it
    season(Season),
    showseason(Season),

    % Force prolog to backtrack to find another season
    fail.

% No more seasons, we have finished
methodtwo :-
    write('Done').

推荐答案

方法一似乎很浪费，因为事实是可用的，为什么还要构建一个列表(尤其是一个大列表).如果列表足够大，这也必须涉及内存?

method one seems wasteful since the facts are available, why bother building a list of them (especially a large list). This must have memory implications too if the list is large enough ?

是的，方法 1 需要 Θ(n) 内存.它的主要好处是它是声明性的，即它具有直接的逻辑含义.

Yes, method 1 takes Θ(n) memory. It's primary benefit is that it is declarative, i.e. it has a straightforward logical meaning.

方法 2，Prolog 程序员称之为故障驱动循环"，占用恒定内存，是过程性的，并且在您进行过程性(超逻辑)事情时可能是首选；即，在 I/O 代码中可以使用它.

Method 2, the "failure-driven loop" as Prolog programmers call it, takes constant memory, is procedural and may be preferred when you're doing procedural (extra-logical) things anyway; i.e., in I/O code it's ok to use it.

请注意，SWI-Prolog 有第三种编写此循环的方法:

Note that SWI-Prolog has a third way of writing this loop:

forall(season(S), showseason(S)).

这仅在 showseason 对 season(S) 的每个绑定都成功时才有效.

This only works if showseason succeeds for each binding of season(S).

这篇关于使用手动列表迭代与通过失败递归的优缺点是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！