Haskell：沒有函數依賴關係的洗牌數據

Question

我試圖實現Fisher-Yates洗牌的一些數據。這個算法對於一維數組很容易實現。但是，我需要能夠在二維矩陣中混洗數據。

一種我認爲可以很好地推廣到更高維數組的方法是將我的任意維度的矩陣轉換爲一維索引數組，然後對這些數組進行混洗，然後通過交換此索引的每個索引處的元素來重新組織矩陣數組與索引數組元素的索引處的元素。換句話說，取2×2矩陣例如：

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管道），我應該能夠洗牌shuffleable的事情，像這樣：

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，提供ň編碼它們的形狀（尺寸）到類型維數組;您可以使用它編寫任何形狀的數組上的通用操作。

我想你可以避開類型類完全通過構建與backpermute或fromFunction陣列和翻譯指數（當你強迫它，它的效率比它看起來，因爲它就會變成一個未裝箱的陣列;事實上，backpermute是根據引擎蓋下的fromFunction實施）。由於兼顧性能（repa的陣列是unboxed的，並且提供的標準操作可以做很好的事情，比如自動並行化）和便利性（你可能會發現它比標準庫的數組更好） IMO的維修比標準陣列有更好的API）。

這是一個很好的introduction to 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。