是否有可能在Haskell(使用RANDOM-PIVOT)中实现一个仍然具有简单Ord a => [a]->[a]签名的快速排序？
我开始理解Monads了,而且,就像现在一样,我将monad解释为像'命令模式'这样的东西,这对于IO非常有用.
所以,我理解一个返回随机数的函数实际上应该返回一个像IO一样的monadic值,因为否则会破坏引用透明性.我也明白,应该没有办法从返回的monadic值中"提取"随机整数,否则,它会再次破坏参照透明度.
但是,我仍然认为应该可以实现'纯' [a]->[a]快速排序功能,即使它使用随机数据透视,因为它是参考透明的.从我的角度来看,随机数据透视只是一个实现细节,不应该改变函数的签名
OBS:我对具体的快速排序问题实际上并不感兴趣(所以,我不想听起来很粗鲁,但我不是在寻找"使用mergesort"或"随机支点不会在实践中提高性能"的答案)我实际上对如何实现一个在其中使用'不纯'函数的'纯'函数感兴趣,在快速排序的情况下,我可以确保该函数实际上是纯函数.
Quicksort就是一个很好的例子.