Why does sort/2 make this fail?

[ocharles]

I'm doing AOC 2024 in Prolog and have an oddity that I can't understand. Here's the code I have for part 1 of day 1:

:- use_module(library(charsio)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).
:- use_module(library(debug)).
:- use_module(library(lists)).
:- use_module(library(pio)).

%
% Input parsing
%

% Xs is each parsed line of input.
lines([X|Xs]) --> line(X), lines(Xs).
lines([])     --> [].

% X-Y is the line "X Y".
line(X-Y) --> integer(X), whitespace, integer(Y), ['\n'].

% N in an integer, parsed as a sequence of ASCII digits.
integer(N) --> digits(Ds), { number_chars(N, Ds) }.

% A run of one or more ASCII digits.
digits([D|Ds]) --> digit(D), digits(Ds).
digits([D])    --> digit(D).

% D is a single ASCII digit.
digit(D) --> [D], { char_code('0', Zero), char_code(D, Code), Code >= Zero, Code =< Zero + 9 }.

% One or more spaces.
whitespace --> [' '].
whitespace --> [' '], whitespace.

% Pairs is a list of pairs, where each pair is a pairwise combination of Xs and Ys.
unpairs([X-Y|Pairs], [X|Xs], [Y|Ys]) :- unpairs(Pairs, Xs, Ys).
unpairs([], [], []).

% D is the distance between X and Y.
pair_distance(X, Y, D) :- 
    D #= abs(X - Y).

% N is the solution to part 1
part_1(File, N) :-
	once(phrase_from_file(lines(Ls), File)),
	unpairs(Ls, Xs, Ys),
	sort(Xs, XsAsc),
	sort(Ys, YsAsc),
	maplist(pair_distance, XsAsc, YsAsc, Distances),
	*sum(Distances, #=, N).

Yet when I use this:

?- part_1("day-01.input", N).
   false.

Huh? Ok, so I'm told to do program slicing to figure this out. You can see I've already sliced out the sum call. If I slice out the call to maplist then I get true - so it seems to be something up with the call to maplist. I'm stuck here though. It seems to be something that sort/2 is doing, because if I write my own sorting predicate then this does work:

asc([], []).
asc([X|Xs], [Y|Zs]) :-
	select(Y, [X|Xs], Ys),
	list_min([X|Xs], Y),
	asc(Ys, Zs).

part_1(File, N) :-
	once(phrase_from_file(lines(Ls), File)),
	unpairs(Ls, Xs, Ys),
	asc(Xs, XsAsc),
	asc(Ys, YsAsc),
	maplist(pair_distance, XsAsc, YsAsc, Distances),
	sum(Distances, #=, N).

?- part_1("day-01.input", N).
   N = 1941353
;  ... .

But this is mega slow because that's unsurprisingly a terrible way to sort lists.

What's up?

[wkral]

sort/2 removes duplicates from the list. I ran into this as well I believe that can make one of the lists a different size from the other, so maplist failed for me. Unfortunately, (or possibly by design) the example for that problem works and gives the correct answer when the duplicates are removed.

To get it to work with scryer I had to use keysort/2 but that requries you to use the pairs module so it's a little indirect. There may be other solutions I think it's pretty easy to implement quicksort with prolog so that might work.

[triska]

More information about sort/2 was recently posted in a related issue: #1163 (comment)

One small thing I noticed: We can write [' '] more compactly as: " ".

?- X = [' '].
   X = " ".

[jjtolton]

Ooooo, thanks! That's very subtle, but makes sense! Not helped by the fact I can't find sort/2 in the Scryer docs to even read what it's expected behavior is (but I guess this one is ISO?)

this is something we need to fix for sure

[UWN]

8.4.3 sort/2

[jjtolton]

8.4.3 sort/2

Whoaa, what a great resource!

[bakaq]

this is something we need to fix for sure

Relevant: #2030 #2265