开发者

Prolog - How this program work

开发者 https://www.devze.com 2023-03-08 21:03 出处:网络
I have this program written in prolog language. The problem is that i cant understand how it works. even_number([],[]).

I have this program written in prolog language. The problem is that i cant understand how it works.

even_number([],[]).
even_number([H|T],S):-even_number(T,W),Z is H mod 2,Z==0,S=[H|W].
even_number([_|T],S):-even_number(T,S).

All it does is to extract the even numbers from a list a开发者_开发技巧nd store it to another list. I know that it works using recursion but i cant understand the steps that are made during execution. Can anyone explain?


The program consists of three rules that are applied as a group. They work together basically as if ... else if ... else if ... [else fail].

The first rule is: the even numbers in an empty list is the empty list. This is easy enough.

The second rule is applied if the first rule fails (i.e., the first argument isn't the empty list). This is a bit more complicated, but basically says to include the first element of the list if it is even. The logic breaks down as follows. The even numbers in a list that starts with H and has a tail of T is S if all the terms on the right are true: that the even numbers in T is some list W; that Z is the remainder after dividing H by 2; that Z is zero; and that S is H followed by W (whatever W turned out to be). (Note that this rule would be more efficient if the first term was moved to after the test Z==0.)

If that rule fails (i.e., H is odd), then the last rule is applied: the even numbers in the list are the even numbers in the tail of the list.


It's written rather poorly. It might be easier to understand if you refactor it a bit and make it tail recursive:

even_numbers( X , R ) :-
  even_numbers( X , [] , T ) ,
  reverse( T , R ).

even_numbers( [] , T , T ).
even_numbers( [X|Xs] , T , R ) :-
  Z is X mod 2 ,
  Z == 0 ,
  ! ,
  even_numbers( Xs , [X|T] , R ).
even_numbers( [_|Xs] , T , R ) :-
  even_numbers( Xs , T , R ).

The first predicate, even_numbers/2 predicate is the public wrapper. It invokes the private helper, even_numbers/3, which hands back the list of even numbers in reverse order. It reverses that and tries to unify it with the result passed in the wrapper. The helper method does this:

  • if the source list is empty: unify the accumulator (T) with the result.
  • if the source list is not empty, and the head of the list (X) is even,
    • recurse down on the tail of the list (Xs), pushing X onto the accumulator.
  • if the source list is not empty, and the head of the list (X) is odd,
    • recurse down on the tail of the list (Xs) without modifying the accumulator.

But as noted by @André Paramés, work through it in the debugger and it will become clear what's going on.

0

精彩评论

暂无评论...
验证码 换一张
取 消