Монадное создание векторов (или: кто-то может напечатать это для меня?) - PullRequest
Новая
       15

Монадное создание векторов (или: кто-то может напечатать это для меня?)

3 голосов
/ 13 октября 2011

Я наткнулся на следующий фрагмент кода как часть этого подпотока Redddit , обсуждающего реализацию тасования Фишера-Йейтса: 

randomIs g n = fill g 0
  where
    v = enumFromN 0 n

    fill g i = when (i < n) $ do
            let (x,g') = randomR (i, n-1) g
            G.swap v i x
            fill g' (i+1)

(наверное G относится к Data.Vector.Generic.Mutable ... верно?). Никогда прежде не создавая векторы монадически, я пытаюсь понять это, особенно без аннотаций типов. Разве v не имеет типа Data.Vector Int? Почему же тогда можно передать это 1010 *? Разве это не должно быть сначала разморозить?

Я мог бы просто неправильно понять Data.Vector.Generic, но если бы кто-то мог прояснить вышесказанное (возможно, добавив аннотации типов?), Я был бы признателен.

Приложение: Вот моя собственная попытка добавления аннотаций типов: 

import qualified Data.Vector.Unboxed as UVect
import qualified Data.Vector.Unboxed.Mutable as UMVect
import qualified System.Random as R
import Control.Monad
import Control.Monad.ST

randomPermutation :: forall a. (R.RandomGen a) => a -> Int -> UVect.Vector Int
randomPermutation g n = runST newVect
    where
      newVect :: ST s (UVect.Vector Int)
      newVect = UVect.unsafeThaw (UVect.enumFromN 0 n) >>= \v ->
                fill v 0 g >>
                UVect.unsafeFreeze v

      fill x i gen = when (i < n) $
                     let (j, gen') = R.randomR (i, n-1) gen in
                     UMVect.unsafeSwap x i j >>
                     fill x (i+1) gen'

Как видите, я избегаю Data.Vector.Generic, чтобы исключить источник ошибки, вызванный, возможно, неправильным пониманием. Я также делаю вещи в ST монаде.

В моей голове тип fill должен быть 

UMVect.MVector (ST s (UVect.Vector Int)) Int -> Int -> a -> ST s ()

но объекты GHC. Есть намеки? Опять же: он проверяет, если я не аннотирую fill.

Sidenote: Я также хотел бы randomPermutation, чтобы вернуть обновленный генератор случайных чисел. Таким образом, мне нужно fill, чтобы также обрабатывать состояние генератора. С моей нынешней путаницей типов я не вижу, как сделать это аккуратно. Есть намеки?

1 Ответ

2 голосов
/ 13 октября 2011

Ошибка компиляции говорит нам: 

Expected type: ST s (UMVect.MVector (ST s (UVect.Vector Int)) Int)
Actual type: ST s (UMVect.MVector (Control.Monad.Primitive.PrimState (ST s)) Int)

Таким образом, изменение сигнатуры типа fill на UMVect.MVector (PrimState (ST s)) Int -> Int -> a -> ST s () (добавление также import Control.Monad.Primitive) решает проблему!

...