CODEWITHSUNDEEP
listrecursionprolog
Tom Stock
Tom Stock

Reputation: 1290

Output of recursive predicate

The goal of the following predicate is to select the first N items of a list. This should be assigned to the output variable, this is not the case however.

firstx(N, [H|T], L) :-
    (
        length(L, Le), Le < N ->
        append(L, [H], O),
        firstx(N, T, O)
    ;
        write(L)
    ).

This is the output of the above predicate

?- firstx(2, [1,2,3,4,5], X).
[1,2],
X = [].

This is what is should be

?- firstx(2, [1,2,3,4,5], X).
[1,2],
X = [1,2].

As shown the last variable is not correctly assigned. Do you have any suggestions at how it should be programmed? Thanks in advance!

Upvotes: 0

Views: 67

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

I'm kind of mystified by the code you wrote. I don't see a base case for your recursion in firstx(N, T, O). N is never reduced and though you peel items off of the list in the second position, you have no case for when that list is empty. Your usage of append/3 appears to be in an attempt to put items on the end of the result list, but you're also constructing L. Ultimately, I think your problem is probably related to the fact that you are passing a new variable for the third argument down to the recursive call (which will then write it out, eventually) but you are not returning O, you are returning L. I'm guessing this doesn't work if you replace L with O because the variable must be uninstantiated when you start your query but you instantiate it in the recursive call.

I'm not really sure what you're trying to do with this code. I see two clear ways to implement this: a recursive predicate, or using append/3, and I see elements of both in your solution. So let me share both of the approaches I see with you.

The recursive method would look like this:

firstx(0, _, []).
firstx(N1, [H|T], [H|R]) :- 
    succ(N0, N1), 
    firstx(N0, T, R).

In this solution, we take items one-by-one from the head of the list into the result. Using succ/2 is a good habit to get into, because unlike N0 is N1 - 1 it will actually work in both directions. This is sort of where I think you're heading when I see [H|T] in the head of your clause, but again, I find it suspicious that you're not building L in a similar way and you're not reducing N in your recursive call.

The append/3 method would look like this:

firstx(N, L, FirstN) :- 
    length(FirstN, N),
    append(FirstN, _, L).

This is a more elegant solution owing to the fact that you can make a list of arbitrary length of variables using length/2 and then just let append/3 do all the unifying for you.

Upvotes: 1

Related Questions