CODEWITHSUNDEEP
listprolog
Tyler
Tyler

Reputation: 73

Make a list of numbers found in list in Prolog

I am trying to construct a list in Prolog for every number it has found. For example, findNumber([g,o,o,d,j,0,6],[0,6]), but I can't construct the list with the given code:

isNum(6).
isNum(6).

findNumber([],[]).
findNumber([V|T],[-|TAfter]) :-
  isNum(V),
  findNumber(T,TAfter).
findNumber([H|T],[H|TAfter]) :-
  not(isNum(H)),
  findNumber(T,TAfter).

Please help... I am in quite the pickle. Thank you!

Upvotes: 1

Views: 79

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

There are a few problems with your code:

You use a predicate isNum you define yourself, but only 6 seems to be a number. 0 is not a number? So correct this to:

isNum(0).
isNum(6).

or use 's builtin predicate number/1. (mind using number/1 slightly modifies the semantics since number/1 does not instantiate the given variable; as long as you use the predicate in only one direction - list to sublist - and do not use uninstantiated variables, that's fine however).

Secondly the predicate itself. First of all, you somehow swapped the cases: here it will add the H to the resulting list in the third clause (where H is not a number). Furthermore in the second clause you add a dash (-) to the list (this does not seem to be the desired behavior). A better predicate is therefore probably:

findNumber([],[]).
findNumber([H|T],[H|TAfter]) :-
  number(H),
  findNumber(T,TAfter).
findNumber([H|T],TAfter):-
  not(number(H)),
  findNumber(T,TAfter).

Or you can make the predicate more compact (and a bit faster) by using a cut (!):

findNumber([],[]).
findNumber([H|T],[H|TAfter]) :-
  number(H),
  !,
  findNumber(T,TAfter).
findNumber([_|T],TAfter):-
  findNumber(T,TAfter).

Demo (swipl):

?- findNumber([g,o,o,d,j,0,6],X).
X = [0, 6].

?- findNumber([g,o,0,o,d,j,6],X).
X = [0, 6].

Recursive list structure

In case you want to do this recursively, you could do this by extending the predicate to a three arguments version findNumber/3. First we map the version with two arguments findNumber/2 on findNumber/3:

findNumber(A,B) :-
    findNumber(A,B,[]).

(the previously defined predicate should be removed).

Next we define the following clauses:

findNumber([],TT,TT).
findNumber([H|T],[H|TA],TT) :-
  number(H),
  !,
  findNumber(T,TA,TT).
findNumber([H|T],TA,TT):-
  findNumber(H,TA,TL),
  !,
  findNumber(T,TL,TT).
findNumber([_|T],TA,TT) :-
    findNumber(T,TA,TT).

This works with a technique called difference lists which will be rather memory and cpu efficient. Furthermore the call stack will only grow in the number of levels of the given list.

The third argument specifies which value should be put at the tail of the list. Evidently the base case is that the list should end with a [] (that's what we do with the findNumber/2 to findNumber/3 conversion.

There is a special case in which Prolog will wonder whether there is a sublist (the second clause), it will call findNumber/3 with the head of the list findNumber(H,TA,TL) and will generate a list TA leaving the tail TL open. The new tail TL will than later be filled with a call findNumber(H,TL,TT) (we thus will put our original tail TT at the real back, but need an intermediate tail TL).

Demo (swipl):

?- findNumber([[g,0,0,d],[n,4,s,t,y]],K).
K = [0, 0, 4].

?- findNumber([[g,0,0,d],[n,4,[s,3,9],t,y]],K).
K = [0, 0, 4, 3, 9].

Upvotes: 2

Related Questions