Counting number of seen states

Question

I have some code which executes a simple task, counting the number of states reachable from a particular state, would just like some advice on how to improve it.

So far it stores all the states it has seen in seen_states. It's just counting them seems so clunky.

move([Head, Head1|Tail], [N|Tail]):-
    N is Head1 - Head,
    N >= 0.
move([Head|Tail], [Head|Tail1]):-
    move(Tail, Tail1).


:- dynamic counted_states/1.





count_state(S, V):-
    count_state(S,V, V).

count_state([], N,N).
count_state(S, Acc, Acc):-
    findall(X, move(S,X), Succ),
    count_sub_states(Succ, Acc, 0).

count_sub_states([],L,L).
count_sub_states([HeadList|List], Count, Acc):-
    count_node(HeadList,N),
    Acc1 is Acc+N,
    count_sub_states(List, Count, Acc1).

count_node(State, 0):-
    counted_states(State),!.

count_node(State, V):-
    not(counted_states(State)), 
    assert(counted_states(State)),
    count_state(State, V1, V1),
    V is V1 +1.

Answer 1

As a general rule of thumb, you should avoid using the global database for such purposes.

For example, in your case, after the predicate completes, counted_states/1 is still asserted, and will influence later invocations of the predicate.

This certainly is not intended, no?

There is a straight-forward solution for this:

1. First, describe what it means that that a state is reachable from a particular state.
2. Then, use findall/3 to collect all such reachable states into a list of results.
3. On that list, simply use length/2 to obtain the number of reachable states.

This works without modifying the global database in any way.