7

我正在尝试对一些数据实施 Fisher-Yates 洗牌。该算法对于一维数组很容易实现。但是，我需要能够对二维矩阵中的数据进行洗牌。

我认为可以很好地推广到高维数组的一种方法是将我的任意维数矩阵转换为一维索引数组，将它们打乱，然后通过将该索引数组的每个索引处的元素与元素交换来重组矩阵在索引数组元素的索引处。换句话说，取一个 2x2 矩阵，例如：

1  2
3  4

我会把它转换成这个“数组”：

[(0, (0,0)),  (1, (0,1)),  (2, ((1,0)),  (3, (1,1))]

然后我会按照正常情况争先恐后地进入，比如说，

[(0, (1,0)),  (1, (0,1)),  (2, ((1,1)),  (3, (0,0))]

重组后，原始矩阵将变为：

2  3
4  1

我的基本方法是我想要一个看起来像这样的类型类：

class Shufflable a where
  indices    :: a -> Array Int b
  reorganize :: a -> Array Int b -> a

然后我将有一个函数来执行如下所示的随机播放：

fisherYates :: (RandomGen g) => g -> Array Int b -> (Array Int b, g)

我的想法是（减去 RandomGen 管道）我应该能够像这样洗牌一个可洗牌的东西：

shuffle :: (Shufflable a, RandomGen g) => a -> g -> (a, g)
shuffle array = reorganize array (fisherYates (indices array))

这是我到目前为止所拥有的：

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances  #-}

module Shuffle where

import Data.Array hiding (indices)
import System.Random         

fisherYates :: (RandomGen g) => Array Int e -> g -> (Array Int e, g)
fisherYates arr gen = go max gen arr
    where
      (_, max) = bounds arr

      go 0 g arr = (arr, g)
      go i g arr = go (i-1) g' (swap arr i j)
          where
            (j, g') = randomR (0, i) g

class Shuffle a b | a -> b where
  indices    :: a -> Array Int b
  reorganize :: a -> Array Int b -> a

shuffle :: (Shuffle a b, RandomGen g) => a -> g -> (a, g)
shuffle a gen = (reorganize a indexes, gen')
  where
    (indexes, gen') = fisherYates (indices a) gen

instance (Ix ix) => Shuffle (Array ix e) ix where
  reorganize a = undefined
  indices a    = array (0, maxIdx) (zip [0..maxIdx] (range bound))
      where
        bound = bounds a
        maxIdx = rangeSize bound - 1

swap :: Ix i => Array i e -> i -> i -> Array i e
swap arr i j = arr // [ (i, i'), (j, j') ]
    where
      i' = arr!j
      j' = arr!i

我的问题：

  1. 我觉得这是解决一个简单问题的很多语言扩展。用另一种方式理解或写会更容易吗？
  2. 我觉得社区正在朝着功能依赖的类型家族发展。有没有办法用它来解决这个问题？
  3. 我的一部分想知道该fisherYates函数是否可以以Shuffle某种方式移动到类型类中。是否有可能和/或值得这样做，以便您实现shuffle或同时实现indicesand reorganize？

谢谢！

4

1 回答 1

5

您可能想查看repa，它提供了n维数组，这些数组将它们的形状（维度）编码为类型；您可以使用它编写适用于任何形状数组的通用操作。

backpermute我认为您可以通过使用or构造数组并转换索引来完全避免类型类fromFunction（它比看起来更有效，因为当您强制它时它会变成一个未装箱的数组；实际上，backpermute是在幕后实现fromFunction的）。

repa 本身使用了相当多的语言扩展，但您可能会发现它比标准库的数组更可取，因为性能（repa 的数组未装箱，并且提供的标准操作可以做一些很好的事情，例如自动并行化）和方便（IMO repa 有一个比标准数组更好的 API）。

这是对 repa 的一个很好的介绍。

诚然，这些都不能直接简化您的代码。但是，如果 repa 的数组非常适合您，那么您最终得到的代码可能会避免您当前解决方案的许多复杂性。

也就是说，将你对函数依赖的使用变成一个类型族非常简单；班级Shuffle变成

class Shuffle a where
  type Elt a
  indices    :: a -> Array Int (Elt a)
  reorganize :: a -> Array Int (Elt a) -> a

实例变为

instance (Ix ix) => Shuffle (Array ix e) where
  type Elt (Array ix e) = ix
  ...

并且Shuffle a b约束变为Shuffle a。

于 2011-12-22T00:26:02.570 回答