Haskell: shuffling data without functional dependencies

Question

I am trying to shuffle some data from Fisher-Yates. This algorithm is easy to implement for one-dimensional arrays. However, I need to be able to shuffle data in a two-dimensional matrix.

The approach, which, I think, can generalize well to arrays with large sizes, is to convert my matrix of arbitrary size into a one-dimensional array of indices, shuffle them, and then reorganize the matrix, replacing the element with each index of this array of indices with an element in the index of an element of an index array. In other words, take a 2x2 matrix, such as:

1 2 3 4 

I would convert this to this "array":

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

Then I would scramble normal, say

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

After the reorganization, the original matrix will become:

 2 3 4 1 

My basic approach is that I want to have a type class that looks something like this:

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

Then I will have a function to perform the shuffle, which looks like this:

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

The idea that (minus plumbing in RandomGen) I would have to shuffle a random thing like this:

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

Here is what I still have:

 {-# 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 ig arr = go (i-1) g' (swap arr ij) where (j, g') = randomR (0, i) g class Shuffle ab | a -> b where indices :: a -> Array Int b reorganize :: a -> Array Int b -> a shuffle :: (Shuffle ab, 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 ie -> i -> i -> Array ie swap arr ij = arr // [ (i, i'), (j, j') ] where i' = arr!j j' = arr!i 

My problems:

• I feel that these are many language extensions to solve a simple problem. Would it be easier to understand or write another way?
• I feel the community is moving towards type families over functional dependencies. Is there a way to use this instead to solve this problem?
• Part of me wonders if the fisherYates function fisherYates move to the Shuffle class. Would it be possible and / or worth it to do so that you either implement Shuffle or implement both indices and reorganize ?

Thanks!

Answer 1

You might want to learn repa , which offers n-dimensional arrays that encode their shape (sizes) into a type; you can encode common operations that work with arrays of any shape with it.

I think you could avoid creating the class completely by building the array using backpermute or fromFunction and translating the indices (it is more efficient than it looks, since it becomes included in the unboxed array when you force it, in fact the backpermute is implemented in terms of fromFunction under the hood).

There are quite a few language extensions in repa itself, but you can consider it preferable for standard library arrays for performance reasons (repa arrays are unpacked, and standard operations offer nice things like automatic parallelization) and convenience (IMO repa has a more convenient API than standard arrays).

Here's a good introduction to repa .

Admittedly, none of this simplifies your code. But if repa arrays are right for you, then the code you end up is likely to avoid the many complexities of your current solution.

---

However, turning the use of functional dependencies into a type family is very simple; class Shuffle becomes

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

instance becomes

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

and the Shuffle ab constraint becomes Shuffle a .