时间戳

首页 > 解决方案 > prolog中的嵌套列表

list - prolog中的嵌套列表

问题描述

我必须分开这个：

    [[[1,2,3,4]],[[1],[1,3],[1,2,3,4]],[[1,2,3,4]],[[1,2,3,4]]]

在这样的事情

    w1 = [1,2,3,4]
    w2 = [1],[1,3],[1,2,3,4]
    w3 = [1,2,3,4]
    w4 = [1,2,3,4]

有人可以帮助我吗？

标签： listprolog

解决方案

听起来您需要遍历任意深度的嵌套列表（可以说是一棵树），识别它包含的平面列表（例如，一个列表，其中的每个成员本身就是一个列表），然后返回它找到的平面列表。

我们将使用一个辅助谓词，它使用一个差异列表（也称为开放列表或部分列表）。

封闭列表类似于，[a,b]它是数据结构：.( a, .( b, [] ) )或[a,b|[]]，列表以 终止[]。包含两个成员的差异列表（或打开列表）看起来像where是未绑定a的变量。它与 相同。b[a,b|T]T.( a, .( b, T ) )

差异列表的用途是，如果您跟踪它的最后一个未绑定的元素，您可以继续附加到它，然后[]在完成后通过统一最后一个元素来关闭它。

所以...

我们有主谓词本身，extract/2它沿着源列表运行，并在每个谓词上调用帮助器，从而构建平面列表的列表。当该源列表用尽时，结果列表将关闭：

extract( []     , [] ) .
extract( [X|Xs] , Ys ) :- extract(X,Ys,Y1), extract(Xs,Y1).

助手，extract/3并不复杂。它只看它通过了什么。如果那是一个

  • 非列表，它是平的
  • 平面列表，它是平面的
  • 对于任何非平面列表，我们
    • 从它的头部递归地提取扁平的东西，并且
    • 如果有一个非空的尾巴，递归地从中提取扁平的东西。
extract( X         , [X|Ys] , Ys ) :- \+ is_list(X), !.
extract( X         , [X|Ys] , Ys ) :- flat_list(X) , !.
extract( [X]       , Ys     , Y1 ) :- extract(X,Ys,Y1).
extract( [X,X1|Xs] , Ys     , Y2 ) :- extract(X,Ys,Y1), extract([X1|Xs],Y1,Y2) .

最后，我们必须定义什么构成了“平面”列表。这也很简单。如果其成员都不是列表，则为扁平列表：

flat_list( []     ) .
flat_list( [X|_]  ) :- is_list(X), !, fail .
flat_list( [_|Xs] ) :- is_flat(Xs) .

把它们放在一起，你会得到：

extract( []     , [] ) .
extract( [X|Xs] , Ys ) :- extract(X,Ys,Y1), extract(Xs,Y1).

extract( X         , [X|Ys] , Ys ) :- \+ is_list(X), !.
extract( X         , [X|Ys] , Ys ) :- flat_list(X) , !.
extract( [X]       , Ys     , Y1 ) :- extract(X,Ys,Y1), !.
extract( [X|Xs] , Ys     , Y2 ) :- extract(X,Ys,Y1), extract(Xs,Y1,Y2) .

flat_list( []     ) .
flat_list( [X|_]  ) :- is_list(X), !, fail .
flat_list( [_|Xs] ) :- flat_list(Xs) .

你可以在这里摆弄它：https ://swish.swi-prolog.org/p/extract-from-list-of-lists.pl

推荐阅读