我如何概括这个就地选择排序？

以下是Monad中ST Monads中选择排序的实现。输入数组被复制到STUArray s Int Int与thaw，然后复制就地排序。我如何概括这个就地选择排序？

selectionSort :: UArray Int Int -> UArray Int Int 
selectionSort arr = runSTUArray $ do 
    let (l, n) = bounds arr 
    a <- thaw arr 
    forM_ [l..n] $ \i -> do 
    minIdx <- newSTRef i 
    forM_ [i..n] $ \j -> do 
     currentMin <- readSTRef minIdx 
     jVal <- readArray a j 
     minVal <- readArray a currentMin 
     when (jVal < minVal) (writeSTRef minIdx j) 
    currentMin <- readSTRef minIdx 
    iVal <- readArray a i 
    minVal <- readArray a currentMin 
    writeArray a i minVal 
    writeArray a currentMin iVal 
    return a

使用FlexibleContexts，我想概括类型：

(IArray UArray a, Ord a, Ix i, Enum i) => UArray i a -> UArray i a

然而，这将导致以下类型的错误：

Could not deduce (MArray (STUArray s) a (ST s)) 
    arising from a use of `thaw' 
from the context (IArray UArray a, Ord a, Ix i, Enum i)

如何更改的selectionSort约束允许这种泛化？

来源

2016-12-13 John Lavelle

如果你只是添加它说缺少的约束？ – dfeuer

's'的类型不明确 –

不幸的是，array的API API不能正确隐藏s状态参数。当您编写runSTUArray action时，action将输入s类型参数。在selectionSort的类型注释中，我们必须编写MArray (STUArray s) a (ST s)，但这不是有意义的，因为在runned动作中使用的s参数在此范围内甚至不在此范围内。在这里提到s只是引入了一个新的不同的s参数，因此含糊不清的错误。

constraint包有这样的事情很好的解决方案。对于Forall从Data.Constraint.Forall我们可以表示约束必须适用于类型参数的任意选择。在我们的例子中，我们可以表示MArray (STUArray s) a (ST s)必须适用于任意s，而在ST动作中，我们可以将量化约束实例化为我们需要的具体s。

{-# language UndecidableInstances, ScopedTypeVariables #-} 

import Data.STRef 
import Control.Monad 
import Control.Monad.ST.Strict 
import Data.Constraint.Forall 
import Data.Constraint 
import Data.Proxy

首先，我们必须创建一个包装类，我们可以插入Forall。

class (MArray (STUArray s) a (ST s)) => MArray' a s 
instance (MArray (STUArray s) a (ST s)) => MArray' a s

现在Forall (MArray' a)变得从中我们可以产生MArray' a s约束任意s约束，并MArray' a s意味着由超类的MArray (STUArray s) a (ST s)约束（这是我们真正需要的）。

为了方便起见，我们需要一个备用转轮功能这使得s输入类型参数更明确的，因此，我们可以参考它在体内：

runSTUArray' :: (forall s. Proxy s -> ST s (STUArray s i e)) -> UArray i e 
runSTUArray' f = runSTUArray (f Proxy)

一般selectionSort现在可以写作，我们观察它可以专门到以前的类型：

selectionSort :: 
    forall i a. 
    (IArray UArray a, Ord a, Ix i, Enum i, Forall (MArray' a)) 
    => UArray i a -> UArray i a 
selectionSort arr = runSTUArray' $ \(s :: Proxy s) -> do 
    let (l, n) = bounds arr 

    -- we use "inst" and a type annotation on its result to instantiate 
    -- the Forall constraint to the current "s" 
    case inst of 
    (Sub (Dict :: Dict (MArray' a s))) -> do 

     a <- thaw arr 
     forM_ [l..n] $ \i -> do 
     minIdx <- newSTRef i 
     forM_ [i..n] $ \j -> do 
      currentMin <- readSTRef minIdx 
      jVal <- readArray a j 
      minVal <- readArray a currentMin 
      when (jVal < minVal) (writeSTRef minIdx j) 
     currentMin <- readSTRef minIdx 
     iVal <- readArray a i 
     minVal <- readArray a currentMin 
     writeArray a i minVal 
     writeArray a currentMin iVal 
     return a 

selectionSort' :: UArray Int Int -> UArray Int Int 
selectionSort' = selectionSort

来源

2016-12-14 12:42:50

唉！这是一个聪明的解决方法。我从来不知道'Forall'是为了什么... – Alec

我如何概括这个就地选择排序？

回答

相关问题