2

I am trying to find the maximum element in multilayered list (meaning list in list in list...) in Prolog. The thing is, I reviewed all the predicates 1 by 1 and they all work, except for the one that is actually supposed to solve my problem. My approach is to flatten the list (make it single-layered) and the find the maximum element in THAT list. This is my code:

is_list([]).

add([],L,L).
add([X|L1],L2,[X|L3]):-add(L1,L2,L3).

maximum([X|O],M) :- max(O,X,M),!.
max([X|O],Y,M) :- X=<Y, max(O,Y,M).
max([X|O],Y,M) :- X>Y, max(O,X,M).
max([],M,M).

flatten([],[]).
flatten([X|L1],[X|L2]):-not(is_list(X)),!,flatten(L1,L2).
flatten([X|L1],L2):-flatten(X,LX),flatten(L1,LL1),add(LX,LL1,L2).

maximum_in_multilayered_list(L,M):-flatten(L,L1),maximum(L1,N), M is N.

For some reason, I get the following error:

?- maximum_in_multilayered_list([1,[2,3],4],X).
ERROR: Type error: `[]' expected, found `[2,3]' (a list) ("x" must hold one character)
ERROR: In:
ERROR:   [13] [2,3]=<1
ERROR:   [12] max([[2|...],4],1,_7284) at c:/users/ace_m/documents/prolog/bp.pl:47
ERROR:   [11] maximum([1,...|...],_7328) at c:/users/ace_m/documents/prolog/bp.pl:46
ERROR:   [10] maximum_in_multilayered_list([1,...|...],_7366) at c:/users/ace_m/documents/prolog/bp.pl:75
ERROR:    [9] <user>
   Exception: (12) max([[2, 3], 4], 1, _7596) ? creep

I understand that the problem is that I am actually comparing a list of integers with an integer meaning they are incompatible types, but why does it even come to that? What am I doing wrong?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Aleksandar
  • 101
  • 1
  • 10
  • Look at `flatten([1,[2,3],4],L)` first. – false Dec 03 '20 at 16:25
  • Why is there a lone `is_list([]).` at the start? What about lists that are not empty? – David Tonhofer Dec 03 '20 at 16:30
  • ^^, furthermore `is_list/1` is a built-in which does exactly what you want it to accomplish. without your definition, it just works. side note: `add/3` is better known as `append/3`, which is also a built-in. :) – Will Ness Dec 03 '20 at 16:32
  • And ... you do not need to flatten! Just walk the tree looking for the maximum (I think this is called a "fold" operation on the tree, as opposed to a fold operation on a list) – David Tonhofer Dec 03 '20 at 16:47
  • 1
    @DavidTonhofer I've added to my answer an aggregate-based code which does just that, I believe. – Will Ness Dec 03 '20 at 16:54

1 Answers1

2

Remove your is_list([]) and it works.

As it is, any non-empty list is not considered to be is_list/1 material, so for [2,3] in [1,[2,3],4] the second clause in the flatten/2 definition applies, and adds X = [2,3] as is into the "flattened" list [X|L2].

But is_list/1 is already a built-in predicate which does exactly what you want.

Another way to implement this is with library(aggregate).

First we define a backtrackable predicate which enumerates all non-lists (i.e. "plain values") through the nested lists (taken from this somewhat related recent answer of mine):

nembr(Z, A) :-    % member in nested lists
  is_list(A), member(B,A), nembr(Z,B)
  ;
  \+ is_list(A), A=Z.

Then

18 ?- nembr(X, [1,[2,3],4]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
false.

19 ?- use_module(library(aggregate)).
true

20 ?- L = [1,[2,3],4], aggregate( max(X), nembr(X,L), R).
L = [1, [2, 3], 4],
R = 4.
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 1
    Prolog is like Perl: [There is more than one way to do it](https://en.wikipedia.org/wiki/There%27s_more_than_one_way_to_do_it) (although you may literally be plagued by failure until you find it and if you curate the unit tests, coding becomes a solid experimental science again) – David Tonhofer Dec 03 '20 at 16:55