DEV Community

Cover image for Learning Pilog - 6: More Lists
Mia
Mia

Posted on • Originally published at picolisp-explored.com

Learning Pilog - 6: More Lists

In the last post, we showed how lists look like and discussed recursion concepts and the member predicate. Today we will look into some further list functions: appending and reversing, and the concept of accumulators.

This post is based on this tutorial.


The append predicate

Another built-in predicate in Pilog is the "append" predicate, which takes three arguments: The first two are the sublists and the third one is the concatenated list.

: (? (append (a b) (c) @X))
 @X=(a b c)
-> NIL
Enter fullscreen mode Exit fullscreen mode

Let's see how many possibilities we have to create [a,b,c] out of two sublists:

: (? (append @X @Y (a b c)))
 @X=NIL @Y=(a b c)
 @X=(a) @Y=(b c)
 @X=(a b) @Y=(c)
 @X=(a b c) @Y=NIL
-> NIL
Enter fullscreen mode Exit fullscreen mode

Let's now take a look at the definition of append (you can find it in the pilog.l library file of your PicoLisp installation). Like member, it is defined recursively. The base case is appending a list @L to an empty list NIL, which means that the result is equal to the final list @L.

(be append (NIL @X @X))
Enter fullscreen mode Exit fullscreen mode

If we are at the base case, the resulting list is equal to the second argument. Now, if the first argument only had one item @A, the new list would be equal to the second argument (now called @Y) prepended by the head of of the first list, right? And this can be repeated recursively, like this:

(be append ((@A . @X) @Y (@A . @Z)) (append @X @Y @Z))
Enter fullscreen mode Exit fullscreen mode

So, to be precise, the (Prolog) predicate name append was maybe not the best choice. concatenated would have fit better (see SWI prolog docs). Let's trace what is happening:

: (? append (append (a b) (c) @X))
2 (append (a b) (c) (a . @Z))
2 (append (b) (c) (b . @Z))
1 (append NIL (c) (c))
 @X=(a b c) 
-> NIL
Enter fullscreen mode Exit fullscreen mode

The first list is reduced down to an empty list, then the second argument is set equal to the third argument. After that, the third argument is "filled up" until we reach the final result.

As you can see, it works, but it takes a lot of steps and can become quite unefficient quickly.


The reversepredicate

Let's look at another predicate called reverse (not built-in in pilog). It returns true if the elements of the first argument are in reverse order compared to the second argument:

: (? (reverse (a b c) @X))
 @X = (c b a)
Enter fullscreen mode Exit fullscreen mode

We could implement it using append again with a recursive approach: starting from an empty list and then building it up by concatenating the head.

(be reverse (NIL NIL))

(be reverse ((@A . @X) @R)
   (reverse @X @Z)
   (append @Z (@A) @R))
Enter fullscreen mode Exit fullscreen mode

However, due to the low efficiency of append, this is not to be recommended. Let's find a better approach.


Using an accumulator

A better idea is to use an accumulator to solve this task. An accumulator is basically a list that "takes up" the elements that are processed.

(be accRev ((@H . @T) @A @R)
   (accRev @T (@H . @A) @R) )

(be accRev (NIL @A @A))
Enter fullscreen mode Exit fullscreen mode

The result (which is the third argument) corresponds exactly to the reversed list. So all we need to do is then to define our (reverse (@L @R)) predicate as follows:

(be reverse (@L @R)
   (accRev @L NIL @R))
Enter fullscreen mode Exit fullscreen mode

Let's trace it in order to check if it does what we think it does:

: (? reverse accRev ( reverse (a b c) @X))
1 (reverse (a b c) @R)
1 (accRev (a b c) NIL @R)
1 (accRev (b c) (a) @R)
1 (accRev (c) (b a) @R)
2 (accRev NIL (c b a) (c b a))
 @X=(c b a)
-> NIL
Enter fullscreen mode Exit fullscreen mode

The advantage is that the result is directly available after the last step, while our "naive" reverse needed to travel the whole recursion tree back up.


Example: Palindrome Checker

Speaking of reversed lists, one example should not be missing: How to write a simple palindrome checker. Actually we have all we need already except for the actual palindrome predicate which only takes one argument, a list:

(be palindrome (@L)
   (reverse @L @L) )
Enter fullscreen mode Exit fullscreen mode

For reverse, we can use one of our previously defined predicates. Let's test it:

: (? (palindrome ( r o t a t o r)))
-> T

: (? (palindrome ( a b c d e f g)))
-> NIL
Enter fullscreen mode Exit fullscreen mode

You can find the sources for all examples here.

In the last post of the Prolog Crash Course series, we will take a look at "Cuts and Negations".


Sources

https://www.swi-prolog.org/pldoc/man?predicate=append/3

Top comments (0)