Demonstration of how I did a mechanical translation of procedural code to Prolog and ended up with the exact same thing 
If I take “union” as an example, here was the code I started with (provided as “possible implementation”):
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
for (; first1 != last1; ++d_first)
{
if (first2 == last2)
return std::copy(first1, last1, d_first);
if (*first2 < *first1)
*d_first = *first2++;
else
{
*d_first = *first1;
if (!(*first1 < *first2))
++first2;
++first1;
}
}
return std::copy(first2, last2, d_first);
}
I start from the for(; first1 != last1; ++d_first) at the top. first1 != last1 says “until the first list is not exhausted”, so,
union([], ?B, ?U).
union([X|A], ?B, ?U).
The ++d_first informs me that inside the loop, for every possible path, there will be something written to the output list. I keep that in mind.
Next,
if (first2 == last2)
return std::copy(first1, last1, d_first);
This now tells me that if I am at the end of the second list, the first list is the remaining of the output list, and I am done. So:
union([], ?B, ?U).
union([X|A], B, U) :-
union_b(B, X, A, U).
union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :- ?.
Then, the first comparison of the two heads:
if (*first2 < *first1)
*d_first = *first2++;
I have committed to using compare/3 so I will write compare(Order, X, Y) and add that case. The *d_first = *first2++; tells me to consume the head of the second list and add it to the result.
union([], ?B, ?U).
union([X|A], B, U) :-
union_b(B, X, A, U).
union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
compare(Order, X, Y),
union_cmp(Order, X, Y, A, B, U).
union_cmp(>, X, Y, A, B, [Y|U]) :-
union([X|A], B, U).
The “else” of that “if” needs to be read at once because the procedural reading is important:
else
{
*d_first = *first1;
if (!(*first1 < *first2))
++first2;
++first1;
}
So, in both other cases of Order, we consume the head of the first list (++first1; at the bottom) and we also add it to the output list (*d_first = *first1; at the top).
In addition, when the two heads are equal, I can consume the head of the second list, too.
if (!(*first1 < *first2))
++first2;
So:
union([], ?B, ?U).
union([X|A], B, U) :-
union_b(B, X, A, U).
union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
compare(Order, X, Y),
union_cmp(Order, X, Y, A, B, U).
union_cmp(<, X, Y, A, B, [X|U]) :-
union(A, [Y|B], U).
union_cmp(=, X, Y, A, B, [X|U]) :-
union(A, B, U).
union_cmp(>, X, Y, A, B, [Y|U]) :-
union([X|A], B, U). % here we can take the shortcut
“The shortcut” is that we have already unpacked the head and tail of the first list in the last case above, so we can directly call union_b/4.
Finally, at the bottom, when the second list is longer than the first, we take the rest to the output:
return std::copy(first2, last2, d_first);
This informs me how to resolve the first clause of union/3, so that I get, at the end:
union([], B, B).
union([X|A], B, U) :-
union_b(B, X, A, U).
union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
compare(Order, X, Y),
union_cmp(Order, X, Y, A, B, U).
union_cmp(<, X, Y, A, B, [X|U]) :-
union(A, [Y|B], U).
union_cmp(=, X, Y, A, B, [X|U]) :-
union(A, B, U).
union_cmp(>, X, Y, A, B, [Y|U]) :-
union_b(B, X, A, U). % shortcut
Compare this to the original code for set union from library(oset) as linked above, complete with the argument-swapping shortcut. (Since we only have equality here, this is completely legal!)
% oset_union(+OSet1, +OSet2, -Union).
% -----------------------------
oset_union([], Union, Union).
oset_union([H1|T1], L2, Union) :-
union2(L2, H1, T1, Union).
union2([], H1, T1, [H1|T1]).
union2([H2|T2], H1, T1, Union) :-
compare(Order, H1, H2),
union3(Order, H1, T1, H2, T2, Union).
union3(<, H1, T1, H2, T2, [H1|Union]) :-
union2(T1, H2, T2, Union). % this shortcut swaps!
union3(=, H1, T1, _H2, T2, [H1|Union]) :-
oset_union(T1, T2, Union).
union3(>, H1, T1, H2, T2, [H2|Union]) :-
union2(T2, H1, T1, Union).
PS: I should actually try some LLM, give it the C++ code and ask it to give me a Prolog equivalent. Stay tuned!
PPS: well it ain’t gonna give it to me easily.
