Создание типа данных в виде сетки в haskell

Проблема

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

Мне нужно получить к нему доступ через застежку-молнию, где мой фокус - это поле (значение, так сказать). Застежка-молния должна поддерживать действия goDown, goUp, goLeft и goRight, каждый из которых меняет фокус на поле в указанном направлении, а также here, который должен возвращать значение поля в настоящее время в фокусе.

Хотя это можно сделать с помощью Map, это неэффективно в том смысле, что изменение фокуса займет log n time, n - количество элементов в Map, так как a Map имеет логарифмическое время поиска.

Мне нужно, чтобы указанные действия работали в O(1).

Пример

Для иллюстрации рассмотрим приведенную ниже матрицу. Число в скобках - это текущий фокус.

1 (2) 3
4  5  6
7  8  9

Если я применил goRight, я должен получить:

1  2 (3)
4  5  6
7  8  9

Если я применил here сейчас, возвращаемое значение должно быть 3.

Вопрос

Как бы тип данных в форме, описанной выше, выглядел в haskell? Возможно ли это как алгебраический тип данных?

Помните, что изменение фокуса во всех четырех направлениях должно выполняться в O(1) времени, а также чтение значения, которое в настоящее время находится в фокусе.

Ответ 1

Хорошо, я разочарован тем, что никто еще не дал "правильный" ответ на эту проблему, потому что я знаю, что он существует, но я не смогу это объяснить. Мой ответ основан на http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html

Прежде всего, стандартом, который является 1-й молнией, может быть:

Data U x = U [x] x [x]

первый элемент - это обратный список всех элементов, "левый" фокус, затем элемент фокусировки, затем список всех элементов "справа" фокуса. Например:.

U [-1,-2,-3] 0 [1,2,3]

Затем мы можем переместить молнию влево и вправо. Вы должны решить, что делать, когда мы убегаем от края сетки. Первоначальное сообщение просто постулировало бесконечную сетку, так что краевой регистр оставлен как упражнение для читателя.

left  (U (a:as) x zs) = U as a (x:zs)
right (U as x (z:zs)) = U (x:as) z zs

Теперь все, что выглядит как контейнер, должно быть Functor так:

instance Functor U where
  fmap f (U a x z) = U (map f a) (f x) (map f z)

В этот момент я действительно хочу, чтобы кто-то еще вошел, чтобы объяснить, что я собираюсь делать и почему. Я собираюсь сделать U экземпляр Control.Comonad. Лучшее, что я могу объяснить, это то, что комонады - это разновидность наизубых монадов. Вместо того, чтобы дать вам один элемент и попросить создать контейнер с новым значением (>>= :: Monad m => m a -> (a -> m b) -> m b), Comonads даст вам всю структуру и попросит только значение, которое принадлежит фокусу: (=>>) :: Comonad w=>w a -> (w a -> b) -> w

Итак, используя термины Control.Comonad в пакете comonad-3.0.2:

Instance Comonad U where
  -- extract :: U a -> a   -- called coreturn in the post
  extract (U _ x _) = x

  -- duplicate :: U a -> U (U a)  -- called cojoin in the post
  duplicate x = U (tail $ iterate left x) x (tail $ iterate right x)

duplicate дает вам молнию молнии, каждая из которых сдвигается влево или вправо еще одним элементом, а затем последним. Это кажется огромным объемом памяти, но Haskell ленив, и фактический объем памяти очень мал и порядка O (n) для полного набора и O (1), если вы вообще не смотрите вокруг.

Но это все в одном измерении. Опять же по причинам, я недостаточно умен, чтобы объяснить, что это расширение до двух измерений id dead easy:

data U2 x = U2 (U(U x))

instance Functor U2 where
  fmap f (U2 y) = U2 $ fmap (fmap f) y

instance Comonad U2 where
  extract (U2 y) = extract (extract y)
  duplicate (U2 y) = fmap U2 $ U2 $ roll $ role y where
    iterate' f = tail . iterate f
    role x = U (iterate' (fmap left) x) x (iterate' (fmap right) x)

Дублирующая функция теперь создает сетку сеток, каждая из которых соответственно сдвигается. Так

goLeft  u = let (U _ (U x _ _) _) = duplicate u in x
goRight u = let (U _ (U _ _ x) _) = duplicate u in x
goUp      = left  . duplicate
goDown    = right . duplicate
here      = extract

Поскольку Haskell ленив, все это O (1). Еще более интересно вы можете изменить here на O (1) стоимость как во времени, так и в памяти и использовать ячейки окрестности в вычислении. Это делает что-то вроде клеточного автомата game of life так же просто, как

rule  (U2 (U
      (U (u0:_) u1 (u2:_):_)
      (U (u3:_) u4 (u5:_))
      (U (u6:_) u7 (u8:_):_))) =
         let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in
           u4 && (n==2 || n==3) || (not u4) && n==3

-- assume u is the original graph each step is
step u = u =>> rule

В дополнение к сообщению в блоге выше, я предлагаю искать Google для Comonad, чтобы узнать больше, особенно, поскольку я не лучший, объясняя это.

Ответ 2

Возможно, это не то, о чем вы просите, но я хотел бы узнать, почему сначала предложить лучший ответ.

data GridWithZipper a = GridWithZipper { grid :: [[a]]
                                       , gwzx :: Int
                                       , gwzy :: Int
                                       }

goLeft  gwz = gwz { gwzx = gwzx gwz - 1 }
goRight gwz = gwz { gwzx = gwzx gwz + 1 }
goUp    gwz = gwz { gwzy = gwzy gwz - 1 }
goDown  gwz = gwz { gwzy = gwzx gwz + 1 }

get gwz = grid gwz !! gwzx gwz !! gwzy gwz

~~Все операции, очевидно, O(1).~~

Все операции go O(1), однако получение и настройка O(sqrt(n)).