CODEWITHSUNDEEP
prolog
Bobby
Bobby

Reputation: 496

How to count duplicate prolog


I have implemented this tree (insertion), but i want to keep track of duplicate, how do i do this. 

insert2(nil, nil, nil).
insert2(Info, nil, t((Info,1), nil, nil)).

insert2(Info , t((RootInfo,_), Left, Right),
          t((RootInfo,_), LeftPlus, Right)) :-
                      Info< RootInfo,
                      insert2(Info, Left, LeftPlus).


insert2(Info , t((RootInfo,count), Left, Right),t((RootInfo,count+1), Left, Right)) :-
                          Info= RootInfo.

insert2(Info, t((RootInfo,_), Left, Right),
                   t((RootInfo,_), Left, RightPlus)) :-
     RootInfo< Info,
     insert2(Info, Right, RightPlus).

To be a bit more clear this is what i mean 

-? T = t((20,3),t((10,1),nil,nil),t((30,2),nil,nil)),
insertT(10,T,NT).
NT = t((20,3), t((10,2),nil,nil),t((30,2),nil,nil)).

Since i have already inserted 10, the tree will just increase the counter instead of adding a duplicate value. Thanks

Upvotes: 0

Views: 95

Answers (1)

lurker
lurker

Reputation: 58254

Since you're so very close, I'll tidy it up. :)

The only real issues remaining with what you have are:

  1. You have an atom instead of variable for Count in one of the clauses
  2. You're attempting to add in line with Prolog, which doesn't really work that way. If you try to use Count + 1 as an argument, it will be read as the term, +(Count, 1) unless it gets passed into a predicate which can evaluate it (like is/2 or an arithmetic comparison).
  3. You don't need the first clause, insert2(nil, nil, nil). Or at least if you plan to account for inserting nil, I would suppose that the result should be the original tree, so it would be, insert2(nil, Tree, Tree) instead. You wouldn't nullify the tree just because you were attempting to insert nil. You would leave the tree alone.

Taking those factors into account:

% (3) Inserting nil into a Tree yields the same Tree
insert(nil, Tree, Tree).

% If you insert into an empty tree, the result is a tree with
%   a single node consisting of your new info
insert(Info, nil, t((Info, 1), nil, nil)).

% (1) If you insert into a tree and the node at the top matches your
%   Info, then you only increment the count of the top node
insert(Info, t((Info, C), L, R), t((Info, Cx), L, R)) :-
    Cx is C + 1.  % (2) `is/2` will evaluate; you can't do this "in-line"

% If you insert Info which is smaller than the top node value of
%   a non-nil tree, then you insert the Info into the left branch
insert(Info, t((I, C), L, R), t((I, C), Lx, R)) :-
    Info < I,
    insert(Info, L, Lx).

% If you insert Info which is greater than the top node value of
%   a non-nil tree, then you insert the Info into the right branch
insert(Info, t((I, C), L, R), t((I, C), L, Rx)) :-
    Info > I,
    insert(Info, R, Rx).

Upvotes: 1

Related Questions