Haskell: xáo trộn dữ liệu mà không cần phụ thuộc chức năng

Question

Tôi đang cố gắng triển khai ngẫu nhiên một số dữ liệu của Fisher-Yates. Thuật toán này dễ thực hiện đối với mảng một chiều. Tuy nhiên, tôi cần có khả năng trộn dữ liệu trong ma trận hai chiều. Một cách tiếp cận mà tôi cho rằng có thể khái quát hóa các mảng chiều cao hơn là chuyển đổi ma trận có kích thước tùy ý của tôi thành một mảng chỉ số một chiều, trộn lẫn, và sắp xếp lại ma trận bằng cách hoán đổi phần tử tại mỗi chỉ mục của chỉ mục này mảng với phần tử ở chỉ mục của phần tử của mảng chỉ mục. Nói cách khác, để có một ma trận 2x2 như:

1 2 
3 4 

tôi sẽ chuyển đổi này thành "mảng" này:

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

nay tôi sau đó sẽ tranh giành mỗi bình thường thành, nói,

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

Khi tái tổ chức, ma trận ban đầu sẽ trở thành:

2 3 
4 1 

tiếp cận cơ bản của tôi ở đây là tôi muốn có một lớp học kiểu đó trông giống như sau:

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

Sau đó, tôi sẽ có một chức năng để thực hiện các shuffle mà trông như thế này:

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

những suy nghĩ là (trừ RandomGen ống nước) tôi sẽ có thể xáo trộn một điều shuffleable như vậy:

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

Dưới đây là những gì tôi có cho đến nay:

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

vấn đề của tôi:

1. tôi cảm thấy như thế này là rất nhiều phần mở rộng ngôn ngữ để giải quyết một vấn đề đơn giản. Nó sẽ dễ hiểu hay viết theo cách khác?
2. Tôi cảm thấy như cộng đồng đang di chuyển theo hướng gia đình loại trên các phụ thuộc chức năng. Có cách nào để sử dụng thay vào đó để giải quyết vấn đề này không?
3. Một phần của tôi tự hỏi nếu chức năng fisherYates có thể được chuyển vào kiểu chữ Shuffle bằng cách nào đó không. Có thể và/hoặc có giá trị để thiết lập điều này để bạn thực hiện shuffle hoặc triển khai cả hai indices và reorganize?

Cảm ơn!

Answer 1

Bạn có thể muốn nhìn vào repa, trong đó cung cấp n mảng chiều mà mã hóa của họ hình (kích thước) vào loại; bạn có thể mã hóa các hoạt động chung hoạt động trên các mảng của bất kỳ hình dạng nào với nó.

Tôi nghĩ rằng bạn có thể tránh được một typeclass hoàn toàn bằng cách xây dựng các mảng với backpermute hoặc fromFunction và dịch các chỉ số (đó là hiệu quả hơn có vẻ, vì nó được biến thành một mảng không có hộp bọc khi bạn buộc nó, trong thực tế, backpermute là thực hiện theo điều khoản của fromFunction dưới mui xe).

repa tự sử dụng một vài phần mở rộng ngôn ngữ, nhưng bạn có thể thấy nó thích hợp hơn với mảng chuẩn của thư viện vì lý do cả hai hiệu suất (mảng của repa không được đóng hộp, và các hoạt động chuẩn được cung cấp làm những việc tốt đẹp như tự động song song) và tiện lợi (IMO repa có một API đẹp hơn các mảng chuẩn).

Dưới đây là một tốt introduction to repa.

Phải thừa nhận rằng, không ai trong số này trực tiếp đơn giản hoá mã của bạn. Nhưng nếu mảng của repa phù hợp với bạn, thì mã bạn kết thúc sẽ có thể tránh được nhiều sự phức tạp của giải pháp hiện tại của bạn.

---

Điều đó nói rằng, việc bạn sử dụng các phụ thuộc chức năng vào một nhóm người thực sự đơn giản; lớp Shuffle trở thành

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

trường hợp trở thành

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

và Shuffle a b hạn chế trở nên Shuffle a.