Stream: t-compiler/wg-nll

Topic: Q: union find data structures

Eh2406 (Jan 07 2019 at 14:57, on Zulip):

I have a question about chalk/polonius implomatation.

For Cargo's resolver, I have been looking into persistent union find data structures. The papers I am reading have had 2 examples of where these are useful: for type resolution and for Prolog implementations. So my question is does chalk/polonius already have an implementation if not would a crate be useful for chalk/polonius?

Eh2406 (Jan 07 2019 at 15:10, on Zulip):

A quote from the paper:
"In Prolog, for example, variables of clauses correspond to elements of a set, and unifications imply disjoint set union operations. In this case, the availability of multiple versions of disjoint sets allows one to support backtracking and branching techniques, and to trace different program executions at the same time."

lqd (Jan 07 2019 at 15:15, on Zulip):

does it have to be persistent ? ena and rustc have a regular union-find IIRC

Eh2406 (Jan 07 2019 at 15:17, on Zulip):

For Cargo's resolver it would be nice. (I have already made the graph structure persistent, for a big performance win.)

lqd (Jan 07 2019 at 15:17, on Zulip):

(for polonius it's not immediately obvious to me right now, and the chalk team will be able to answer in the other stream, either niko or scalexm)

davidtwco (Jan 07 2019 at 15:18, on Zulip):


lqd (Jan 07 2019 at 15:18, on Zulip):

(@davidtwco yeah eh2406 posted this question there already :)

davidtwco (Jan 07 2019 at 15:19, on Zulip):

Ah, :thumbs_up:

Last update: Jul 14 2020 at 13:35UTC