Безопасность создания вектора

Question

Этот вопрос на самом деле представляет собой небольшую решетку очень тесно связанных вопросов; Я не думаю, что есть смысл разбивать его еще.

Один из фундаментальных способов создания Vector использует unsafeFreeze, Как следует из названия, unsafeFreeze действительно небезопасно. В частности, ничто не мешает MVector перешел к unsafeFreeze от изменения после того, как он заморожен. Это приводит к двум различным проблемам:

1. Это может привести к изменению значения неизменных векторов. Это всего лишь жуткий поступок на расстоянии, который Хаскелл обычно избегает.

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

vector Пакет [1] предлагает два эффективных, казалось бы, безопасных примитива для создания неизменяемых векторов: create а также createT:

create :: (forall s. ST s (MVector s a)) -> Vector a
createT :: Traversable t => (forall s. ST s (t (MVector s a))) -> t (Vector a)

Игнорируя бизнес слияния векторов, основные реализации выглядят как

create m = runST $ m >>= unsafeFreeze
createT m = runST $ m >>= traverse unsafeFreeze

create довольно явно безопасно. Он запускает данный ST s действие, которое должно создать свежий MVector s (тип runST гарантирует, что он не может использовать существующий, а также гарантирует, что fixST не может играть какие-либо забавные трюки), замораживает его и возвращает замороженный вектор.

createT довольно ясно, когда Traversable инстанция законна. Со списками, например, createT m запускает действие, производящее список MVector с, затем замораживает их всех. Параметричность в s тогда кажется достаточным, как для create, чтобы ничего плохого не случилось. Обратите внимание, что действие может создать список с несколькими копиями одного и того же MVector, Они будут заморожены дважды, но в этом не должно быть никакого вреда. законная Traversable все экземпляры очень похожи на оформленные списки, поэтому они должны вести себя одинаково. Теперь я наконец дошел до своего первого вопроса:

Является createT безопасно при использовании с незаконным Traversable пример?

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

Один очевидный способ обобщения createT позволяет пользователю передавать свою собственную функцию обхода:

createTOf
  :: (forall f x y. Applicative f => (x -> f y) -> t x -> f (u y))
  -> (forall s. ST s (t (MVector s a))) -> u (Vector a)
createTOf trav m = runST $ m >>= trav unsafeFreeze

Обратите внимание, что я позволил обходу изменить тип контейнера с t в u, Это позволяет пользователю, например, произвести Vector (MVector s a) но верни [Vector a], когда t ~ u это очевидно так же безопасно, как createT с незаконным Traversable пример. Уменьшает ли дополнительная гибкость изменения типа "контейнера" безопасность? Редактировать: я только что понял, что могу ответить на этот вопрос: нет, это не имеет значения. См. [2] ниже для объяснения.

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

traverse f <$> createT m

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

createTOfThen
  :: Applicative g
  => (forall f x y. Applicative f => (x -> f y) -> t x -> f (u y))
  -> (Vector a -> g b)
  -> (forall s. ST s (t (MVector s a)))
  -> g (u b)
createTOfThen trav f m =
  runST $ m >>= getCompose . trav (Compose . fmap f . unsafeFreeze)

Является createTOfThen безопасно, если trav не законный обход?

---

Я сказал, что буду говорить о решетке, верно? Следующий вопрос - насколько (если вообще) мы можем ослабить полиморфизм обхода, не создавая проблем. Все будет перепроверяться, даже если обход должен быть только полиморфным в s, но это, очевидно, небезопасно, так как может чередовать зависание с модификацией, как ему нравится. Выявление того, что конечный результат имеет место Vector значения, вероятно, достаточно безвредны, но мы, конечно, не можем дать понять, что он работает в ST s и что это обрабатывает MVector s a ценности. Но можем ли мы дать ему знать об одном из этих фактов? Исправление Applicative наверняка будет полезно:

createTOf'
  :: (forall s x y. (x -> ST s y) -> t x -> ST s (u y))
  -> (forall s. ST s (t (MVector s a))) -> u (Vector a)

createTOfThen'
  :: Applicative g
  => (forall s x y. (x -> Compose (ST s) g y) -> t x -> Compose (ST s) g (u y))
  -> (Vector a -> g b)
  -> (forall s. ST s (t (MVector s a)))
  -> g (u b)

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

С другой стороны, я подозреваю, что мы можем сообщить об обходе MVector s... до тех пор, пока мы не дадим ему понять, с каким потоком состояний они связаны. Этого достаточно, чтобы распаковать их, а также (возможно, к сожалению), чтобы получить их размеры.

Редактировать! Если прохождение позволено знать, что он производит Vector s (что выглядит как наименее вероятная вещь, которая может быть проблематичной), то createTOfThen может быть реализовано с точки зрения createTOf:

createTOfThen trav post m = getConst $
  createTOf (\f ->
    fmap Const . getCompose . (trav (Compose . fmap post . f))) m

---

Взяв решетку в третьем направлении, давайте перейдем к обходам ранга 2. rank2classes пакет предлагает свой Traversable класс, который я назову R2.Traversable:

class (R2.Functor g, R2.Foldable g) => R2.Traversable g where
  R2.traverse :: Applicative m
              => (forall a. p a -> m (q a))
              -> g p -> m (g q)

Мы можем играть в одни и те же игры, чтобы получить гетерогенные контейнеры Vector s:

createTHet
  :: R2.Traversable t
  => (forall s. ST s (t (MVector s)))
  -> t Vector
createTHet m = runST $ m >>= R2.traverse unsafeFreeze

createTHetOf
  :: (forall h f g.
       (Applicative h => (forall x. f x -> h (g x)) -> t f -> h (u g)))
  -> (forall s. ST s (t (MVector s)))
  -> u Vector
createTHetOf trav m = runST $ m >>= trav unsafeFreeze

createTHetOfThen
  :: Applicative q
  => (forall h f g.
       (Applicative h => (forall x. f x -> h (g x)) -> t f -> h (u g)))
  -> (forall x. Vector x -> q (r x))
  -> (forall s. ST s (t (MVector s)))
  -> q (u r)
createTHetOfThen trav post m =
    runST $ m >>= getCompose . trav (Compose . fmap post . unsafeFreeze)

наряду с аналогичными версиями, где обход разрешается знать, что он работает в ST s, Я предположил бы, что свойства безопасности версий ранга 2 идентичны свойствам соответствующих версий ранга 1, но я понятия не имею, как можно доказать это.

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

createTHetOfThen'
  :: (forall s1 s2.
       ((forall x. MVector s2 x -> Compose (ST s1) q (r x)) -> t (MVector s2) -> Compose (ST s1) q (u r)))
  -> (forall x. Vector x -> q (r x))
  -> (forall s. ST s (t (MVector s)))
  -> q (u r)
createTHetOfThen' trav post m =
    runST $ m >>= getCompose . trav (Compose . fmap post . unsafeFreeze)

---

[1] Я связался со Stackage, потому что Hackage сегодня не работает. Если я вспомню и успею, я исправлю ссылки позже.

[2] Доказательство исходит от Data.Functor.Sum, Учитывая неизменяющий тип createTOfSame мы можем написать

createTOf
  :: (forall f a b. Applicative f => (a -> f b) -> t a -> f (u b))
  -> (forall s. ST s (t (MVector s a)))
  -> u (Vector a)
createTOf trav m =
  case createTOfSame (\f (InL xs) -> InR <$> trav f xs)
                     (InL <$> m) of
    InR u -> u

Это на самом деле будет полным, хотя "обход" является частичным: мы всегда находим совпадение с тем, что мы обязательно найдем.

Answer 1

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

createTOf
  :: (forall s1 s2.
       (MVector s1 a -> ST s2 (Vector a))
       -> t (MVector s1 a) -> ST s2 (u (Vector a)))
  -> (forall s. ST s (t (MVector s a)))
  -> u (Vector a)
createTOf trav m = runST $ m >>= trav unsafeFreeze

Это, конечно, довольно полный набор сигнатур! Давайте сосредоточимся на безопасности, о которой мы заботимся: что нет MVector мутирует после того, как замерз. Первое, что мы делаем, это бегаем m производить что-то типа t (MVector s a),

t сейчас очень загадочно. Это контейнер? Это какое-то действие, которое производит векторы? Мы не можем сказать ужасно много о том, что это такое, но мы можем сказать кое-что о том, что это такое. trav unsafeFreeze не могу с этим поделать. Давайте начнем с разрыва типа подписи trav:

trav :: forall s1 s2.
        (MVector s1 a -> ST s2 (Vector a))
     -> t (MVector s1 a) -> ST s2 (u (Vector a)))

trav витки t (MVector s1 a) в ST s2 (u (Vector a)), Если t содержит векторы, то эти векторы живут в потоке состояний s1, Результатом, однако, является действие в потоке состояний s2, Так trav не может изменить MVectorЭто дается с использованием обычных операций. Он может применять только ту функцию, которая ему нужна (которая будет unsafeFreeze) и использовать любые машины, на которых можно ездить t, На каких машинах можно ездить? t? Ну, вот глупый пример:

data T :: Type -> Type where
  T :: [ST s (MVector s a)] -> t (MVector s a)

Мог trav чередовать эти ST действия с зависаниями? Нет! Те ST действия соответствуют MVectors, но они не соответствуют потоку состояний trav работает в. Так trav не могу ничего с ними сделать.