Main.hs

{-# LANGUAGE LinearTypes #-}
{-# LANGUAGE UnicodeSyntax #-}
{-# LANGUAGE ImportQualifiedPost #-}
module Main where

import Data.Array.Mutable.Linear (Array, set)
import Data.Array.Mutable.Linear qualified as Array
import Prelude.Linear (Ur(..), (&), (.))

quicksort :: Array Int ⊸ Array Int
quicksort arr = case Array.size arr of
   (Ur len, arr1) -> go 0 (len-1) arr1

go :: Int -> Int -> Array Int ⊸ Array Int
go lo hi arr = case lo >= hi of
  True -> arr
  False -> case Array.read arr lo of
    (Ur pivot, arr1) -> case partition arr1 pivot lo hi of
      (Ur ix, arr2) -> case swap arr2 lo ix of
        arr3 -> case go lo ix arr3 of
          arr4 -> go (ix+1) hi arr4

partition :: Array Int ⊸ Int -> Int -> Int -> (Ur Int, Array Int)
partition arr pivot lx rx
  | (rx < lx) = (Ur rx, arr)
  | otherwise = case Array.read arr lx of
      (Ur lVal, arr2) -> case Array.read arr2 rx of
        (Ur rVal, arr3) -> case (lVal <= pivot, pivot < rVal) of
          (True, True) -> partition arr3 pivot (lx+1) (rx-1)
          (True, False) -> partition arr3 pivot (lx+1) rx
          (False, True) -> partition arr3 pivot (lx-1) (rx-1)
          (False, False) -> case swap arr3 lx rx of
            arr4 -> partition arr4 pivot (lx+1) (rx-1)

swap :: Array Int ⊸ Int -> Int -> Array Int 
swap arr lx rx = 
    case Array.read arr lx of
      (Ur lVal, arr1) -> case Array.read arr1 rx of
        (Ur rVal, arr2) -> set lx rVal (set rx lVal arr2)

main :: IO ()
main = case Array.fromList [1::Int, 4, 11, 7, 5, 9] (Array.toList Prelude.Linear.. quicksort) of
    Ur as -> print as

qs.cabal

cabal-version:      3.0
name:               qs
version:            0.1.0.0
synopsis:

-- A longer description of the package.
-- description:
homepage:

-- A URL where users can report bugs.
-- bug-reports:
license:            NONE
author:             Daniel Díaz
maintainer:         diaz_carrete@yahoo.com

-- A copyright notice.
-- copyright:
-- category:
extra-source-files: CHANGELOG.md

executable qs
    main-is:          Main.hs

    -- Modules included in this executable, other than Main.
    -- other-modules:

    -- LANGUAGE extensions used by modules in this package.
    -- other-extensions:
    build-depends:    base ^>=4.16.2.0,
                      linear-base >= 0.2.0

    -- Directories containing source files.
    -- hs-source-dirs:
    default-language: Haskell2010