Prolog: working with lists

Question

I got this assignment with Prolog lists and I need some help.

Build a program in Prolog that

1. Check if a list is empty
2. Check if a list is not empty
3. Check if a list only has one element
4. Check if a list has 2 or more elements
5. Get the first element from a list
6. Get the second element from a list
7. Get a list without the first element (tail)
8. Add an element to the head of the list

Answer 1

It sounds like you are the very beginning of prolog. These questions mostly relate to how prolog unifies variables and expressions.

1. Check if a list is empty

   empty([]).
   

   In prolog, you state facts and predicates. Here, you are simply stating that any empty list is true. It is implied that all other expressions are false.

2. Check if a list is not empty

   not_empty([_|_]).
   

   (Improved by lurker). This rule matches a list that has at least a head and zero or more tail elements, so empty list would fail.

3. Check if a list only has one element

   one([_]).
   

   When prolog checks this fact, it can only bind to a list with one element. So the fact it bound already proves it is a one element list.

4. Check if a list has 2 or more elements

   two([_,_|_]).
   

   The first 2 underscores bind to 2 elements in the list, the 3rd underscore to zero or more trailing elements. So this will only evaluate to true on lists with two or more elements.

5. Get the first element from a list

   first([H|_], H).
   

   Prolog will bind H to the first element of the list in the first argument and the second argument. You call it with first([1,2,3],F).. Prolog will bind F to the first element of the list. You can also call it with first([1,2,3],1). to ask if 1 is the first element.

6. Get the second element from a list

   second([_,I|_], I).
   

   Just using simple binding, the first underscore binds with the first element, I with the second element, and the second underscore with the rest of the list, (if any). If you start asking for much higher elements, it is easier to use built-in predicates like nth1 to do the work for you.

7. Get a list without the first element (tail)

   tail([_|T],T).
   

   Prolog binds the tail to T, which must match the second T to be considered true.

8. Add an element to the head of the list

   addelem(H,T,[H|T]).
   

   Just using Prolog binding, the H will be bound to the front of the list in the 3rd argument, and T to the tail of the list. Call with

   • addelem(1,[2,3,4],T). — Binds T to [1,2,3,4].
   • addelem(1,[2,3,4],[1,2,3,4]). — Proves that this result is correct.
   • addelem(H, [2,3,4], [1,2,3,4]). — Pulls the first element of the 3rd argument, if the second argument matches the tail.
   • addelem(1, T, [1,2,3,4]). — another way of getting the tail, if the head is 1.