Haskell: barajando datos sin dependencias funcionales

Question

Estoy tratando de implementar una mezcla de algunos datos de Fisher-Yates. Este algoritmo es fácil de implementar para matrices unidimensionales. Sin embargo, necesito poder mezclar los datos en una matriz bidimensional.

Un enfoque que creo que se podría generalizar a matrices de mayor dimensión es convertir mi matriz arbitrariamente dimensionada en una matriz de índices de una sola dimensión, mezclarlos y reorganizar la matriz intercambiando el elemento en cada índice de este índice array con el elemento en el índice del elemento de la matriz de índice. En otras palabras, para tomar una matriz 2x2, tales como:

1 2 
3 4 

que sería convertir esto en esta "matriz":

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

Esto lo haría entonces lucha por la normalidad en, digamos,

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

Una vez reorganizado, la matriz original se convertiría en:

2 3 
4 1 

Mi enfoque básico aquí es que quiero tener una clase de tipo que se ve algo como esto:

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

entonces tendré una función para realizar la reproducción aleatoria, que se ve así:

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

la idea es que (menos la plomería RandomGen) que debería ser capaz de mezclar una cosa shuffleable así:

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

Esto es lo que tengo hasta ahora:

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

Mis problemas:

1. Siento que este es un montón de extensiones de lenguaje para resolver un problema sencillo. ¿Sería más fácil de entender o escribir de otra manera?
2. Siento que la comunidad se está moviendo hacia familias tipo sobre dependencias funcionales. ¿Hay alguna manera de usar eso en su lugar para resolver este problema?
3. Una parte de mí se pregunta si la función fisherYates se puede mover de alguna manera a la clase de tipo Shuffle. ¿Sería posible y/o valioso hacer esto para que implemente shuffle o implemente indices y reorganize?

¡Gracias!

Answer 1

Es posible que desee ver en repa, que ofrece n matrices dimensionales que codifican sus forma (dimensiones) en el tipo; puede codificar operaciones genéricas que funcionan en matrices de cualquier forma con él.

Creo que se podría evitar una clase de tipos en su totalidad por la construcción de la matriz con backpermute o fromFunction y la traducción de los índices (que es más eficiente de lo que parece, ya que se convirtió en una matriz sin caja cuando lo fuerzas, de hecho, backpermute es implementado en términos de fromFunction debajo del capó).

Repa sí mismo utiliza varias extensiones de idioma, pero es posible que prefiera las matrices de la biblioteca estándar por razones de rendimiento (las matrices Repa no están incluidas y las operaciones estándar ofrecen cosas agradables como la paralelización automática) y la conveniencia (La reparación de IMO tiene una API más agradable que las matrices estándar).

Aquí hay una buena introduction to repa.

Es cierto que nada de esto simplifica directamente su código. Pero si las matrices de repa son una buena opción para ti, entonces el código que acabes probablemente evitará muchas de las complejidades de tu solución actual.

---

Dicho esto, convertir el uso de dependencias funcionales en una familia de tipos es realmente simple; la clase se convierte en Shuffle

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

la instancia se convierte en

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

y la restricción se convierte en Shuffle a bShuffle a.