Is there a priority queue implementation in ATS?

Question

I need to do some sort of priority-based search. Could someone point me to a priority queue implementation in ATS?

Answer 1

You can readily base a priority queue on a binomial heap.

There are two implementations of binomial heaps in ATS. Here are some use-cases:

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLIB/libats_linheap_binomial.dats

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATSLIB/libats_linheap_binomial2.dats

Answer 2

I came up with some unsafe C-based max-heap (based on somebody else's gist). I think that it does show that interfacing with C code in ATS, while generally unsafe, is very easy to do.

See the full sample at Glot.io

EDIT: here's another implementation, this time in ATS. It's a bit of a hassle to use, though (too many indexes in the type!), but the key salient feature of this code is that it is type-safe while also being extremely close to a typical C implementation in terms of runtime behavior.