sorting-network: Sort small lists with sorting network.

[ apache, library, sorting ] [ Propose Tags ]

Functions that sort small (2~16 elements) lists or homogenous tuples.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.2.0.0, 0.2.1.0
Change log CHANGELOG.md
Dependencies base (>=4.15 && <=1000), primitive, template-haskell, vector [details]
License Apache-2.0
Author Javran Cheng
Maintainer javran.c@gmail.com
Category Sorting
Home page https://github.com/Javran/sorting-network#readme
Bug tracker https://github.com/Javran/sorting-network/issues
Source repo head: git clone https://github.com/Javran/sorting-network
Uploaded by javran at 2023-03-08T08:02:13Z
Distributions NixOS:0.2.1.0
Downloads 95 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-03-08 [all 1 reports]

Readme for sorting-network-0.2.1.0

[back to package description]

sorting-network

Sort small lists with sorting network.

How to use

This library provides functions that can sort small (2 ~ 16 elements), fixed-sized list / homogenous tuple of elements.

To use this library, import Data.SortingNetwork and you will bring two sets of functions into scope:

-- where X is a number from 2-16
unsafeSortListXBy :: (a -> a -> Ordering) -> [a] -> [a]

-- where X is a number from 2-16
sortTup2By :: (a -> a -> Ordering) -> (a, a) -> (a, a)
sortTup3By :: (a -> a -> Ordering) -> (a, a, a) -> (a, a, a)
sortTup4By :: (a -> a -> Ordering) -> (a, a, a, a) -> (a, a, a, a)
...
sortTup16By :: (a -> a -> Ordering) -> (a, a, ..., a) -> (a, a, ..., a)

in which unsafeSortListXBy are partial functions that only accept list of corresponding length (you will get pattern matching failures if that is not the case).

How it works

A sorting network can sort fixed size list of elements.

Observe that the following function sorts a tuple of 3 elements (name shadowing is intentional for demostration):

sortTup3By :: (a -> a -> Ordering) -> (a, a, a) -> (a, a, a)
sortTup3By = \cmp (a, b, c) ->
  let sw = \u v f ->
        if cmp u v == GT then f v u else f u v
   in sw a b \a b ->
        sw a c \a c ->
          sw b c \b c ->
            (a, b, c)

This works because it simulates a sorting network of length 3: if we pretend variable a, b, and c are 3 wires in the network, and sw a b \a b -> {body} applies a comparator on wire a and b, shadowing old variables with now properly ordered a and b in the {body}.

To generalize, if we have n variables and a sorting network known to sort n elements, we can build a sort function of fixed size n by building sorting network with comparators applied layer-by-layer in that order.

This library builds those functions for you, utilizing template haskell.

Acknowledgment

This library takes inspiration from @oisdk's post Sorting Small Things in Haskell.

Optimal networks (by size) are taken from https://bertdobbelaere.github.io/sorting_networks.html.

Also thanks for all the suggestion, support, and criticism from the initial release thread on Reddit.