Prolog problems {lists}

I'm having some problems in implementing code in prolog because I find it kind of hard to understand it since I'm habitual to normal coding :(

I have to sort a list of integers but it has to keep the duplicated values. I tried to think of a solution and I would use bubble sort but I don't know how to write it in prolog... If someone can explain the code step by step and to enlighten me I would really appreciate...

And yeah, another problem I have is to sort a list consisting of integers and lists of numbers... I have no idea how to start with this one... For example: [1, 2, [4, 1, 4], 3, 6, [7, 10, 1, 3, 9], 5, [1, 1, 1], 7] needs to output [1, 2, [1, 4, 4], 3, 6, [1, 3, 7, 9, 10], 5, [1, 1, 1], 7].

I tried to write some code but it doesn't work at all and I gave up... I copied something from the internet for the first problem but it doesn't really make sense for me...

Solution

Prolog is normal coding 🙃

It's just not imperative coding, and it's recursive by nature. You need to stop thinking in imperative terms (telling the compute what to do), and you need to start thinking recursively (A fine book on the topic.)

MergeSort is your friend here. It is a stable, recursive sorting algorithm that is performant and well-suited to the way prolog works. The way it works is easy:

The empty list is, by definition, ordered.
A list of length 1 is also, by definition, ordered.
For lists of length > 1,
- partition the list into 2 halves,
- recursively sort each one, and
- merge the two now-ordered lists together.

That's all there is to it.

So, we need 3 things:

a predicate to partition a list into two halves,
a predicate to merge two ordered list into one ordered list, and
a predicate that orders a list, using those 2 helpers.

Partition

Partitioning a list is easy. There are two special cases that terminate the recursion, and one general case. The special cases are trivial:

The empty list ([]) is partitioned into 2 empty lists
```
partition( [] , [] , [] ) .
```
A list of length one is partitioned into itself and an empty list:
```
partition( [L] , [L] , [] ) .
```

The general case, that of a list of length greater than 1 is hardly more complex. Here, we just take the first 2 items from the list, assigning one to the left partition and the other to the right partition, and then we recurse down to process the remainder:

partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs).

Putting it all together, you get partition/3:

partition( []       , []     , []     ) .
partition( [L]      , [L]    , []     ) .
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .

Merge

Merging 2 ordered lists into one ordered list is likewise simple. We have 3 special cases that terminate recursion, and one general case. The special cases are those where one source list is empty and the other is not, and the case of both source lists being the empty list:

merge( []     , []     , []     ) .
merge( [L|Ls] , []     , [L|Ls] ) .
merge( []     , [R|Rs] , [R|Rs] ) .

The general, recursive case, where the two source lists are non-empty is a little tricker (but not much). You have

the case where the left head collates before or equal to the right head, and
the case where the left head collates after the right head.

We can use Prolog's in-built operators for the comparison of terms to determine collation sequence:

merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge(    Ls  , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @>  R, merge( [L|Ls] ,    Rs  , Xs ) .

Putting it all together, you get merge/3:

merge( []     , []     , []     ) .
merge( [L|Ls] , []     , [L|Ls] ) .
merge( []     , [R|Rs] , [R|Rs] ) .
merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge(    Ls  , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @>  R, merge( [L|Ls] ,    Rs  , Xs ) .

Sort

And sorting is likewise easy. There are 2 special cases that terminate execution, the empty list and a list of length 1, both of which are ordered by definition. The general recursive case, for lists of length greater than 1 is

partition the list,
recursively sort each half, and
merge the two now-sorted lists

Thus:

merge_sort( []       , []  ) .
merge_sort( [X]      , [X] ) .
merge_sort( [X,Y|Zs] , Ys  ) :-
    partition( [X,Y|Zs], L0, R0 ) ,
    merge_sort(L0,Ls),
    merge_sort(R0,Rs),
    merge(Ls,Rs,Ys)
    .

Whole Enchilada

You can fiddle with this at https://swish.swi-prolog.org/p/SCBlSONF.pl

partition( []       , []     , []     ) .
partition( [L]      , [L]    , []     ) .
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .

merge( []     , []     , []     ) .
merge( [L|Ls] , []     , [L|Ls] ) .
merge( []     , [R|Rs] , [R|Rs] ) .
merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge(    Ls  , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @>  R, merge( [L|Ls] ,    Rs  , Xs ) .

merge_sort( []       , []  ) .
merge_sort( [X]      , [X] ) .
merge_sort( [X,Y|Zs] , Ys  ) :-
  partition( [X,Y|Zs], L0, R0 ) ,
  merge_sort(L0,Ls),
  merge_sort(R0,Rs),
  merge(Ls,Rs,Ys)
  .

You might notice that most of the work in this program consists of pattern matching in the heads of each predicate's clauses. That's a big part of what makes Prolog as expressive and concise as it is.