Haskell: mélange de données sans dépendances fonctionnelles

Question

J'essaie d'implémenter un mélange de données de Fisher-Yates. Cet algorithme est facile à implémenter pour les tableaux unidimensionnels. Cependant, je dois être capable de mélanger les données dans une matrice bidimensionnelle. Une approche que je pense pouvoir généraliser aux tableaux de plus grandes dimensions est de convertir ma matrice arbitrairement dimensionnée en un tableau d'indices unidimensionnel, de mélanger ceux-ci, puis de réorganiser la matrice en échangeant l'élément à chaque index de cet index. array avec l'élément à l'index de l'élément du tableau d'index. En d'autres termes, prendre une matrice 2x2 tels que:

1 2 
3 4 

je serais convertir en ce « tableau »:

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

cela, je puis bousculade par la normale dans, disons,

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

Une fois réorganisée, la matrice d'origine deviendrait:

2 3 
4 1 

Mon approche de base est ici que je veux avoir une classe de type qui ressemble à ceci:

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

Ensuite, je vais avoir une fonction pour effectuer la lecture aléatoire qui ressemble à ceci:

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

la pensée est que (moins la plomberie RandomGen) Je devrais être capable de mélanger une chose shuffleable comme ceci:

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

Voici ce que j'ai jusqu'à présent:

{-# 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 

Mes problèmes:

1. Je me sens comme cela est beaucoup d'extensions de langage pour résoudre un problème simple. Serait-il plus facile de comprendre ou d'écrire d'une autre manière? J'ai l'impression que la communauté évolue vers des familles de types plutôt que des dépendances fonctionnelles. Y a-t-il un moyen d'utiliser cela pour résoudre ce problème?
2. Une partie de moi se demande si la fonction fisherYates peut être déplacée d'une façon ou d'une autre dans la classe Shuffle. Serait-il possible et/ou utile de mettre en place ceci afin que vous puissiez implémenter shuffle ou implémenter à la fois indices et reorganize?

Merci!

Answer 1

Vous pouvez regarder dans repa, qui offre n tableaux qui codent leurs -dimensionnelle forme (dimensions) dans le type; vous pouvez coder des opérations génériques qui fonctionnent sur des tableaux de n'importe quelle forme avec.

Je pense que vous pourriez éviter une classe de types entièrement en construisant le tableau avec backpermute ou fromFunction et traduire les indices (il est plus efficace qu'il n'y paraît, car il se transforme en un tableau Unboxed lorsque vous forcez, en fait, backpermute est mis en œuvre en termes de fromFunction sous le capot). Repa lui-même utilise quelques extensions de langage, mais vous pouvez préférer les tableaux de la bibliothèque standard pour des raisons de performance (les tableaux de repa sont décompactés, et les opérations standard offertes font de bonnes choses comme la parallélisation automatique) et la commodité (IMO repa a une API plus agréable que les tableaux standard).

Voici une bonne introduction to repa.

Certes, rien de tout cela ne simplifie directement votre code. Mais si les tableaux de repa vous conviennent, alors le code que vous obtiendrez évitera probablement beaucoup des complexités de votre solution actuelle. Cela dit, transformer votre utilisation des dépendances fonctionnelles en une famille de types est vraiment simple; la classe Shuffle devient

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

l'instance devient

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

et la contrainte Shuffle a b devient Shuffle a.