3 ms·
> You can write a perfectly great Timsort that's pure. I would be interested to learn how (with the same space complexity?), but anyway my point is that writin
by pron 11y ago
> You can write a perfectly great Timsort that's pure.
I would be interested to learn how (with the same space complexity?), but anyway my point is that writing a provably correct Timsort using CH is harder than simply proving the imperative algorithm with a model checker.
- tel 11y agoHave a pure model of memory which is implemented directly. Associate this with a proof that the extensional side of it is pure (copying mechanics of substructural types) and you're done.
- pron 11y agoRight, but proving correctness would still be much harder than with the model checker, I think.