Can we use foldl with bool values?

General
1

This may be a completely off the wall idea, but after @peter.ludemann introduced me to foldl/4 yesterday, I’ve been playing, and am impressed with its power.

At the same time, I was toying with an exercise in a book that required you to write a predicate ordered(L) which is true if the elements of L are in numerical order.

I came up with a solution (not posted here as it’s not relevant), but wondered if I could have done it as a one-liner using foldl/4. My idea was something like…

ordered([H|T]) :-
  foldl(=<, T, H, true).

Now this doesn’t compile for a couple of reasons, but hopefully you can see where I was trying to go with this. I tried defining a predicate to use instead of =< but couldn’t get that to work either.

Is it possible to do something like this, or am I being totally off-field here?

Thanks

2

I think that this does what you want. Note the order of the arguments to ord/3.

The foldl/4 passes a result between iterations, so the ord/3 predicate checks that ordering is correct and passes the higher value to the next iteration. (EDIT: removed an unneeded clause from ordered/1)

ord(This, Prev, NewPrev) :- Prev =< This, NewPrev = This.

ordered([]).
ordered([X|Xs]) :-
    foldl(ord, Xs, X, _).

BTW, there are also filters on lists: include/3, exclude/3, convlist/3.

4

foldl falls into what’s broadly known as aggregate functions, ie something that takes in a list and produces one atomic value.
Courtesy of a MooC I did while back with Turing-award winner Jeffrey Ullman on automata, he digressed into exactly that topic of boolean aggregators.
A nice thing about boolean algebra is there are only two aggregators: commonly called and and or.
One of the arguments with aggregators is what should be the base value for an empty list: by convention with addition it’s 0, and multiplication it’s 1.
In Boolean algebra, and is the equivalent of multiplication, so the base value is 1 or true, while or is equivalent to addition so its base value is 0 or false.

1 Like
5

Thanks for the excellent explanation.

As it happens, I’m quite used to aggregators, as I use them in Linq (I’m a C# programmer by day), which is probably why I understood foldl, and had the idea of using it with bools.

6

There are more folders. Since foldl is list oriented and not set oriented.
So for example we do not require that f(A,A) = A. This means also that
there is for example a counting folder, which behaves as follows:

count(_,N,M) :- M is N+1.

?- foldl(count, [1,2,3,2], 0, X).
X = 4.

?- foldl(count, [1,2,3], 0, X).
X = 3.

The first result wouldn’t be accepted if the list is interpreted as a set.
Similarly you can use the boolean exclusive or operation to determine
the parity of the number of elements of a list that give the value 1:

exclusive_or(X,Y,Z) :- Z is xor(X,Y).

?- foldl(exclusive_or, [1,0,1,0], 0, X).
X = 0.

?- foldl(exclusive_or, [0,1,0], 0, X).
X = 1.
7

Please could you explain this line a bit more as I can’t get my head round it.

Thanks

8

For a set, the list is a little shorter:

?- list_to_set([1,2,3,2], X).
X = [1, 2, 3].

So the count=4 is wrong, for set it should be count=3.

1 Like
9

If you want count-distinct (treating the list as a set and not a multi-set or bag):

count_distinct(List, Count) :-
    foldl(c, List, 0-[], Count-_).

c(X, CountSoFar-Seen, Count-Seen2) :-
    (   memberchk(X, Seen)
    ->  Count = CountSoFar,
        Seen2 = Seen
    ;   Count is CountSoFar + 1,
        Seen2 = [X|Seen]
    ).

Or you could use the SWI-Prolog extension for “dicts”:

count_distinct(List, Count) :-
    foldl(c, List, ''{count:0, seen:[]}, CountSeen),
    Count = CountSeen.count.

c(X, CountSeen, CountSeen2) :-
    (   memberchk(X, CountSeen.seen)
    ->  CountSeen2 = CountSeen
    ;   Count is CountSeen.count + 1,
        CountSeen2 = ''{count:Count, seen:[X|CountSeen.seen]}
    ).
10

(Nothing of Importance)

11

I can make it a bit faster by using an associative tree - O(N log N) I think:

:- use_module(library(rbtrees)).

count_distinct(List, Count) :-
    rb_empty(Seen),
    foldl(c, List, 0-Seen, Count-_).

c(X, CountSeen, CountSeen2) :-
    CountSeen = Count-Seen,
    (   rb_insert_new(Seen, X, -, Seen2)
    ->  Count2 is Count + 1,
        CountSeen2 = Count2-Seen2
    ;   CountSeen2 = CountSeen
    ).

EDIT: changed the code for c/3 from the slightly less efficient:

c(X, Count-Seen, Count2-Seen2) :-
    (   rb_insert_new(Seen, X, -, Seen2)
    ->  Count2 is Count + 1
    ;   Count2 = Count,
        Seen2 = Seen
    ).
13

What about using nextto/3 from library(lists). Like here:

sorted(L) :- forall(nextto(X,Y,L), X @< Y).

The above makes also use of forall/2. Seems to work:

?- sorted([1,2,3,4]).
true.

?- sorted([1,4,3,2]).
false.

?- sorted([1,2,2,3]).
false.
14

This got me tinkering with how to write the equivalent of the builtin min_list(+List:list(number), -Min:number) using foldl(:Goal, +List, +V0, -V)

Something I’ve found very handy learning Prolog is listing(:What) and doing listing(min_list) shows it doesn’t use foldl.

My way of doing it with foldl is as follows:

my_min(A, B, C) :-
  C is min(A, B).

my_min_list([H|T], Min) :-
  foldl(my_min, [H|T], H, Min).

On my first attempt I set the base value +V0 to a guestimated 10000, but then it occurred to me using the first value in the list would work around the problem of list where the minimum value is bigger than the guestimate.

It also returns false for empty lists, so just like the builtin with fewer lines courtesy of using foldl as the template for whatever aggregator!

Note I had to write a helper function for :Goal since it needs to be in the style where the final argument is the result of whatever aggregator operation, and the builtin min(+Expr1, +Expr2) is designed to be used on the right-hand side of is which makes arithmetic suff in Prolog more “traditional”.

15

I think that saying “returns false” can result in subtle misunderstanding; I prefer to say “it fails” (and “it succeeds” instead of “returns true”).

My code for ordered/1 above uses the same trick as your code, by setting the initial “accumulator” value to be the first list element.

If you don’t like writing auxiliary predicates, there’s library(yall), which would allow writing:

minlist([L|List], Min) :-
    foldl([A,B,C]>>(C is min(A,B)), List, L, Min).

ordered([]).
ordered([X|Xs]) :-
    foldl([This,Prev,This]>>(Prev =< This), Xs, X, _).
1 Like
16

Now I also want to jump on the bandwagon.

It would be enough to use msort/2 or the new sort/4 to sort without removing duplicates, to solve this declaratively :wink:

ordered(X) :- sort(0, =<, X, X).

This can be faster in some use cases, it is declarative, and it doesn’t take too much effort to write.

It does, however, this little silliness:

?- ordered([1, 1.0]).
false.

?- ordered([1.0, 1]).
true.

But you should then maybe make it clear that this is arithmetically ordered (and not ordered by the standard order of terms) and then use predsort, for example like this:

arith_leq_order(Order, A, B), A =< B => Order = (<).
arith_leq_order(Order, A, B), A > B => Order = (>).

arith_ordered(X) :- predsort(arith_leq_order, X, X).

and then:

?- arith_ordered([1,1,2]).
true.

?- arith_ordered([1,0]).
false.

?- arith_ordered([1, 1.0]).
true.

?- arith_ordered([1.0, 1]).
true.

But of course this has nothing to do with boolean values or folding, at least not on the surface of it.

17

There are other threads in this forum where people started using
the phrase “returns false” for failure. Its quite confusing. But SWI-Prolog

is also to blame a little bit, since it changed the top-level to display
"false" (could mean derivation with false result) upon failure, whereas

traditionally top-levels showed "no" (meaning no derivation).

/* GNU Prolog */
?- 1 == 2.
no

/* SWI-Prolog */
?- 1 == 2.
false.

In my Prolog systems I tried something new:

?- 1 == 2.
fail.
18

Someone tried to draw the analogy between “predicates” (functions returning boolean) in languages as C++ or Python and it went too far.

See also this post: Is the definition of "predicate" correct in the Glossary of Terms? - #13 by Boris

19

How about displaying “Holds” or “Does not hold” - I think that would be sufficiently strange, for a beginner to think outside the “returns” box :grinning:

20

Maybe we should embrace unicode and emojis and use any two fitting symbols, why not:

?- a == a.
💯

?- 1 == 2.
🤌🏾
1 Like
21

I would have guessed that this has to do with the idea that the answer of a query can be pasted as a query without changing it. “true” and “false” fulfil that requirement.

?- false.
false.

?- true.
true.
1 Like
22

Logic broadly comes up in two ways in computer programing and it’s something I’ve been struggling to articulate: there’s flow control and then there’s traditional boolean two-value algebra.

The latter doesn’t come up that often, and my house rule is to rather use 0 for false and 1 for true to distinguish from flow control where I don’t actually want a boolean value returned, but a different path in the program taken.

I’ve recently been doing quite a lot of Bash shell scripting, and found the Unix convention that 0 is true a bit weird. I understand the rationale since there is only one true as in no errors while there are a wide variety of falses as in error codes to explain what went wrong. I found that a bit counter intuitive since in databases searches etc there’s one false (as in no result) and any number of trues.

I’d say using foldl for a list of booleans falls into the two-value algebra rather than flow control side, and as I mentioned there the options are only and and or. Here I find using 0 and 1 especially handy because and equates to min_list and or to max_list, with the modification that an empty list anded should return 1 and an empty list ored should return 0.