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

我问题:

1. 我觉得这是解决一个简单问题的大量语言扩展。是更容易理解还是用另一种方式写?
2. 我觉得社区正朝着类型族而不是功能依赖的方向发展。有没有办法用它来解决这个问题呢?
3. 我想知道fisherYates函数是否可以以某种方式移动到Shuffle类型类。是否有可能和/或值得这样做，以便您要么实现shuffle，要么实现indices和reorganize ?

谢谢!

Answer 1

你可能想看看repa，它提供了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