Prolog - List of sequence from f0 to fN

Question

The question require me to write a predicate seqList(N, L), which is satisfied when L is the list [f0, . . . , fN].

Where the fN = fN-1 + fN-2 + fN-3

My code is to compare the head of a list given, and will return true or false when compared.

seqList(_,[]).
seqList(N,[H|T]) :-
    N1 is N - 1,
    seq(N,H),
    seqList(N1,T).

However, it only valid when the value is reversed, e.g. seqList(3,[1,1,0,0]) will return true, but the list should return me true for seqList(3,[0,0,1,1]). Is there any way for me to reverse the list and verifies it correctly?

the definition of your predicate is unclear to me. Plus, you should add your seq predicate, here you don't have all the code. — m09, Aug 17 '12 at 07:07
are you banned to use [reverse](http://www.swi-prolog.org/pldoc/doc_for?object=reverse/2)/2? — CapelliC, Aug 17 '12 at 08:25
im sry for that unclear @Mog any way, im currently not in home, will upload all those details to you in no time. Well, i can use anything i can as long as i can did the job, anyway using the reverse will cause my list to keep flipping each time it recurse going down to the base case.@chac — Danny Teo, Aug 18 '12 at 13:18

score 3 · Answer 1 · edited May 23 '17 at 10:24

It seems that you want to generate N elements of a sequence f such that f(N) = f(N-1) + f(N-2) + f(N-3) where f(X) is the X-th element of the sequence list, 0-based. The three starting elements must be pre-set as part of the specification as well. You seem to be starting with [0,0,1, ...].

Using the approach from Lazy lists in Prolog?:

seqList(N,L):- N >= 3, !,
   L=[0,0,1|X], N3 is N-3, take(N3, seq(0,0,1), X-[], _).

next( seq(A,B,C), D, seq(B,C,D) ):- D is A+B+C.

Now all these functions can be fused and inlined, to arrive at one recursive definition.

But you can do it directly. You just need to write down the question, to get the solution back.

question(N,L):-

Since you start with 0,0,1, ... write it down:

    L = [0, 0, 1 | X],

since the three elements are given, we only need to find out N-3 more. Write it down:

    N3 is N-3,

you've now reduced the problem somewhat. You now need to find N-3 elements and put them into the X list. Use a worker predicate for that. It also must know the three preceding numbers at each step:

    worker( N3, 0, 0, 1, X).

So just write down what the worker must know:

worker(N, A, B, C, X):-

if N is 0, we must stop. X then is an empty list. Write it down.

    N = 0, X = [] .

Add another clause, for when N is greater than 0.

worker(N, A, B, C, X):-
    N > 0,

We know that the next element is the sum of the three preceding numbers. Write that down.

    D is A + B + C,

the next element in the list is the top element of our argument list (the last parameter). Write it down:

    X = [D | X2 ],

now there are one less elements to add. Write it down:

    N2 is N - 1,

To find the rest of the list, the three last numbers are B, C, and D. Then the rest is found by worker in exactly the same way:

    worker( N2, B, C, D, X2).

That's it. The question predicate is your solution. Rename it to your liking.

Prolog - List of sequence from f0 to fN

1 Answers1