代码之家  ›  专栏  ›  技术社区  ›  flawr

统计列表中的出现次数

  •  1
  • flawr  · 技术社区  · 9 年前

    我正在尝试创建一个规则来计算给定列表中某个元素的出现次数,但迄今为止,我尝试的方法似乎没有达到预期效果:

    第一个 论点 这里应该是列表,第二个是我们要查找的元素,最后一个是出现的次数:

    %empty list should always return 0 occurences
    count([],E,0) :- true.
    
    %if our head is what we are looking for, count
    count([E|T],E,N) :- count(T,E,N-1).
    
    %otherwise, do not count
    count([H|T],E,N) :- H \== E, count(T,E,N).
    

    在这里 H T 这个 给定列表的。

    基本情况,例如。 count([],1,N). 收益 N = 0 正如预期的那样,但一旦列表非空,我们总是得到 false. :

    ?- count([1],1,N).
    false.
    ?- count([1,2,1,3],1,N).
    false.
    

    有人能指出我做错了什么吗?

    更新:

    将第二行替换为

    count([E|T],E,N+1) :- count(T,E,N).
    

    但我就是不明白为什么这与我的第一个想法不一样。

    然后我们得到

    ?- count([1,2,1,3],1,N).
    N = 0+1+1 
    

    这是正确的。

    2 回复  |  直到 4 年前
        1
  •  4
  •   lurker    9 年前

    评估与统一

    在Prolog中 =/2 是一个 合一 操作人员它不会将一个术语作为一个表达式来计算,即使该术语可能表示某种数值可计算的内容。同样,当您使用 count([E|T], E, N+1) ,序言 不会 评估术语 N+1 对Prolog来说,这只是另一个术语,内部表示为 +(N, 1) .

    要将术语解释为数值表达式并进行计算,您需要使用特定的Prolog运算符。正如@SQB所指出的,其中之一是 is/2 :

    N = 1, N1 is N + 1.
    

    这将导致 N1 = 2 然而,这:

    N = 1, N1 = N + 1.
    

    将导致: N1 = 1 + 1 (或同等标准, N1 = +(1, 1) ).

    Prolog中还有数字比较运算符,也可以计算表达式。这些是 =:=/2 , >/2 , >=/2 , </2 =</2 。因此,您将看到以下内容:

    1 + 2 =:= 3.
    

    将产生“true”,因为 =:=/2 专门用于比较可计算数值表达式的相等性。然而:

    1 + 2 = 3.
    

    将产生“错误”,因为术语 +(1,2) 与术语不匹配(或者更准确地说,不能与术语统一) 3 .

    啊!参数未充分实例化!

    我看到过不少关于SO的帖子,其中提到了一个错误,即它们的参数“没有充分实例化”。其中许多是在使用 是/2 如上所述, 是/2 将在第二个参数中计算表达式,然后将结果与第一个参数统一。第二个参数 必须是完全可评估的 (表达式中涉及的所有变量都必须用数值实例化),否则会出现错误。同样,当使用表达式比较时,两个参数中的所有变量都必须完全实例化。因此,如果 X 是未绑定的变量,以下操作将产生“参数未充分实例化”错误:

    9 is X * 3.       % Will NOT yield X = 3, but will give an error
    Y + 2 =:= X * 2.  % Error if either X or Y are not instantiated
    Y = 1, X = 2, Y + 2 =:= X * 2.  % Yields "false" (fails) since 3 is not equal to 4
    Y = 1, X = 2, Y + 2 < X * 2.    % Yields "true" (succeeds) since 3 is less than 4
    Y = 1, X = 2, X + 1 = Y + 2.    % Yields "false" since +(2,1) doesn't unify with +(1,2)
    

    在表达式上执行约束逻辑时,要使用的工具是CLP(FD)库。因此:

    X * 3 #= 6.
    

    将屈服, X = 2 .

        2
  •  1
  •   SQB    9 年前

    问题是 N+1 (或 N-1 )未评估,正如您的第二个(工作)示例所示。

    % empty list has 0 occurrences
    count([], _, 0).
    
    % if our head is what we are looking for, count
    count([E|T], E, N) :-
        N_1 is N - 1,         % this is the important one
        count(T, E, N_1).
    
    % otherwise, do not count
    count([H|T], E, N) :-
        H \== E,
        count(T, E, N).
    

    is 事实上 评估 方程式,而不是 统一 这个 N 在下次通话中 N-1号机组 这就是为什么在第二个例子中 N=0+1+1 而不是 N=2 .

    推荐文章