Haskell: mischiare dati senza dipendenze funzionali

Question

Sto provando ad implementare un rimescolamento di alcuni dati da parte di Fisher-Yates. Questo algoritmo è facile da implementare per gli array monodimensionali. Tuttavia, ho bisogno di essere in grado di mescolare i dati in una matrice bidimensionale.

Un approccio che a mio avviso potrebbe generalizzare meglio ad array di dimensioni superiori è convertire la matrice arbitrariamente dimensionata in una matrice di indici unidimensionale, mescolarli e quindi riorganizzare la matrice scambiando l'elemento in ciascun indice di questo indice array con l'elemento nell'indice dell'elemento dell'array di indice. In altre parole, di prendere una matrice 2x2 quali:

1 2 
3 4 

Vorrei convertirlo in questa "matrice":

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

Questa avrei poi scramble per normale in, diciamo,

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

volta riorganizzata, matrice origine diventerebbe:

2 3 
4 1 

Il mio approccio di base è che voglio avere una classe tipo che sembra qualcosa di simile:

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

Allora dovrò una funzione per eseguire la riproduzione casuale che assomiglia a questo:

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

il pensiero è che (meno la randomgen impianto idraulico) dovrei essere in grado di mescolare una cosa shuffleable in questo modo:

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

Ecco quello che ho finora:

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

I miei problemi:

1. Mi sento come questo è un sacco di estensioni del linguaggio per risolvere un problema semplice. Sarebbe più facile capire o scrivere in un altro modo?
2. Mi sento come se la comunità si stesse spostando verso famiglie di tipi su dipendenze funzionali. C'è un modo per usarlo invece per risolvere questo problema?
3. Una parte di me si chiede se la funzione fisherYates possa essere spostata in qualche modo nella classe di caratteri Shuffle. Sarebbe possibile e/o vale la pena farlo per impostare questo in modo da implementare shuffle o implementare entrambi indices e reorganize?

Grazie!

Answer 1

Si potrebbe voler esaminare repa, che offre n array -dimensionale che codificano i loro forma (dimensioni) nel tipo; puoi codificare operazioni generiche che funzionano su array di qualsiasi forma con esso.

Credo si possa evitare una typeclass interamente costruendo la matrice con backpermute o fromFunction e traducendo gli indici (è più efficiente di quanto sembri, dato che viene trasformato in un array unboxed quando si forza, infatti, backpermute è implementato in termini di fromFunction sotto il cofano).

repa utilizza alcune estensioni di lingua, ma potrebbe essere preferibile agli array della libreria standard per motivi di entrambe le prestazioni (gli array di repa sono non inbox e le operazioni standard offerte fanno cose piacevoli come la parallelizzazione automatica) e la convenienza (IMO repa ha un'API migliore rispetto agli array standard).

Ecco un buon introduction to repa.

Certo, nessuno di questi semplifica direttamente il codice. Ma se gli array di repa si adattano bene a te, allora il codice con cui verrai probabilmente eviterà molte delle complessità della tua attuale soluzione.

---

Detto questo, trasformare l'utilizzo delle dipendenze funzionali in una famiglia di tipi è davvero semplice; la classe Shuffle diventa

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

l'istanza diventa

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

e il vincolo Shuffle a b diventa Shuffle a.