{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih2zjk2we4gnjdwvkofi2wnmolhp6qxxycrbkxklkelg4t6dbiclm",
    "uri": "at://did:plc:pi6woz4d47bkuws673w2il2r/app.bsky.feed.post/3mk67jbllylc2"
  },
  "path": "/t/pure-borrow-linear-haskell-meets-rust-style-borrowing/13975#post_2",
  "publishedAt": "2026-04-23T13:33:10.000Z",
  "site": "https://discourse.haskell.org",
  "textContent": "… And now I think it might be also good to show the flavour of work-stealing version implementation of quicksort. Here it is:\n\n\n    qsortDC' ::\n      (Ord a, Copyable a) =>\n      -- | Threshold for the length of vector to switch to sequential sort.\n      Int ->\n      DivideConquer α Pair (LV.Vector a)\n    qsortDC' thresh =\n      DivideConquer\n        { divide = \\vs ->\n            case LV.size vs of\n              (Ur n, v)\n                | n <= 1 ->\n                    v `lseq` Control.pure Done\n                | n <= thresh ->\n                    Done Control.<$ LV.qsort 0 v\n                | otherwise -> Control.do\n                    let i = n `quot` 2\n                    (Ur pivot, v) <- LV.copyAtMut i v\n                    (lo, hi) <- LV.divide pivot v 0 n\n                    Control.pure $ Continue $ Pair lo hi\n        }\n\n\nIt is just a rewritten version of `qsort` in the post, but now defined in terms of `DivideConquer` datatype:\n\n\n    data DivideConquer α t a = DivideConquer\n      { divide :: forall β. (α >= β) => Mut β a %1 -> BO β (Result β t a)\n      }\n\n    data Result β t a = Done | Continue (t (Mut β a))\n\n\nThat is, it just encodes the divide-and-conquer nature within general API, using `BO`-monad inside each step.\nActual computation can now be done by calling `divideAndConquer` combinator on it:\n\n\n    qsortDC ::\n      (RandomGen g, Ord a, Copyable a, α >= β) =>\n      -- | The # of workers.\n      Int ->\n      -- | Threshold for the length of vector to switch to sequential sort.\n      Int ->\n      g ->\n      Mut α (LV.Vector a) %1 ->\n      BO β (Mut α (LV.Vector a))\n    qsortDC nwork thresh = divideAndConquer nwork (qsortDC' thresh)\n\n    divideAndConquer ::\n      forall α β t a g.\n      (RandomGen g, Data.Traversable t, Consumable (t ()), α >= β) =>\n      -- | The # of workers.\n      Int ->\n      DivideConquer α t a ->\n      g ->\n      Mut α a %1 ->\n      BO β (Mut α a)\n\n\nUnder 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`.\nAlthough the scheduler logic of `divideAndConquer` still has lot of room of improvements, but it seems quite promising example of applicability of Pure Borrow",
  "title": "Pure Borrow: Linear Haskell Meets Rust-Style Borrowing"
}