CODEWITHSUNDEEP
prolog
jewelltaylor9430
jewelltaylor9430

Reputation: 119

Prolog - building list of terms recursively only including certain terms

I am trying to build a list of states recursively only including states that have some sort of condition. I am trying to use a conditional in order to do so but the list is not accumulating through recursive calls.

%Base case
epsilon_closure_helper(State, [], States) :-
  States = [State].

%Recursive Case
epsilon_closure_helper(State, Transitions, States) :-
  Transitions = [Head|Tail],
  epsilon_closure_helper(State, Tail, States1),
  Head = next(A, B, Symbol),
  %If test_state true: append State B to States list else append empty list
  test_state(State, A, Symbol) -> append(States1, [B], States) ; 
  append(States1, [], States).

  test_state(TargetState, State, Symbol) :-
    State = TargetState,
    Symbol = epsilon.

   %Example list of Transitions (next). Transitions contain a From state, a To 
    state and Symbol
  [next(state(0, not_accepting), state(1, not_accepting), epsilon), 
   next(state(1, not_accepting), state(3, not_accepting), epsilon)]

Even if I change the else condition to States = States1 it doesn't work. All I want is the States variable to have all the State terms that have the certain condition. Any advice how I can do so or where I am going wrong? Any help would be much appreciated!! :)

Edit: So the logic is as follows. If State A from a transition in the transition list matches the target which is supplied in the State variable in the epsilon_closure_helper predicate and the transition Symbol is epsilon I want to add State B from the same transition to the States list. Transitions are represented as: next(FromState, ToState, Symbol) States are represented as: State(Number, Accepting) The accepting variable doesn't matter for this solution.

Upvotes: 1

Views: 124

Answers (1)

Guy Coder
Guy Coder

Reputation: 24976

Since you did not give any example input and output and some of the clauses/facts are missing, e.g. test_state/3 this is a comparable solution.

When working with threaded variables, i.e. State, the customary way to do it is put them at the end of the arguments:

epsilon_closure_list([H|T],State0,State)

Next with threaded variables the input variable has 0 appended to it and the result variable has no number appended to it. The remaining variables have an incrementing number appended to them.

In your code the tail is processed before each item, which is fine, but when the recursive call is at the end of the clause it is know as tail-recursion. When tail-recursion is used, many compilers can optimize the code. This answer uses tail-recursion.

Your code also uses =/2 which can be factored out to simplify the code, but when learning or writing some new code I too often use it until I have the code working. This answer will have all of the =/2 factored out.

The use of append/3 can probably be factored out, and in most cases can, but since you did not give enough example code this answer leaves append/3 in the answer.

Complete code

epsilon_closure_list([H|T],State0,State) :-
    (
        valid(H)
    ->
        append(State0,[H],State1)
    ;
        append(State0,[],State1)
    ),
    epsilon_closure_list(T,State1,State).
epsilon_closure_list([],State,State).

valid(a).
valid(c).
valid(d).

Test cases

:- begin_tests(epsilon_closure).

epsilon_closure_test_case([],[]).
epsilon_closure_test_case([b],[]).
epsilon_closure_test_case([b,e],[]).
epsilon_closure_test_case([a],[a]).
epsilon_closure_test_case([a,b],[a]).
epsilon_closure_test_case([a,b,c],[a,c]).

test(1,[forall(epsilon_closure_test_case(Input,Expected_result))]) :-
    epsilon_closure_list(Input,[],State),
    assertion(State == Expected_result ).

:- end_tests(epsilon_closure).

Example run

?- run_tests.
% PL-Unit: epsilon_closure ...... done
% All 6 tests passed
true.

Upvotes: 1

Related Questions