Bug in display_list

[chownces]

display_list does not show the correct list notation, when we apply display_list to the suggested solution for the subsets question in Studio 6

subsets(list(1,2,3)); // omitted subsets implementation

[Cloud7050]

Oh nice, an issue has already been opened. I was confused by this, and messed around with my answer, the answer that was gone through, and bunches of test code trying to figure it out. It seems to have to do with some odd mix of append(), map() and x being abstracted in this case. Small example to illustrate/replicate issue:

const x = list(
    list(2),
    list(2, 3)
);
display_list(append(
    x,
    map(l => pair(1, l), x)
));
display_list(append(
    list(
        list(2),
        list(2, 3)
    ),
    map(l => pair(1, l), x)
));

[parnikkapore]

Triaged this for fun for a bit and reduced the small example further. I can't get it any smaller while still reproducing the issue:

const x = list(
    list(2, 3)
);

display_list(append(
    x,
    map(l => pair(1, l), x)
)); // list(list(2, 3), [1, list(2, 3)]) - Wrong

display_list(append(
    list(list(2, 3)),
    map(l => pair(1, l), x)
)); // list(list(2, 3), list(1, 2, 3)) - Correct

[thomastanck]

const x1 = list(2, 3);
const x2 = list(x1, pair(1, x1));
display_list(x2);
// list(list(2, 3), [1, list(2, 3)])

The cause is an incorrect algorithm that failed to handle list dependencies correctly in certain cases (like this one). That being said, it's not obvious to me how to gracefully handle dependencies while also being performant on inputs with high sharing and/or cycles.

We will take a short look this weekend and see if it has a simple fix, else this needs a rewrite. The best solution might be to (accurately) transform a relatively simple recursive solution into an iterative one.

[martin-henz]

This bug is still there. It was rediscovered by a CS1101S student today.

[RichDom2185]

Bug also present for the following sample code (as reported by Grace):

const xs = list(2, 3);
display_list(list(pair(1, xs), pair(4, xs)));