Haskell:在没有功能依赖的情况下对数据进行洗牌

Question

我正在尝试实现一些数据的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

My problems:

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

谢谢!

Answer 1

您可能需要查看雷帕，它提供了将其形状(维度)编码到类型中的n维数组；您可以编写处理任意形状数组的通用操作。

我认为您完全可以通过使用backpermute或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。