时间戳

首页 > 解决方案 > 如何通过Prolog中的分隔符将列表拆分为列表列表

list - 如何通过Prolog中的分隔符将列表拆分为列表列表

问题描述

我知道这应该很简单，但我不知道。基本上给定一个列表，例如[a,b,c,' ',d,' ',e,f]，该列表应拆分为列表列表。在这个例子中，输出应该是[[a,b,c],[d],[e,f]]

目前我做了这样的事情：

helper([], _, _).
helper([Elem|Rest], Sub, Result):- 
    (Elem == ',' -> 
        append(Result, Sub, NewResult),
        helper(Rest, [], NewResult)
    ;   
        append(Sub, [Elem], New),
        helper(Rest, New, Result)
    ).

任何人都可以提出一些想法吗？

标签： listsplitprologdelimiter

解决方案

让我们从编写一个flatten/2谓词开始，它将列表列表转换为扁平列表，前面的“列表中断”由~（而不是~，但只是因为它更容易在源中查找）表示

% flatten(ListOfLists,ListWithCommas)

flatten([Sublist1|[Sublist2|More]],MergedList) :-
   !, % not needed, but we want to tell Prolog to not 
      % look for more solutions in the next two clauses
      % because there aren't any
   append(Sublist1,[~],Part1),
   flatten([Sublist2|More],Part2),    
   append(Part1,Part2,MergedList).
flatten([Sublist],Sublist).
flatten([],[]).

% - - 8< - - - - - - - 8< - - - - - - - 8< - - - - - - - 
 
:- begin_tests(flatten).

test(a1) :- 
   flatten([],Result),
   assertion(Result == []).
   
test(a2) :- 
   flatten([[a,b,c]],Result),
   assertion(Result == [a,b,c]).

test(a3) :- 
   flatten([[]],Result),
   assertion(Result == []).

test(a4) :- 
   flatten([[a,b,c],[d,e,f]],Result),
   assertion(Result == [a,b,c,~,d,e,f]).

test(a5) :- 
   flatten([[a,b,c],[d,e,f],[g,h,i]],Result),
   assertion(Result == [a,b,c,~,d,e,f,~,g,h,i]).

test(a6) :- 
   flatten([[a,b,c],[],[g,h,i]],Result),
   assertion(Result == [a,b,c,~,~,g,h,i]).
   
:- end_tests(flatten).

这工作正常。如果我们运行测试：

?- run_tests.
% PL-Unit: flatten ...... done
true.

我们不能神奇地“反转”上述行为（虽然这很好）：

?- flatten(ListOfLists,[a,b,c,~,d,e,f]).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.7Gb, global: 0.2Gb, trail: 60.4Mb

所以我们必须编写一个heighten/2我们知道内置谓词的限制并且知道数据流的代码：

heighten([],[]).  
heighten([Sublist],Sublist) :- 
   \+ member(~,Sublist),
   !.                                % Not needed, but tell Prolog to not look
                                     % for another solution via the next clause because there isn't one
heighten([Sublist1|[Sublist2|More]],MergedList) :-
   append(Part1,Part2,MergedList),   % Propose how to split MergedList into Part1 and Part2   
   append(Sublist1,[~],Part1),       % We demand that Part1 end with ~, which also gives us Sublist1
   \+ member(~,Sublist1),            % And ~ is itself not member of Sublist1
   !,                                % Not needed, but tell Prolog to not backtrack
                                     % past this point, because there are no more solutions there
   heighten([Sublist2|More],Part2).
   
% - - 8< - - - - - - - 8< - - - - - - - 8< - - - - - - - 
   
:- begin_tests(heighten).

test(b1) :- 
   bagof(Prior,heighten(Prior,[]),Bag),
   assertion(Bag == [ [] ,  [[]]] ). % clearly this mapping is not bijective
   
test(b2) :- 
   heighten(Prior,[a,b,c]),
   assertion(Prior == [[a,b,c]]).

test(b4) :- 
   heighten(Prior,[a,b,c,~,d,e,f]),
   assertion(Prior == [[a,b,c],[d,e,f]]).

test(b5) :- 
   heighten(Prior,[a,b,c,~,d,e,f,~,g,h,i]),
   assertion(Prior == [[a,b,c],[d,e,f],[g,h,i]]).

test(b6) :- 
   heighten(Prior,[a,b,c,~,~,g,h,i]),
   assertion(Prior == [[a,b,c],[],[g,h,i]]).
   
:- end_tests(heighten).

这正是我们所需要的。我真的很惊讶它的效果如此之好，我并没有完全追踪我脑海中的行为：

?- run_tests.
% PL-Unit: flatten ...... done
% PL-Unit: heighten ..... done
% All 11 tests passed
true.

它不如“搜索”的命令式版本那么有效：append(Part1,Part2,MergedList)必须提出解决方案直到匹配。

推荐阅读