你能为基数排序制定一个幺半群吗？

Question

This is the pseudocode for the radix sort:

Pseudocode for Radix Sort:
Radix-Sort(A, d)
// Each key in A[1..n] is a d-digit integer. (Digits are
// numbered 1 to d from right to left.)
1. for i = 1 to d do
Use a stable sorting algorithm to sort A on digit i.

这是基数排序的Scala代码：

object RadixSort {
  val WARP_SIZE = 32

  def main(args: Array[String]) = {
    var A = Array(123,432,654,3123,654,2123,543,131,653,123)

    radixSortUintHost(A, 4).foreach(i => println(i))
  }

  // LSB radix sort
  def radixSortUintHost(A: Array[Int], bits: Int): Array[Int] = {
    var a = A
    var b = new Array[Int](a.length)

    var rshift = 0
    var mask = ~(-1 << bits)

    while (mask != 0) {
      val cntArray = new Array[Int](1 << bits)

      for (p <- 0 until a.length) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)+= 1
      }

      for (i <- 1 until cntArray.length)
        cntArray(i) += cntArray(i-1)

      for (p <- a.length-1 to 0 by -1) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)-= 1
        b(cntArray(key)) = a(p)
      }

      val temp = b
      b = a
      a = temp

      mask <<= bits
      rshift += bits
    }

    b
  }
}

这是基数排序的Haskell代码：

import Data.Bits (Bits(testBit, bitSize))
import Data.List (partition)

lsdSort :: (Ord a, Bits a) => [a] -> [a]
lsdSort = fixSort positiveLsdSort

msdSort :: (Ord a, Bits a) => [a] -> [a]
msdSort = fixSort positiveMsdSort

-- Fix a sort that puts negative numbers at the end, like positiveLsdSort and positiveMsdSort
fixSort sorter list = uncurry (flip (++)) (break (< 0) (sorter list))

positiveLsdSort :: (Bits a) => [a] -> [a]
positiveLsdSort list = foldl step list [0..bitSize (head list)] where
step list bit = uncurry (++) (partition (not . flip testBit bit) list)

positiveMsdSort :: (Bits a) => [a] -> [a]
positiveMsdSort list = aux (bitSize (head list) - 1) list where
aux _ [] = []
aux (-1) list = list
aux bit list = aux (bit - 1) lower ++ aux (bit - 1) upper where
    (lower, upper) = partition (not . flip testBit bit) list

我的问题是：使用基数排序可以制定一个单子或半群吗？

- hawkeye

---

你的意思是创建一个新的半群实例，其二元操作使用基数排序来保持顺序？ - David Young

Yes. - Daniel Wagner

你无法将算法（例如排序）“写成单子”。你可以使用单子来表达算法，比如在你提出的另一个问题的回答中所述。链接为 https://dev59.com/lnzaa4cB1Zd3GeqPS6z3?rq=1 - Alexey Romanov

谢谢@AlexeyRomanov - 非常有帮助 - 我已经更新了问题。 - hawkeye

Answer 1

基数排序的不变条件是使用前k位对数据进行排序。 如果您想要一个添加更多数据（无论是否已排序）的操作，则需要合并排序功能，而不是基数排序。 如果您要添加的是所有记录的数据位，则可以使用单子。

编辑：单子的核心是一个关联操作。 我们可以将排序位视为应用偏序的一种方式。您逐位摄取所有记录的数据。每个位应用一个偏序。这是可结合的，您可以合并一些位以获得更详细的偏序。请注意，顺序很重要，但仍然是可结合的，因此可以视为单子。

- Meir Maor

---

谢谢@Meir - 假设我想要一个基数排序 - 你会怎么做呢？ - hawkeye

Answer 2

我认为你对基数排序的想法可能太过字面化了。抽象地说，我想你想要的是一个单子：

1. 有序列表，具有
2. 合并

重要的问题是，你想如何表示排序的列表。如果你将它们表示为已排序的 Haskell 列表，则合并操作是合并排序中使用的通常逐个合并的一部分。如果你以更“基数”方式表示它们，那么你将会有某种trie（字典树）的变体。你可能可以找到一些用于合并 tries 的算法。在 bytestring-trie 中有一个，但它的实现似乎没有记录。

- dfeuer

---

假设我想编写自己的数据结构？ - hawkeye

@hawkeye，我不明白谁编写数据结构的重要性。你能解释一下吗？ - dfeuer