# Code review, advantages and disadvantages of these two ways of writing a predicate

**URL:** <https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795>\
**Category:** Help!\
**Created:** [August 27, 2023, 7:43pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795 "2023-08-27T19:43:40Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 27, 2023, 7:43pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/1 "2023-08-27T19:43:41Z")

</div>

I’m working my way through “_Prolog For Artificial Intelligence_” by Ivan Bratko, and exercise 3.17 is to write a `maxlist(L, M)` that succeeds when `M` is the largest number in the list `L`.

My attempt at this was:

```prolog
maxlist([H|T], Max) :-
  maxlist(T, H, Max).
maxlist([], Max, Max).
maxlist([H|T], CurrentMax, Max) :-
  (
    CurrentMax > H
    -> maxlist(T, CurrentMax, Max)
    ;
    maxlist(T, H, Max)
  ).

```

The author’s solution was:

> ```
> maxlist([N], N).
> maxlist([N1,N2|T], Max) :-
> maxlist([N2|T], MaxTail),
> max(N1, MaxTail, Max).
> 
> ```

My code is longer, and not as easy to read, but his code gave a choice point.

Anyone have any comments on either piece of code? In particular, is there anything to choose his over mine or vice versa?

Thanks

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 27, 2023, 9:10pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/2 "2023-08-27T21:10:47Z")

</div>

> [@Yossu](#):
>
> ```prolog
> maxlist([N], N).
> maxlist([N1,N2|T], Max) :-
> maxlist([N2|T], MaxTail),
> max(N1, MaxTail, Max).
> 
> ```

I assume that `max/3` is defined:

```prolog
max(X, Y, Z), X >= Y => Z = X.
max(_, Y, Z) => Z = Y.

```

Your code is “accumulator” style, which has two advantages over the textbook code: it doesn’t leave a choicepoint and it’s tail recursive (the last call in the 2nd clause of `maxlist/3` is to `maxlist/3`, so the compiler can change the recursion into iteration).

Some implementations might not leave a choicepoint for the textbook code - but they’d need to do a deeper inspection of the first argument (`[N]` vs `[N1,N2|T]`). However, this wouldn’t make the textbook code tail-recursive.

It’s hard to say which is more difficult to read.

- The textbook code can be read as:
  - the maximum of a single-element list is the element.
  - otherwise, it’s the maximum of the first element and the maximum of the rest of the list.

- Your code can be read as:
  - select the first element as the maximum-so far.
  - iterate through the rest of the list, for each element keeping the larger of the maximum-so-far and the first element.

When you have an accumulator-style predicate, you can use the foldl/4 predicate, which is more concise and doesn’t leave a choicepoint if `max/3` doesn’t:

```prolog
maxlist([L1|Ls], Max) :-
    foldl(max, Ls, L1, Max).

```

It took me a while to get used to this style of programming … this style is very common in some functional programming languages such as Haskell, Ocaml, and Lisp; but works just as well in Prolog (and sometimes a bit better) – see also maplist/3, and similar meta-predicates in [library(apply)](https://www.swi-prolog.org/pldoc/man?section=apply).

---

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 27, 2023, 10:27pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/3 "2023-08-27T22:27:37Z")

</div>

@peter.ludemann Thanks for the comments. His code for `max/3` was actually…

```prolog
max(X, Y, X) :-
  X >= Y.
max(X, Y, Y) :-
  X < Y.

```

This works, but left a choicepoint. It was while I was working on this, and an exercise for the GCD of two numbers that you [posted some code](https://swi-prolog.discourse.group/t/why-doesnt-evaluate-the-arguments/6792/2) that helped me write it using `if`.

I wrote my code based on the excellent help I’ve had here. I’m trying hard to avoid choicepoints where there is only one solution to a question (eg there’s only one maximum of two integers, only one GCD of two integers, etc), and what I learned about argument indexing led me to the code I wrote.

Thanks also for the pointer toward `foldl/4`. I’ve come across this before, and have seen similar ideas in other languages, but haven’t yet become familiar enough with it (or most of the built-in predicates) to be confident in using it. Your example will help me explore it more.

Thanks again.

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [August 28, 2023, 8:16am UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/4 "2023-08-28T08:16:58Z")

</div>

To my mind, performing the check _twice_ is inelegant, when we have -\>/2 and \*-\>/2 for if…then…else.

max/3 can be:

```prolog
max(X, Y, Max) :-
    ( X @< Y
    -> Max = Y
    ; Max = X
    ).

```

For iterating through a list, use an accumulator properly:

```prolog
max_list([H|T], Max) :-
    max_list_(T, H, Max).

max_list_([], Max, Max).
max_list_([H|T], U, Max) :-
    ( U @< H
    -> M = H
    ; M = U
    ),
    max_list_(T, M, Max).

```

This is much faster than `maxlist`, and uses less memory due to tail-end recursion not needing to remember the state of the variables.

Can test with e.g.:

```prolog
?- numlist(1, 5_000_000, NL), time(maxlist(NL, Max)).
% 6,615,659 inferences, 2.636 CPU in 2.639 seconds (100% CPU, 2510201 Lips)
ERROR: Stack limit (1.0Gb) exceeded

```

vs

```prolog
?- numlist(1, 5_000_000, NL), time(max_list(NL, Max)).
% 10,000,000 inferences, 0.248 CPU in 0.249 seconds (100% CPU, 40268784 Lips)

```

Non-tail-end recursion can be convenient, but it comes with performance and memory-usage penalties.

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [August 28, 2023, 12:45pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/5 "2023-08-28T12:45:55Z")

</div>

Bratko is a classic that I know only via other people’s quotations. It looks like you’re working a lot for your bedtime exercises 😅 👏  
I have a general question: is the if-then-else construct typical of the SWI-Prolog implementation of the language or is it a standard thing, so to say? Thanks

---

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 28, 2023, 1:06pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/6 "2023-08-28T13:06:56Z")

</div>

@brebs Thanks for that, very useful.

---

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 28, 2023, 1:08pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/7 "2023-08-28T13:08:29Z")

</div>

> [@anon419083](#):
>
> Bratko is a classic that I know only via other people’s quotations. It looks like you’re working a lot for your bedtime exercises 😅 👏

I picked up a copy of the 3rd edition really cheaply, and am working through it. It’s very good, although judging by some of the comments I’ve had here, I think some of my answers to the exercises are better than his!

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [August 28, 2023, 1:21pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/8 "2023-08-28T13:21:22Z")

</div>

> [@anon419083](#):
>
> I have a general question: is the if-then-else construct typical of the [SWI-Prolog](https://www.swi-prolog.org/pldoc/doc_for?object=manual) implementation of the language or is it a standard thing, so to say? Thanks

(If-\>Then;Else) is ISO standard. Also discussed `=>` and `*->` are SWI-Prolog specific. We find `(If*->Then;Else)` as `if(If,Them,Else)` in several Prolog systems and `=>` in [Picat](http://picat-lang.org/)

---

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 28, 2023, 1:39pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/9 "2023-08-28T13:39:08Z")

</div>

> [@brebs](#):
>
> when we have [-\>/2](https://www.swi-prolog.org/pldoc/doc_for?object=-%3E/2) and [\*-\>/2](https://www.swi-prolog.org/pldoc/doc_for?object=*-%3E/2) for if…then…else

Is there a simple explanation of the difference between these two, as I can’t get my head round the info in the docs. Prolly makes lots of sense to those who understand Prolog properly, but for beginners like me, it’s really not clear.

Thanks

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 28, 2023, 5:39pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/10 "2023-08-28T17:39:04Z")

</div>

> [@Yossu](#):
>
> a simple explanation of the difference between [[-\>/2](https://www.swi-prolog.org/pldoc/doc_for?object=-%3E/2) and [\*-\>/2](https://www.swi-prolog.org/pldoc/doc_for?object=*-%3E/2)]

`Cond -> Then ; Else` is the same as `once(Cond) *-> Then ; Else`.  
The difference is in what happens if there are more than one way for `Cond` to succeed; (\*-\>)/2 will try those alternatives but (-\>)/2 won’t.

As a contrived example:

```prolog
num(one, 1).
num(two, 2).
num(three, 3).

p(Num, Value) :-
    ( num(Num, Value)
    *-> true
    ; Value = '-none-'
    ).

```

```prolog
?- p(N,V).
N = one,
V = 1 ;
N = two,
V = 2 ;
N = three,
V = 3.

```

If `p/2` had been written with (-\>)/2, there would have been only one solution: `N=one,V=1`.

However, the behaviour if the `N` argument is instantiated would be the same for both (-\>)/2 and (\*-\>)/2, which is why (-\>)/2 is usually used – it’s relatively uncommon to have a condition that also binds a value.  
Similarly, it’s relatively uncommon to only use the “if-then” part; it’s usually of the form “if-then-else”. Also note that (;)/2 is “or” and can be defined like this:

```prolog
(A ; _) :- call(A).
(_ ; B) :- call(B).

```

---

<div class="post-metadata">

**Author:** ![Yossu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/yossu/32/5233_2.png) [@Yossu](https://swi-prolog.discourse.group/u/Yossu)\
**Post date:** [August 28, 2023, 6:55pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/11 "2023-08-28T18:55:34Z")

</div>

Brilliant!

Thanks very much for the clear explanation.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 28, 2023, 7:05pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/12 "2023-08-28T19:05:47Z")

</div>

One other thing: the if-then-else parses as follows (due to operator precedence) – the `->` binds tighter than `;`, so `Cond -> Then ; Else` can be read "(if Cond, then (cut) Then); else Else`.

```prolog
?- write_canonical((a->b;c)).
;(->(a,b),c)
true.

```

```prolog
?- forall((member(Op,[';','->','*->']), current_op(P,F,Op)), writeln(op(P,F,Op))).
op(1100,xfy,;)
op(1050,xfy,->)
op(1050,xfy,*->)

```

---

<div class="post-metadata">

**Author:** ![nbassili1](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/nbassili1/32/3325_2.png) [@nbassili1](https://swi-prolog.discourse.group/u/nbassili1)\
**Post date:** [September 1, 2023, 6:50am UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/13 "2023-09-01T06:50:29Z")

</div>

Hi,  
To add to this discussion, I bring to your attention a recent paper of ours (actually a book chapter) that discusses over 9 different implementations of min\_list/2 (all implementations could be easily mirrored for max\_list/2).

[https://www.researchgate.net/publication/371661553\_Demonstrating\_Multiple\_Prolog\_Programming\_Techniques\_Through\_a\_Single\_Operation](https://www.researchgate.net/publication/371661553_Demonstrating_Multiple_Prolog_Programming_Techniques_Through_a_Single_Operation)

My favorite one concerning elegance and efficiency is the “functional” one (implementation no. 6 in the paper) that exploits the first element of the list to deliver the temporary minimum/maximum to the rest of the “iterations” of the list. In the case of maxlist the solution looks like this:

```prolog
maxlist([N],N).
maxlist([N1,N2|T], Max) :-
    max(N1,N2,TmpMax),
    maxlist([TmpMax|T], Max).

```

In this solution there is no choice point left (if max/3 does not leave one), it is as compact as the Bratko’s solution, but it is also efficient since it is tail-recursive. At the bottom line, it is similar to the solution that uses foldl that Peter suggested, but it is easier for a Prolog programmer that has no exposure to functional programming to understand.

Hope I have helped.  
Nick

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [September 1, 2023, 7:45am UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/14 "2023-09-01T07:45:13Z")

</div>

> [@nbassili1](#):
>
> ```prolog
> maxlist([N],N).
> maxlist([N1,N2|T], Max) :-
> max(N1,N2,TmpMax),
> maxlist([TmpMax|T], Max).
> 
> ```

I would consider this an anti-pattern. Specifically, you are reusing the input list to keep the state. \[1\] And at least on my computer and SWI-Prolog this **does** in fact leave a choice point.

This is conventionally refactored to (appears as list\_min3 in your paper):

```prolog
maxlist([X|Xs], Max) :- maxlist_(Xs, X, Max).

maxlist_([], Max, Max).
maxlist_([X|Xs], Max0, Max) :-
    max(Max0, X, Max1),
    maxlist_(Xs, Max1, Max).

```

… and this solution appeared higher in the thread; and it is also the manual rewriting that foldl/4 would do, in case we defined it as:

```prolog
maxlist([X|Xs], Max) :- foldl(max, Xs, X, Max).

```

Neither of those leaves a choice point.

Note that if you are in fact doing this for numbers, you might as well use `Max is max(A, B)` instead of a hand-rolled `max/3` predicate. At the very least you avoid one unnecessary conditional.

EDIT: one more thing. SWI-Prolog provides [library(apply\_macros)](https://www.swi-prolog.org/pldoc/doc/_SWI_/library/apply_macros.pl) that does compile-time re-writing for some meta-predicates, for example maplist. But it does not currently include foldl, so while this mechanical rewriting at compile time is possible, it does not happen.

* * *

1. There is an attempt to resolve this on the syntactic level by using “semi-context notation” with a DCG rule, not sure how successful it is.

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [September 1, 2023, 7:50am UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/15 "2023-09-01T07:50:34Z")

</div>

> [@nbassili1](#):
>
> Prolog programmer that has no exposure to functional programming

I would strongly suggest any programmer to get exposure to both Prolog and functional programming 😃 we can adjust our tools to a limited set of skills, but we could also grow our skills together with our tools.

---

<div class="post-metadata">

**Author:** ![wlodr](https://avatars.discourse-cdn.com/v4/letter/w/dec6dc/32.png) [@wlodr](https://swi-prolog.discourse.group/u/wlodr)\
**Post date:** [September 1, 2023, 10:28pm UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/16 "2023-09-01T22:28:11Z")

</div>

> [@peter.ludemann](#):
>
> Your code can be read as:
> 
> - select the first element as the maximum-so far.
> - iterate through the rest of the list, for each element keeping the larger of the maximum-so-far and the first element.

Why not

- the third argument is the maximum of the second argument and all the elements of the first one.  
This is declarative (and leads to a quick correctness proof of the program). The quoted description is operational.

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [September 2, 2023, 8:16am UTC](https://swi-prolog.discourse.group/t/code-review-advantages-and-disadvantages-of-these-two-ways-of-writing-a-predicate/6795/17 "2023-09-02T08:16:25Z")

</div>

PS: There is, in fact, a difference between using arithmetic comparison operators to implement max/3, and the arithmetic function max().

```prolog
?- [user].
|: max(X,Y,M) :- ( X >= Y -> M = X ; M = Y ).
|: ^D% user://1 compiled 0.02 sec, 1 clauses
true.

?- max(1, 2+3, Max).
Max = 2+3.

?- X is max(1, 2+3).
X = 5.

```

I guess either behaviour could be the “right” one depending on the use case.