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

然后我将有一个函数来执行看起来像这样的shuffle:

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本身使用了相当多的语言扩展,但你可能会发现它比标准库的数组更好,原因在于性能(修复数组是未装箱的,提供的标准操作可以做很好的事情,如自动并行化)和方便(IMO repa有一个比标准数组更好的API).

这是对修复的一个很好的介绍.

不可否认,这些都不会直接简化您的代码.但是如果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.