aggregation without reification?

[jjtolton]

I recently found myself writing some Prolog code like this:

max_string_nonrepeatsubstring(Max, String, MaxSub) :-
        findall(Substring, string_nonrepeatsubstring(String, Substring), Substrings),
        maxlength(Substrings, MaxSub, Max).

It did the job, but it made me curious if I was approaching this procedurally by using findall/3, which I assume pulls Substrings completely into memory before continuing with the maxlength/3 predicate.

In general, assuming eventual termination, do/should aggregations be reified as I have done here or should they be tabulated cumulatively somehow?

[UWN]

Ideally, such code would be written in the pure subset. And in this case I think it is feasible although quite challenging. But often this is too complex, and the quick and dirty fix is to use some 2nd order constructs to fix it. The downside is that you have now to protect such a definition against uses that could reveal its weakness. In your case it seems necessary to guarantee that String is ground.

Assuming you refer to this, note that there are already some problems in is_nonrepeating/1. Maybe concentrate first on simpler examples.

[jjtolton]

Assuming you refer to this

You caught me!!

Maybe concentrate first on simpler examples.

Oh no, this is a "leet code medium" problem! 😅

Ideally, such code would be written in the pure subset. And in this case I think it is feasible although quite challenging.

Ok, yes, that makes sense. I'm probably not thinking carefully enough, because in the code you mentioned, there was:

maxlength([], [], 0).
maxlength([S|Substrings], Substring, Max) :-
        length(S, N),
        if_( #N #< #Max0,
             (   #Max #= #Max0, Substring=Substring0 ),
             (   #Max #= #N, Substring=S )
           ),
        maxlength(Substrings, Substring0, Max0).

Which is an aggregation without using bagof/3, findall/3, etc, so really I just composed it poorly. Thank you!

[jjtolton]

Oh, no, I'm wrong. maxlength/3 is provided a list already, it's not piggybacking on backtracking. Hmm. Will have to meditate on this.

[UWN]

Why not start with nonrepeating/1 alone? You are attacking too much at the same time. No way to get to a solution.

[jjtolton]

#2498 (reply in thread)

🥳

I was really struggling with that last night because I couldn't figure out how to prove a negation. Figuring out repeating/1 was easy, but figuring out nonrepeating/1 I couldn't figure out until this comment for some reason!! 😆 😓 🤔 🤷‍♂️

[UWN]

Negating such properties is often quite difficult, because a naive full negation is not what we want. That is what constructive negation does. But here in this case, what about [a,a|non_list] which probably should fail for both. Or even non_list alone.