Re:Some Functional Programmers Are Arrogant
by pron on Thursday July 09, 2015 @02:22PM
(#9859742)
> 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.
Re:Some Functional Programmers Are Arrogant
by tel on Friday July 10, 2015 @12:43AM
(#9862335)
Have 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.
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.