使用手动列表迭代与失败递归的优缺点是什么 [英] 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屋！