Haskell中的Random-Pivot Quicksort

Question

是否有可能在Haskell(使用RANDOM-PIVOT)中实现一个仍然具有简单Ord a => [a]->[a]签名的快速排序？

我开始理解Monads了,而且,就像现在一样,我将monad解释为像'命令模式'这样的东西,这对于IO非常有用.

所以,我理解一个返回随机数的函数实际上应该返回一个像IO一样的monadic值,因为否则会破坏引用透明性.我也明白,应该没有办法从返回的monadic值中"提取"随机整数,否则,它会再次破坏参照透明度.

但是,我仍然认为应该可以实现'纯' [a]->[a]快速排序功能,即使它使用随机数据透视,因为它是参考透明的.从我的角度来看,随机数据透视只是一个实现细节,不应该改变函数的签名

OBS:我对具体的快速排序问题实际上并不感兴趣(所以,我不想听起来很粗鲁,但我不是在寻找"使用mergesort"或"随机支点不会在实践中提高性能"的答案)我实际上对如何实现一个在其中使用'不纯'函数的'纯'函数感兴趣,在快速排序的情况下,我可以确保该函数实际上是纯函数.

Quicksort就是一个很好的例子.

Answer 1

你假设选择枢轴点只是一个实现细节.考虑对集合进行部分排序.像卡片上的快速排序一样

如果面值较小但是如果您要评估布尔值,则a卡<卡b:

  4 spades < 4 hearts (false)
  4 hearts < 4 spades (false)
  4 hearts = 4 spades (false)

在这种情况下,枢轴的选择将决定卡的最终排序.以完全相同的方式

对于像这样的功能

a = get random integer  
b = a + 3
print b 

是由a决定的.如果你是随机选择某些东西,那么你的计算是或者可能是非确定性的.