Haskell: перетасовка данных без функциональных зависимостей - PullRequest
Новая
       28

Haskell: перетасовка данных без функциональных зависимостей

7 голосов
/ 22 декабря 2011

Я пытаюсь реализовать некоторую перестановку Фишера-Йейтса. Этот алгоритм легко реализовать для одномерных массивов. Однако мне нужно иметь возможность перемешивать данные в двумерной матрице.

Подход, который, я думаю, мог бы хорошо обобщить для массивов более высокой размерности, состоит в том, чтобы преобразовать мою матрицу произвольного размера в одномерный массив индексов, перемешать их, а затем реорганизовать матрицу путем замены элемента на каждый индекс этого массива индексов. с элементом в индексе элемента индекса массива. Другими словами, взять матрицу 2x2, такую ​​как: 

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) я должен быть в состоянии перетасовать случайную вещь, например, так: 

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?

Спасибо!

1 Ответ

5 голосов
/ 22 декабря 2011

Возможно, вы захотите взглянуть на repa , который предлагает n -мерные массивы, которые кодируют их форму (размеры) в тип;Вы можете кодировать универсальные операции, которые работают с массивами любой формы с ним.

Я думаю, что вы могли бы полностью избежать класса типов, создав массив с backpermute или fromFunction и перевод индексов (это более эффективно, чем кажется, поскольку при его форсировании он превращается в распакованный массив; на самом деле, backpermute реализован в терминах fromFunction под капотом).

сама repa использует довольно много языковых расширений, но вы можете найти ее предпочтительнее массивов стандартной библиотеки по причинам как производительности (массивы repa распакованы, так и предлагаемые стандартные операции делают полезные вещи, такие как автоматическое распараллеливание) и удобства (IMOУ repa более хороший API, чем у стандартных массивов).

Вот хорошее введение в 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.

...