解释和澄清Haskell计数排序

Question

我正在阅读Cormen et al.， Introduction to Algorithms, 3rd ed.，但是我对Haskell也很感兴趣。第8.2节介绍计数排序。我对它和许多算法如何在haskell中实现很感兴趣，因为它们经常使用数组访问和破坏性更新。我看了看RosettaCode的实现(复制如下)，我发现很难遵循。

import Data.Array
countingSort :: (Ix n) => [n] -> n -> n -> [n]
countingSort l lo hi = concatMap (uncurry $ flip replicate) count
  where count = assocs . accumArray (+) 0 (lo, hi) . map (i -> (i, 1)) $ l

我喜欢haskell的一个原因是算法可以非常清晰(例如haskell快速排序示例)，至少作为一个没有优化的规范。这似乎很不清楚，我想知道这是必要的，还是只是过度。

谁能

1. 澄清这里发生了什么，
2. 可能提供了更有指导意义和更明确的实现，而
3. 处理这是否实际上实现计数排序，或者如果非严格性(懒惰)和不变性意味着这实际上是伪装成计数排序的其他排序?

Answer 1

它确实在进行计数排序。这是一个稍微重写的版本，我觉得更容易理解:

import Data.Array
countingSort :: (Ix n) => [n] -> n -> n -> [n]
countingSort l lo hi = concat [replicate times n | (n, times) <- counts]
  where counts = assocs (accumArray (+) 0 (lo, hi) [(i, 1) | i <- l])

让我们一步一步地分析一下。我们将使用列表[5, 3, 1, 2, 3, 4, 5]。

*Main> [(i, 1) | i <- [5, 3, 1, 2, 3, 4, 5]]
[(5,1),(3,1),(1,1),(2,1),(3,1),(4,1),(5,1)]

我们只是取列表中的每个元素并把它变成一个带1的元组。这是我们计算的基础。现在我们需要一种方法来对每个元素的计数求和。这就是accumArray发挥作用的地方。

*Main> accumArray (+) 0 (1, 5) [(i, 1) | i <- [5, 3, 1, 2, 3, 4, 5]]
array (1,5) [(1,1),(2,1),(3,2),(4,1),(5,2)]

accumArray的第一个参数是累加过程中应用的操作(对我们来说只是简单的加法)。第二个参数是起始值，第三个参数是边界。因此，我们最终得到一个数组，将数字映射到它们在输入中的计数。

接下来，我们使用assocs从映射中获取键/值元组:

*Main> assocs $ accumArray (+) 0 (1, 5) [(i, 1) | i <- [5, 3, 1, 2, 3, 4, 5]]
[(1,1),(2,1),(3,2),(4,1),(5,2)]

然后replicate根据其计数重复每个数字:

*Main> [replicate times n | (n, times) <- assocs $ accumArray (+) 0 (1, 5) [(i, 1) | i <- [5, 3, 1, 2, 3, 4, 5]]]
[[1],[2],[3,3],[4],[5,5]]

最后，使用concat将这个列表的列表转换为单个列表:

*Main> concat [replicate times n | (n, times) <- assocs $ accumArray (+) 0 (1, 5) [(i, 1) | i <- [5, 3, 1, 2, 3, 4, 5]]]
[1,2,3,3,4,5,5]

在我上面写的实际函数中，我使用where来分解这个一行代码。

我发现列表理解比map和concatMap更容易处理，所以这些是我在我的函数版本中所做的主要更改。

(uncurry $ flip replicate)是一个很好的技巧…flip replicate给出了replicate的一个版本，它以相反的顺序接受参数。uncurry接受该柯里化函数，并将其转换为一个接受元组作为参数的函数。总之，它们产生的结果与我的列表推导式相同，它解构了元组，然后以相反的顺序传递其参数。我对Haskell不太熟悉，不知道这是否是一种常见的习惯用法，但对我来说，列表理解更容易遵循。

Answer 2

count到accumArray作为直方图生成器。也就是说，对于从lo到hi的每个数字，它返回该数字在参数列表中出现的次数。

count ::  (Ix i, Num e) => [i] -> i -> i -> [(i, e)]
count l lo hi = assocs . accumArray (+) 0 (lo, hi) . map (i -> (i, 1)) $ l
count [6,2,1,6] 0 10 ==  
   [(0,0),(1,1),(2,1),(3,0),(4,0),(5,0),(6,2),(7,0),(8,0),(9,0),(10,0)]

count的结果用于从该规范生成原始元素。这是通过对元组snd的每个fst元素进行replicate遍历来实现的。这将产生一个由连接在一起的列表组成的列表。

 f l lo hi = map (uncurry $ flip replicate ) $ count l lo hi
 f [6,2,1,6] 0 10 == [[],[1],[2],[],[],[],[6,6],[],[],[],[]]

完全解等价于

countingSort l lo hi = concat $ f l lo hi