That's really interesting. I'm not immediately understanding the Haskell code, but I'm eager to look at it more and learn about this language. I read that it's very fast for its level of abstraction.
I'm wondering if the bottleneck in the Swift version might be the simulated priority queue. I see that there's a Heap planned for Swift collections.
You're right! I sort of knew that it could be made faster by using a real priority queue, but like the Haskell version I wanted to stick to the standard library which is why I went with the simulated priority queue. Though the Haskell version has a bit of an advantage there - while it doesn't have a priority queue in the standard library either, the standard Set in Haskell offers a O(log n) minView.
Anyways, for curiosity's sake I went ahead and created a version that uses the preview Heap from the Swift Collections package. And indeed, it is around 4x faster. It now runs in 0.13 second on the full input.
Here's the code for the modified version (the code changes were minimal, but I had to add a Package.swift and the jazz that comes with it to import the Swift Collections package).
That's amazing! I don't often take time to appreciate a good data structure, but you've given us a good opportunity, and an example of how to use the new Heap, too. Thanks!