确定术语的最大深度

Question

如何实现二元谓词，将第一个参数的深度计算为第二个参数。

备注：变量、数、0元数函数符号、0元数谓词符号的深度为0。

项或原子公式的深度是所有子项或子公式的最大深度加 1。

?-depth((p(X,a(q(Y)),c), X).

X=3

我的努力：我实现了 max_list 谓词，但我无法进一步开发我的代码。

Answer 1

我认为这是朝着一个方向发展的。

depth(A,0):-
 \+compound(A).
depth(A,B):-
 compound(A),
 A =.. [_H|T],
 maplist(depth,T,Depths),
 max_list(Depths,Max),
 B is Max +1.

Answer 2

列表实际上只是一个术语，带有一些简化最常见用法的语法糖。所以，我的 depth/2 定义，给定 compound/1, aggregate/3 and arg/3 可用性的 1-liner，答案如下：

?- depth(a(a,[1,2,3],c),X).
X = 4.

?- depth(p(X,a(q(Y)),c), X).
X = 3.

编辑我会很高兴地完成它：填写圆点

depth(T, D) :- compound(T) -> aggregate(max(B), P^A^(..., ...), M), D is M+1 ; D = 0.

edit 显然，填充点没有乐趣:)[=14=]

depth(T, D) :-
  compound(T)
  ->  aggregate(max(B+1), P^A^(arg(P, T, A), depth(A, B)), D)
  ;   D = 0.

Answer 3

这是一个简单明了的方法。它将列表视为平面数据结构（即使在现实中，它们是深度嵌套的 ./2 结构。

depth( T , D ) :- % to compute the depth of an arbitrary term...
  depth(T,0,D)    % - call the worker predicate with the accumulator seeded to zero.
  .

depth( T      , CM , MD ) :- var(T)    , ! , MD is CM+1 . % an unbound term is atomic  : its depth is the current depth + 1 .
depth( T      , CM , MD ) :- atomic(T) , ! , MD is CM+1 . % an atomic term is...atomic : its depth is the current depth + 1 .
depth( [X|Xs] , CD , MD ) :-                              % we're going to treat a list as a flat data structure (it's not really, but conceptually it is)
  findall( D , (member(T,[X|Xs),depth(T,0,D)) , Ds ) ,    % - find the depth of each item in the list
  max(Ds,N) ,                                             % - find the max depth for a list item.
  MD is CD + 1 + N                                        % - the max depth is the current depth + 1 (for the containing list) + the max depth of a list item
  .                                                       %
depth( T , CD , MD ) :-                                   % for other compound terms...
  T \= [_|_] ,                                            % - excluding lists,
  T =.. [_|Args] ,                                        % - decompose it into its functor and a list of arguments
  depth(Args,0,N) ,                                       % - compute the depth of the argument list
  MD is CD + N                                            % - the max depth is the current depth plus the depth of the argument list.
  .                                                       % Easy!

max( [N|Ns] , M ) :- max( Ns , N , M ) . % to compute the maximum value in a list, just call the worker predicate with the accumulator seeded to zero.

max( [] , M , M ) .               % when we hit the end of the list, we know the max depth.
max( [N|Ns] , T , M ) :-          % otherwise,
  ( N > T -> T1 = N ; T1 = T ) ,  % - update the current high water mark
  max(Ns,T1,M)                    % - recurse down.
  .                               % Easy!

确定术语的最大深度

Determine the maximum depth of a term

prolog