Advanced List handling

Discussions related to Visual Prolog
User avatar
Thomas Linder Puls
VIP Member
Posts: 1635
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 7 Mar 2014 9:43

First of all I think the intension was different. Iterate (from front) until you encounter an element that fulfill a certain requirement, skip that element? and the rest. So if no element fullfils the requirement you will iterate to the end of the list.

before_nd does nothing if the element is not in the list (i.e. something quite different).

Secondly, you predicate is highly inefficient. Running member on a list is O(N) (i.e. proportional to the number of elements in the list). At each of up to N steps you have an operation O(N) operation. Meaning that you algorithm is O(N*N).

The before_nd functionality that you have implemented can easily be acomplished by an O(N) predicate.

Exersize: Create an O(N) implementation of before_nd.

By the way I don't think any of these predicates are adequade for the list class. I think they lack clarity (it is not obvious what they do) and secondly the usability seem a little limited. Furthermore, the number of variations that such predicates could have is endless, and if there are too many variants it becomes very difficult to remember which one does what (and thus to find the one that you need in a certain context).
Regards Thomas Linder Puls
PDC

Harrison Pratt
VIP Member
Posts: 287
Joined: 5 Nov 2000 0:01

Re:

Unread post by Harrison Pratt » 7 Mar 2014 12:53

Thomas,
You are, of course, right about inefficient code. In practice I never recurse into member/2 if it can be avoided.

I believe that George's stated intent was to have processing terminate when a specified string was encountered and not process strings after that string. What to do when there is no terminating string was not specified. My assumption was that the terminating string was required.

I agree that this isn't a candidate for a class predicate. This is the first time I've encountered a need for a predicate that does this and at this time I can't imagine where I would use it.

I'll do the exercise.

Thanks for your comments.

Paul Cerkez
VIP Member
Posts: 202
Joined: 6 Mar 2000 0:01

Unread post by Paul Cerkez » 7 Mar 2014 13:27

Back inthe 5.x and 6.x days what I would do is have 2 predicates.

the first was simply a list iterator. the second contained clauses to execute an action (or not).

Yes the entrie list will be gone through but there will no action on the ones you don't care about. it typically pretty fast (maybe not the most effcient).

In my case, the value I would be looking for typically appeared more than once in the list so this allowed me to every instance of it.

very roughly:

Code: Select all

predciate   iterate_list(string*). clauses    iterate_List([]).    iterate_list([H|L]):-       doAction(H),       iterate_List(l).   predicates    doAction(string). clauses    doAction(S):-  % the specific value I want to act on  you can have multiple clauses here, one for each string you wish to act on.          & do whatever you need to    doAction(_).  % ignore all others      
AI Rules!
P.

Harrison Pratt
VIP Member
Posts: 287
Joined: 5 Nov 2000 0:01

Re:

Unread post by Harrison Pratt » 7 Mar 2014 14:01

Paul Cerkez wrote:Back inthe 5.x and 6.x days what I would do is have 2 predicates.

the first was simply a list iterator. the second contained clauses to execute an action (or not).
That's what I do in 5.2, also. I try to avoid nondeterminism for bulky processes to avoid the dreaded GStack overflow condition.

Below are my answers to Thomas' exercise question (VIP 5.2 syntax). This would seem to fit George's query about a way to handle certain lists. It would seem better to use list filter clauses like these to extract the members of interest and then process that filtered list, rather than using the filters as a nondeterministic test in a loop, for example.

Code: Select all

PREDICATES nondeterm memb_preceding_nd( SLIST, STRING, STRING ) -(i,i,o)   nondeterm memb_except_nd( SLIST, STRING, STRING ) -(i,i,o) CLAUSES %-- return any member preceding, but not after the Stop string memb_preceding_nd( [H,Stop|_], Stop, H ):- !.    % normal terminal condition memb_preceding_nd( [Stop|_], Stop, _ ):- !, fail. % FAIL if no strings precede Stop memb_preceding_nd( [H|_], _, H ).                     % interim valid condition memb_preceding_nd( [_|T], Stop, S ):-               % recurse    memb_preceding_nd( T, Stop, S ).   %-- return all members except the Ignore string memb_except_nd( [H|_],Ignore, H ):- H <> Ignore. memb_except_nd( [_|T], Ignore, S ):-    memb_except_nd( T,Ignore,S ).
Thanks for the nudge in a better direction, Thomas! :D

User avatar
George
VIP Member
Posts: 313
Joined: 19 Sep 2011 8:54

Unread post by George » 7 Mar 2014 14:53

Dear Harrison Pratt,

My intention is to make use of 7.4 version built in predicate - And try to minimize the code as much as possible...

Ex :

Code: Select all

class predicates     testForAllLoop : (). clauses     testForAllLoop():-         MyList = ["A", "B", "C", "D", "E", "F", "G"],         list::forAll(MyList, {(Head):-             if Head = "D" then                 !  %Need to end the loop here - please suggest me..             end if             }).
We've a Built in predicate " list::forAll/.." to loop through all the element in the list. and do what ever we need

But, the "list::forAll/.." built in entry doesn't have a option to terminate the loop in middle of the processing which we can do it on the backtracking concepts which you have clearly given..

Code: Select all

PREDICATES nondeterm memb_preceding_nd( SLIST, STRING, STRING ) -(i,i,o)     nondeterm memb_except_nd( SLIST, STRING, STRING ) -(i,i,o) CLAUSES %-- return any member preceding, but not after the Stop string memb_preceding_nd( [H,Stop|_], Stop, H ):- !.    % normal terminal condition memb_preceding_nd( [Stop|_], Stop, _ ):- !, fail. % FAIL if no strings precede Stop memb_preceding_nd( [H|_], _, H ).                     % interim valid condition memb_preceding_nd( [_|T], Stop, S ):-               % recurse    memb_preceding_nd( T, Stop, S ).   %-- return all members except the Ignore string memb_except_nd( [H|_],Ignore, H ):- H <> Ignore. memb_except_nd( [_|T], Ignore, S ):-    memb_except_nd( T,Ignore,S ).
Can you do the above logic through "list::forAll/.." built in entry in 7.4 version ? Note : You should never use separate predicate to do this - everything should be handled in "forAll/.." predicate..


Mr. Thomas Linder Puls, told that it is not possible

The following is his comments:
Why use a predicate against its obvious intention? I suggest that you don't use forAll when you don't want to do it for all elements.

I guess - May be in future, PDC will bring a concept to termination condition inside forAll/.. predicate
Kind Regards,
George Ananth. S | Prolog Developer
georgeananth.prolog@gmail.com
+91 9791499282

Post Reply