Haskell vector С++ push_back аналог

Ответ 1

Нет такого объекта в Data.Vector. Это не так сложно реализовать с нуля, используя MutableArray, как Data.Vector.Mutable (см. Мою реализацию ниже), но есть некоторые существенные недостатки. В частности, все его операции заканчиваются внутри некоторого контекста состояния, обычно ST или IO. Это имеет недостатки, которые

• Любой код, который управляет такой структурой данных, должен быть монодичным
• Компилятор гораздо реже может оптимизировать. Например, библиотеки, такие как vector, используют что-то действительно умное, называемое fusion, чтобы оптимизировать промежуточные распределения. В государственном контексте это невозможно.
• Parallelism будет намного сложнее: в ST у меня не может быть двух потоков, а в IO у меня будут условия гонки по всему месту. Прохладный бит здесь заключается в том, что любой обмен должен произойти в IO.

Как будто все это было недостаточно, сборка мусора также лучше работает внутри чистого кода.

Что мне делать?

Не так уж часто бывает, что вам нужно именно такое поведение - обычно вам лучше использовать неизменяемую структуру данных (тем самым избегая всех вышеупомянутых проблем), что делает что-то подобное. Просто ограничиваясь containers, который поставляется с GHC, некоторые альтернативы включают в себя:

• если вы почти всегда используете push_back, возможно, вам просто нужен стек (простой старый [a]).
• если вы ожидаете делать больше push_back, чем поисковые запросы, Data.Sequence дает вам O(1) дополнение к концу и O(log n) поиск.
• Если вы заинтересованы в большом количестве операций, особенно hashmap-like, Data.IntMap довольно оптимизирован. Даже если теоретическая стоимость этих операций O(log n), вам понадобится довольно большой IntMap, чтобы начать ощущать эти расходы.

Создание чего-то типа С++ vector

Конечно, если не нужно упоминать об упомянутых выше ограничениях, нет оснований не иметь такой С++-вектор. Просто для удовольствия я пошел дальше и реализовал это с нуля (пакеты потребностей data-default и primitive).

Причина, по которой этот код, вероятно, еще не в какой-то библиотеке, заключается в том, что он противоречит большей части духа Haskell (я делаю это с намерением соответствовать вектору стиля С++).

• Единственной операцией, которая фактически создает новый вектор, является newVector - все остальное "изменяет" существующий вектор. Поскольку pushBack не возвращает новый GrowVector, он должен изменить существующий (включая его длину и/или емкость), поэтому length и capacity должны быть "указателями". В свою очередь это означает, что даже получение length является монадической операцией.
• Пока это не распакован, было бы не так сложно реплицировать vector data family подход - это просто утомительно ¹.

Сказав это:

module GrowVector (
  GrowVector, newEmpty, size, read, write, pushBack, popBack
) where 

import Data.Primitive.Array
import Data.Primitive.MutVar
import Data.Default
import Control.Monad
import Control.Monad.Primitive (PrimState, PrimMonad)
import Prelude hiding (length, read)

data GrowVector s a = GrowVector
  { underlying :: MutVar s (MutableArray s a) -- ^ underlying array
  , length :: MutVar s Int                    -- ^ perceived length of vector
  , capacity :: MutVar s Int                  -- ^ actual capacity
  }

type GrowVectorIO = GrowVector (PrimState IO)

-- | Make a new empty vector with the given capacity. O(n)
newEmpty :: (Default a, PrimMonad m) => Int -> m (GrowVector (PrimState m) a)
newEmpty cap = do
  arr <- newArray cap def
  GrowVector <$> newMutVar arr <*> newMutVar 0 <*> newMutVar cap

-- | Read an element in the vector (unchecked). O(1)
read :: PrimMonad m => GrowVector (PrimState m) a -> Int -> m a
g `read` i = do arr <- readMutVar (underlying g); arr `readArray` i

-- | Find the size of the vector. O(1)
size :: PrimMonad m => GrowVector (PrimState m) a -> m Int
size g = readMutVar (length g)

-- | Double the vector capacity. O(n)
resize :: (Default a, PrimMonad m) => GrowVector (PrimState m) a -> m ()
resize g = do
  curCap <- readMutVar (capacity g)         -- read current capacity
  curArr <- readMutVar (underlying g)       -- read current array
  curLen <- readMutVar (length g)           -- read current length
  newArr <- newArray (2 * curCap) def       -- allocate a new array twice as big
  copyMutableArray newArr 1 curArr 1 curLen -- copy the old array over
  underlying g `writeMutVar` newArr         -- use the new array in the vector
  capacity g `modifyMutVar'` (*2)           -- update the capacity in the vector

-- | Write an element to the array (unchecked). O(1)
write :: PrimMonad m => GrowVector (PrimState m) a -> Int -> a  -> m ()
write g i x = do arr <- readMutVar (underlying g); writeArray arr i x

-- | Pop an element of the vector, mutating it (unchecked). O(1)
popBack :: PrimMonad m => GrowVector (PrimState m) a -> m a
popBack g = do
  s <- size g;
  x <- g `read` (s - 1)
  length g `modifyMutVar'` (+ negate 1)
  pure x

-- | Push an element. (Amortized) O(1)
pushBack :: (Default a, PrimMonad m) => GrowVector (PrimState m) a -> a -> m ()
pushBack g x = do
  s <- readMutVar (length g)                -- read current size
  c <- readMutVar (capacity g)              -- read current capacity
  when (s+1 == c) (resize g)                -- if need be, resize
  write g (s+1) x                           -- write to the back of the array
  length g `modifyMutVar'` (+1)             -- increase te length

Текущая семантика grow

Я думаю, что github issue неплохо объясняет семантику:

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

В основном вы должны использовать grow, если вам нужен новый изменяемый вектор увеличенного размера, начиная с элементов старого вектора (и больше не заботятся о старом векторе). Это весьма полезно - например, реализовать GrowVector можно с помощью MVector и grow.

¹ подход заключается в том, что для каждого нового типа ненужного вектора, который вы хотите иметь, вы делаете data instance, который "расширяет" ваш тип в фиксированное количество распакованных массивов (или других распакованных векторы). Это точка data family - чтобы разные экземпляры типа имели совершенно разные представления во время исполнения, а также были расширяемы (вы можете добавить свой собственный data instance, если хотите).