Pure Borrow: Linear Haskell Meets Rust-Style Borrowing

… And now I think it might be also good to show the flavour of work-stealing version implementation of quicksort. Here it is:

qsortDC' ::
  (Ord a, Copyable a) =>
  -- | Threshold for the length of vector to switch to sequential sort.
  Int ->
  DivideConquer α Pair (LV.Vector a)
qsortDC' thresh =
  DivideConquer
    { divide = \vs ->
        case LV.size vs of
          (Ur n, v)
            | n <= 1 ->
                v `lseq` Control.pure Done
            | n <= thresh ->
                Done Control.<$ LV.qsort 0 v
            | otherwise -> Control.do
                let i = n `quot` 2
                (Ur pivot, v) <- LV.copyAtMut i v
                (lo, hi) <- LV.divide pivot v 0 n
                Control.pure $ Continue $ Pair lo hi
    }

It is just a rewritten version of qsort in the post, but now defined in terms of DivideConquer datatype:

data DivideConquer α t a = DivideConquer
  { divide :: forall β. (α >= β) => Mut β a %1 -> BO β (Result β t a)
  }

data Result β t a = Done | Continue (t (Mut β a))

That is, it just encodes the divide-and-conquer nature within general API, using BO-monad inside each step. Actual computation can now be done by calling divideAndConquer combinator on it:

qsortDC ::
  (RandomGen g, Ord a, Copyable a, α >= β) =>
  -- | The # of workers.
  Int ->
  -- | Threshold for the length of vector to switch to sequential sort.
  Int ->
  g ->
  Mut α (LV.Vector a) %1 ->
  BO β (Mut α (LV.Vector a))
qsortDC nwork thresh = divideAndConquer nwork (qsortDC' thresh)

divideAndConquer ::
  forall α β t a g.
  (RandomGen g, Data.Traversable t, Consumable (t ()), α >= β) =>
  -- | The # of workers.
  Int ->
  DivideConquer α t a ->
  g ->
  Mut α a %1 ->
  BO β (Mut α a)

Under the hood, divideAndConquer uses some unsafe constructs, such as concurrent queues, but it hides its implementational detail behind the BO-based API, and user can describe their divide-and-conquer algorithm purely with BO. Although the scheduler logic of divideAndConquer still has lot of room of improvements, but it seems quite promising example of applicability of Pure Borrow