Haskell中的Random-Pivot Quicksort [英] Random-Pivot Quicksort in Haskell
问题描述
是否有可能在Haskell中实现一个快速排序（使用RANDOM-PIVOT），它仍然有一个简单的 Ord a => [a] - > [a] 签名？
我开始了解Monads，现在我很友善将单子解释为一种命令模式，这对IO来说非常有用。
所以，我明白一个返回一个随机数的函数实际上应该返回一个像IO这样的monadic值，否则它会破坏引用透明性。我也明白，应该没有办法从返回的monadic值中'提取'随机整数，否则，它会再次破坏参考透明度。
但是，我仍然认为应该可以实现'纯' [a] - > [a] quicksort函数，即使它使用随机数据透视，因为，它是参照透明的。从我的角度来看，随机数据透视仅仅是一个实现细节，不应该改变函数的签名。
OBS：我对实际的快速排序没有兴趣问题（所以，我不想听起来粗鲁，但我不是在寻找使用mergesort或随机数据透视不会增加实际性能类）我实际上对如何实现一个使用'不纯'函数的'纯'函数感兴趣，例如快速排序，我可以确保函数实际上是一个纯函数。
Quicksort就是一个很好的例子。在这种情况下， ，你知道这个函数是引用透明的，但是你不能向编译器证明它，你可以使用函数 unsafePerformIO :: IO a - >例如，你可以使用 code> unsafePerformIO 获得一个初始随机状态，然后用这个状态做任何事情。
但请注意：不要如果它不是真的需要，就使用它。即使如此，请仔细考虑一下。 unsafePerformIO 有点是所有邪恶的根源，因为它的后果可能是戏剧性的 - 任何事情都可以通过强制使用这个函数来破坏RTS来实现。
Is it possible to implement a quicksort in Haskell (with RANDOM-PIVOT) that still has a simple Ord a => [a]->[a] signature?
I'm starting to understand Monads, and, for now, I'm kind of interpreting monads as somethink like a 'command pattern', which works great for IO.
So, I understand that a function that returns a random number should actually return a monadic value like IO, because, otherwise, it would break referential transparency. I also understand that there should be no way to 'extract' the random integer from the returned monadic value, because, otherwise, it would, again, break referential transparency.
But yet, I still think that it should be possible to implement a 'pure' [a]->[a] quicksort function, even if it uses random pivot, because, it IS referential transparent. From my point of view, the random pivot is just a implementation detail, and shouldn't change the function's signature
OBS: I'm not actually interested in the specific quicksort problem (so, I don't want to sound rude but I'm not looking for "use mergesort" or "random pivot doesn't increase performance in practice" kind of answers) I'm actually interested in how to implement a 'pure' function that uses 'impure' functions inside it, in cases like quicksort, where I can assure that the function actually is a pure one.
Quicksort is just a good example.
In such cases, where you know that the function is referentially transparent, but you can't proof it to the compiler, you may use the function unsafePerformIO :: IO a -> a from the module Data.Unsafe.
For instance, you may use unsafePerformIO to get an initial random state and then do anything using just this state.
But please notice: Don't use it if it's not really needed. And even then, think twice about it. unsafePerformIO is somewhat the root of all evil, since it's consequences can be dramatical - anything is possible from coercing different types to crashing the RTS using this function.
这篇关于Haskell中的Random-Pivot Quicksort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
