A quicksort that supported progress reporting and cancellation might have a function parameter that it calls periodically to report progress, with the function returning a bool indicating cancellation. But this is using code, not data.
How might this be implemented within the data model?
2: Returns an intermediate state containing the progress of the sort in addition to the current state of the sort.
You would repeatedly pass the intermediate state to the sorting function until finished. You can use the progress component of the intermediate state to track progress.
Something like the following (I don't actually write Haskell, so this could probably be represented better):
data SomeIntermediateState = ...
data Progress = Double
data SortState a =
Complete [a]
| InProgress (SomeIntermediateState, Progress)
sortInit :: [a] -> SortState
sort :: SortState -> SortState
Glad you asked. The progress should be a bound on the worst case time.
If you have N elements, then the initial worst case time is N^2. Say after the first partition, you are left with pieces N/3 and 2N/3; the worst case time is now (N/3)^2 + (2N/3)^2. Your progress after the first partition is the difference between the original worst case and the new worst case.
This can make for uneven progress advancement but itβs monotonic: the progress bar will never go backwards.
How might this be implemented within the data model?