Haskell: создавать различные представления для тех же данных

Question

Предположим, что у меня есть некоторые данные, которые организованы в виде сетки, как это (размеры могут варьироваться, но сторона сетки всегда n**2):

0 1 2 3 
4 5 6 7 
8 9 A B 
C D E F 

Что я хотел бы добиться того, чтобы иметь список с теми же данными, представленными различными способами, т.е. разбить на колонки, строки, или (что самое главное) клетки, который

0 1 | 2 3 
4 5 | 6 7 
----+---- 
8 9 | A B 
C D | E F 

Так что, если я какое-то действие, я буду в состоянии получить данные в виде следующего списка:

[[0, 1, 4, 5], 
[2, 3, 6, 7], 
[8, 9, C, D], 
[A, B, E, F]] 

Если заказ не имеет значения.

Я хотел бы использовать это, чтобы позже построить объектив, который сможет устанавливать значения с учетом различных видов представлений. Это то, что могло бы быть достигнуто с использованием указателей или ссылок на императивных языках (где это применимо).

Помимо особенностей, я хотел бы знать, существует ли общий подход к представлению одинаковых внутренних данных по-разному.

Вот что я до сих пор, используя [Int] в качестве внутреннего представления и функции преобразования, чтобы получить конкретные «мнения»:

import Data.List (transpose) 

data Access = Rows | Columns | Cells 

isqrt :: Int -> Int 
isqrt = floor . sqrt . fromIntegral 

group :: Int -> [a] -> [[a]] 
group _ [] = [] 
group n l 
    | n > 0 = (take n l) : (group n (drop n l)) 
    | otherwise = error "inappropriate n" 

representAs :: [Int] -> Access -> [[Int]] 
representAs list Rows = group (isqrt . length $ list) list 
representAs list Columns = transpose $ list `representAs` Rows 
representAs list Cells = let row_width = isqrt . length $ list 
           cell_width = isqrt row_width 
           drops = map (\x -> cell_width 
                * row_width 
                * (x `quot` cell_width) 
               + cell_width 
                * (x `rem` cell_width) 
              ) [0..row_width-1] 
          in (map ((map snd) 
            . (filter ((==0) 
               . (`quot` cell_width) 
               . (`rem` row_width) 
               . fst) 
            ) 
            . (zip [0..]) 
            . (take (row_width * cell_width)) 
            . (`drop` list) 
            ) drops 
           ) 

main = mapM_ (putStrLn . show) ([1..16] `representAs` Cells) 

Мой вопрос основан на той же идее, this one, но ответа там считает только проблемы с памятью, а не строительство. Кроме того, если я хочу хранить одни и те же данные по-разному в нескольких представлениях, мне придется обновить их все, установив новое значение, насколько я понимаю.

Answer 1

Прежде всего, как user2407038 имеет упомянутых в комментариях, List - не очень эффективная структура данных, особенно для того, что вы пытаетесь сделать. Поэтому я предоставил реализацию, используя пакет Vector от vector, который, очевидно, имеет преимущество постоянного поиска времени.

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

В реализации ниже он всегда хранит данные как квартиру Vector и позволяет всем функциям, действующим на MyGrid, принимать во внимание текущее представление Access.Вероятно, вы предпочтете передать Access в функции, вместо того чтобы сделать его частью типа данных MyGrid, но я сделал этот выбор просто для простоты.

import qualified Data.Vector as V 

data Access = Rows | Columns | Cells 

data MyGrid a = MyGrid { side :: Int -- square grid with each side = N 
         , view :: Access 
         , vect :: V.Vector a } 

Такой подход позволяет создавать собственные конструктор, которые делают все проверки вменяемости, например:

-- | Constructs a grid from a list, while making sure no elements are lost. 
fromList :: [a] -> Access -> MyGrid a 
fromList ls a = MyGrid { side = if side'*side' == length ls 
           then if even side' 
            then side' 
            else error "grid cannot be split in the middle" 
           else error "list cannot be represented as a square grid" 
         , view = a 
         , vect = V.fromList ls } where 
    side' = floor . sqrt . fromIntegral . length $ ls 

другой конструктор мог быть один, который использует функцию для создания элементов с использованием индексов сетки и текущего представления:

fromFunction :: Int -> Access -> ((Int, Int) -> a) -> MyGrid a 

Теперь, вот самая важная часть, которая заботится о представлении, которое извлечения элемент п ром сетки:

index :: MyGrid a -> (Int, Int) -> a 
index grid (i, j) = 
    case view grid of 
    Rows -> vect grid V.! (i * side grid + j) 
    Columns -> vect grid V.! (j * side grid + i) 
    Cells -> vect grid V.! if even i then k else k - d where 
     n = side grid 
     d = n `div` 2 
     k = (i + j `div` d) * n + j `mod` d 

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

toLists :: MyGrid a -> [[a]] 
toLists grid = map (map (index grid)) [[(j, i) | i <- [0..n]] | j <- [0..n]] 
    where n = side grid - 1 

instance Show a => Show (MyGrid a) where 
    show grid = unlines . map show $ toLists grid 

instance Functor MyGrid where 
    fmap f grid = grid { vect = V.map f $ vect grid} 

который теперь позволяет вам иметь дело с текущим представлением MyGrid «s (за счет использования show, fmap и т.д.):

λ> fromList [0..15] Rows 
[0,1,2,3] 
[4,5,6,7] 
[8,9,10,11] 
[12,13,14,15] 

λ> succ <$> fromList [0..15] Columns 
[1,5,9,13] 
[2,6,10,14] 
[3,7,11,15] 
[4,8,12,16] 

λ> fromList [0..15] Cells 
[0,1,4,5] 
[2,3,6,7] 
[8,9,12,13] 
[10,11,14,15] 

Вот что я сделал о том, как разделить ячейки на сетку со стороной больше, чем 4. Может быть, сетка должна иметь сторону с 2, возможно, ячейки должны быть 2 от 2, я не мог сделать вывод. Просто настроить математику к тому, что вам нужно, но я решил разделить большие сетки для Cells таким образом:

0 1 2 | 3 4 5 
6 7 8 | 9 10 11 
---------+--------- 
12 13 14 | 15 16 17 
18 19 20 | 21 22 23 
---------+--------- 
24 25 26 | 27 28 29 
30 31 32 | 33 34 35 

Если вам нужна дополнительная помощь с правильной ячейкой расщеплением, редактировать этот вопрос с некоторыми примерами, как это должно быть сделано и я отрегулирую реализацию.

Answer 2

неэффективная реализация возможно вызвать лучшие идеи

column,row :: Int -> [((Int,Int),a)] -> [a] 
column n xs = map snd $ filter (\((_,y),_) -> y==n) xs 
row n xs = map snd $ filter (\((x,_),_) -> x==n) xs 

cell :: Int -> Int -> [((Int,Int),a)] -> [a] 
cell n m xs = map snd $ filter (\((x,y),_) -> (div x 2 == n) && (div y 2==m)) xs 

здесь индексировать элементы 4x4 матрицы

> let a = zipWith (\x y -> ((div y 4,mod y 4),x)) [0..15] [0..] 

клетки 2х2 блоков

> cell 1 1 a 
[10,11,14,15] 

> cell 0 0 a             
[0,1,4,5] 

> column 2 a     
[2,6,10,14] 

> row 1 a 
[4,5,6,7] 

Answer 3

Для последующей и будущей ссылки я опубликую реализацию на основе собранных идей. Весь ответ - это программа literate Haskell и может быть сохранена как *.lhs и запускаться (хотя из-за форматирования ей потребуются дополнительные строки для разделения кода и текста).

> {-# LANGUAGE TemplateHaskell, FlexibleContexts #-} 

> import Control.Lens (makeLenses, lens, (^.), ix, (.~), (.=), (^?), (%~)) 

> import qualified Data.Vector as V 
> import Data.Vector.Lens (sliced) 

> import Data.Maybe (fromJust) 
> import Data.Function ((&)) 
> import Data.List (sortBy) 

Представление данных аксессор:

• Клетки неперекрывающихся квадратов таким образом, что число элементов в каждом равно стороне сетки;
• Строки - это просто данные, разделенные на куски длины стороны сетки;
• Столбцы представляют собой строки, транспонированные.

> data Access = Rows | Columns | Cells

Структура данных сама по себе, представление образца будет

1 2 3 | 4 5 6 | 7 8 9 
10 11 12 | 13 14 15 | 16 17 18 
19 20 21 | 22 23 24 | 25 26 27 
---------+----------+--------- 
28 29 30 | 31 32 33 | 34 35 36 
37 38 39 | 40 41 42 | 43 44 45 
46 47 48 | 49 50 51 | 52 53 54 
---------+----------+--------- 
55 56 57 | 58 59 60 | 61 62 63 
64 65 66 | 67 68 69 | 70 71 72 
73 74 75 | 76 77 78 | 79 80 81 

В случае, когда одна ячейка, например,

1 2 3 
10 11 12 
19 20 21 

В ячейке всегда содержится столько же элементов, сколько строка или столбец.

> data MyGrid a = MyGrid { _cell :: Int -- size of cell in grid, whole grid 
>          -- is a square of width `cell^2` 
>      , _vect :: V.Vector a -- internal data storage 
>      } 
> makeLenses ''MyGrid 

Преобразование 2D индекс данного представления и размера ячейки внутренней

> reduce_index_dimension :: Access -> Int -> (Int, Int) -> Int 
> reduce_index_dimension a s (x,y) = 
> case a of 
>  Cells -> (y`rem`s) 
>    + (x`rem`s) * s 
>    + (y`quot`s) * s^2 
>    + (x`quot`s) * s^3 
>  Rows -> x * s * s + y 
>  Columns -> y * s * s + x 

Преобразование внутренний индекс для данного представления и размера ячейки в 2D

> increase_index_dimension :: Access -> Int -> Int -> (Int, Int) 
> increase_index_dimension a s i = 
> case a of 
>  Cells -> (s * i `quot` s^3 
>    +  (i `rem` s^2) `quot` s 
>    , s * ((i `quot` s^2) `rem` s) 
>    +  i `rem` s ) 
>  Rows -> (i `rem` s^2 
>    , i `quot` s^2) 
>  Columns -> (i `quot` s^2 
>    , i `rem` s^2) 

Создаёт сетку из списка, при этом убедитесь, что элементы не потеряны.

> fromList :: [a] -> MyGrid a 
> fromList ls = MyGrid { _cell = if side'^2 == length ls 
>        then if cell'^2 == side' 
>          then cell' 
>          else error "can't represent cell as a square" 
>        else error "can't represent list as a square" 
>      , _vect = V.fromList ls } where 
> side' = floor . sqrt . fromIntegral . length $ ls -- grid width 
> cell' = floor . sqrt . fromIntegral $ side'  -- cell width 

Преобразовать данное представление внутренней

> convert :: Access -> [[a]] -> [a] 
> convert from list = map snd 
>     . sortBy compare_index 
>     . map reduce_index 
>     . concatMap prepend_index 
>     . zip [0..] $ list 
> where 
>  size      = floor . sqrt . fromIntegral . length $ list 
>  prepend_index (a, xs)  = zipWith (\b c -> ((a, b), c)) [0..] xs 
>  reduce_index (i, x)  = (reduce_index_dimension from size i, x) 
>  compare_index (i, _) (j, _) = compare i j 

Создаёт сетку из другой сетки, принимая представление во внимание

> fromListsAs :: Access -> [[a]] -> MyGrid a 
> fromListsAs a l = MyGrid { _cell = if allEqualLength l 
>         then if cell'^2 == side' 
>           then cell' 
>           else error "can't represent cell as a square" 
>         else error "lists have different length or do not fit" 
>       , _vect = V.fromList . convert a $ l } where 
> side' = length l 
> cell' = floor . sqrt . fromIntegral $ side'  -- cell width 
> allEqualLength xs = and $ map ((== side') . length) (tail xs) 

комбинируя линзы более того же объекта, см Haskell use first level lenses to create complex lens

> (x ^>>= f) btofb s = f (s ^. x) btofb s 

линзы фокусировки на элементе poited в данном представлении с данным 2d индекс

> lens_as a i = cell ^>>= \s -> vect . sliced (reduce_index_dimension a s i) 1 . ix 0 

обращенного в 2d представления

> toListsAs :: MyGrid a -> Access -> [[a]] 
> toListsAs g a = [[fromJust $ g^?(lens_as a (x, y)) | y <- [0..n]] | x <- [0..n]] 
> where n = (g^.cell)^2 - 1 

по умолчанию

> toLists :: MyGrid a -> [[a]] 
> toLists g = g `toListsAs` Rows 

> instance Show a => Show (MyGrid a) where 
> show grid = unlines . map show . toLists $ grid 

> instance Functor MyGrid where 
> fmap f grid = grid & vect %~ V.map f 

здравомыслие проверка

> main = mapM_ (putStrLn . show) (fromList [0..(+80)0] `toListsAs` Cells)