В первом приближении Haskell является достаточно выразительным языком, поэтому любой алгоритм, реализованный на другом языке общего назначения, также может быть реализован в Haskell при сохранении асимптотических характеристик производительности c. (Это довольно низкая планка. Большинство языков общего назначения являются такими выразительными.)
В частности, хотя Haskell наиболее естественно поддерживает неизменяемые структуры данных, он имеет достаточную поддержку изменяемых данных, что изменяемые структуры данных и их алгоритмы обычно могут быть напрямую переведены в Haskell код. Могут быть некоторые издержки (часто существенные накладные расходы), и изменяемые структуры данных могут быть значительно более неудобными для использования, чем их неизменные кузены, но это все же возможно.
На практике, однако, соответствие Фактическая (в отличие от асимптотики c) производительность C ++ реализации изменяемой структуры данных, вероятно, окажется чрезвычайно сложной, если не невозможной. Может быть разумно получить в 2-3 раза производительность C ++, а получить в 5-10 раз довольно легко (см. Ниже). Однако, если вам нужно соответствовать производительности C ++, вам, вероятно, было бы лучше написать высокопроизводительный мутирующий код на C ++ и использовать FFI (интерфейс внешних функций) для взаимодействия с этим кодом.
В любом случае, «умеренный» Производительность "двусвязный список с O (1) length безусловно возможна, и нет никаких фундаментальных трудностей с поддержкой изменяемых метаданных всего списка. Причина, по которой stm-linkedlist не обеспечивает O (1) length, вероятно, та же самая причина, по которой C ++ гарантировал только O (n) std::list<>::size производительность до C ++ 11 . А именно, во многих практических случаях использования списков с двойной связью не нужно вызывать length / size, а обеспечение производительности O (1) сопряжено с дополнительными расходами на ведение бухгалтерского учета.
В качестве подтверждения концепции Для реализации полностью изменяемого двусвязного списка с функцией длины O (1) достаточно следующих типов данных. Здесь типы и идентификаторы, заканчивающиеся подчеркиванием, предназначены только для внутреннего использования. Список строг в своих указателях (поэтому нет бесконечных списков!), Но ленив в своих значениях.
data List a = List
{ headNode_ :: !(IORef (Node_ a))
, length_ :: !(IORef Int) }
data Node_ a = Node_
{ prev_ :: !(IORef (Node_ a))
, next_ :: !(IORef (Node_ a))
, value_ :: a }
Тип List содержит указатель (т. Е. IORef) на неполный headNode это указывает на начало и конец списка (или на себя для пустого списка), но имеет неопределенное поле значения. Это делает это значение небезопасного узла, поэтому он никогда не должен быть напрямую доступен конечному пользователю. List также содержит указатель на значение длины списка.
Дополнительный тип Node (без подчеркивания) используется для украшения указателя узла соответствующим списком (например, «итератор» из комментариев). ), чтобы сделать метаданные списка доступными для функций, которые в них нуждаются:
data Node a = Node
{ node_ :: !(IORef (Node_ a))
, list_ :: !(List a) }
Обратите внимание, что List и Node - это типы данных для работы со списками, ориентированные на пользователя.
Вы создаете список empty следующим образом:
empty :: IO (List a)
empty = mdo
n <- newIORef (Node_ n n undefined)
List n <$> newIORef 0
Вставка до и после данного узла работает следующим образом. Вот где небезопасное представление головного узла окупается, поскольку алгоритм может рассматривать вставку в начале и конце списка как особые случаи вставки между головным узлом и фактическим узлом списка.
insertBefore :: a -> Node a -> IO (Node a)
insertBefore x Node{node_=rnode2, list_} = do
Node_{prev_=rnode1} <- readIORef rnode2
insertBetween_ x list_ rnode1 rnode2
insertAfter :: a -> Node a -> IO (Node a)
insertAfter x Node{node_=rnode1, list_} = do
Node_{next_=rnode2} <- readIORef rnode1
insertBetween_ x list_ rnode1 rnode2
insertBetween_ :: a -> List a -> IORef (Node_ a) -> IORef (Node_ a) -> IO (Node a)
insertBetween_ x l rnode1 rnode2 = do
modifyIORef' (length_ l) succ
newnode <- newIORef (Node_ rnode1 rnode2 x)
modifyIORef' rnode1 (\n -> n{next_=newnode})
modifyIORef' rnode2 (\n -> n{prev_=newnode})
return $ Node newnode l
Поскольку пользователю не разрешено «иметь» головной узел, нам нужны дополнительные пользовательские функции для вставки в начало и конец списка:
prepend :: a -> List a -> IO (Node a)
prepend x l = insertAfter x (Node (headNode_ l) l)
append :: a -> List a -> IO (Node a)
append x l = insertBefore x (Node (headNode_ l) l)
Обратите внимание, что все вставки go - insertBetween_ который отвечает за увеличение значения длины.
Удаление является простым и равномерным, будь то внутренний узел или узел в начале или конце. Все удаления go с помощью этой функции delete, которая отвечает за уменьшение значения длины.
delete :: Node a -> IO ()
delete Node{node_,list_} = do
modifyIORef' (length_ list_) pred
Node_{next_, prev_} <- readIORef node_
modifyIORef' prev_ (\n -> n{next_=next_})
modifyIORef' next_ (\n -> n{prev_=prev_})
Удаление головного узла может привести к катастрофе, но пользователи не могут иметь такой Node, поэтому мы в безопасности.
Если у пользователя есть Node, он может перемещаться по списку:
prev :: Node a -> IO (Maybe (Node a))
prev Node{node_, list_} = do
Node_{prev_} <- readIORef node_
return $ maybeNode_ prev_ list_
next :: Node a -> IO (Maybe (Node a))
next Node{node_, list_} = do
Node_{next_} <- readIORef node_
return $ maybeNode_ next_ list_
maybeNode_ :: IORef (Node_ a) -> List a -> Maybe (Node a)
maybeNode_ n l =
if n == headNode_ l
then Nothing
else Just (Node n l)
Обратите внимание, что мы должны позаботиться о том, чтобы никогда не давать пользователю головной узел, поэтому maybeNode_ здесь проверяет его и возвращает вместо него Nothing.
Для начала пользователь может получить старт или конец List с использованием следующих функций (которые используют prev или next на запрещенном главном узле):
start :: List a -> IO (Maybe (Node a))
start l = next $ Node (headNode_ l) l
end :: List a -> IO (Maybe (Node a))
end l = prev $ Node (headNode_ l) l
Все, чего не хватает, - это несколько разных функций запроса:
value :: Node a -> IO a
value = fmap value_ . readIORef . node_
null :: List a -> IO Bool
null l = (==0) <$> length l
length :: List a -> IO Int
length = readIORef . length_
некоторые утилиты для преобразования в простые списки:
toList :: List a -> IO [a]
toList = toList_ next_
toListRev :: List a -> IO [a]
toListRev = toList_ prev_
toList_ :: (Node_ a -> IORef (Node_ a)) -> List a -> IO [a]
toList_ dir l = go =<< readIORef h
where h = headNode_ l
go n = do
if dir n == h then return []
else do
n' <- readIORef (dir n)
(value_ n':) <$> go n'
и Show экземпляр для отладки:
instance (Show a) => Show (List a) where
showsPrec d lst = showParen (d > 10) $ showString "fromList " . showsPrec 11 (unsafePerformIO $ toList lst)
ПРЕДУПРЕЖДЕНИЕ: This Show Экземпляр небезопасен, если список видоизменен до полной оценки сгенерированной строки, поэтому его следует использовать только для отладки (и, вероятно, удаления из рабочей версии).
Кроме того, хотя это не является строго обязательным, поскольку мы можем удалить и вставить заново, ни одна уважающая себя изменчивая структура не будет полной без изменения элементов на месте:
modify :: (a -> a) -> Node a -> IO ()
modify f Node{node_} = modifyIORef' node_ (\n -> n { value_ = f (value_ n) })
Вот полный код. (См. Определение ex1 для примера использования.) Вы можете использовать его в качестве отправной точки для своей собственной реализации. Он не проверен и не соответствует стандартам, за исключением нескольких быстрых тестов, которые, вероятно, примерно в 5-10 раз медленнее, чем реализация C ++.
{-# LANGUAGE NamedFieldPuns, RecursiveDo #-}
module LinkedList
( List, Node
, value, null, length
, empty, prepend, append, insertBefore, insertAfter, delete, modify
, prev, next, start, end
, toList, toListRev
) where
import System.IO.Unsafe
import Control.Monad
import Prelude hiding (null, length)
import Data.IORef
data List a = List
{ headNode_ :: !(IORef (Node_ a))
, length_ :: !(IORef Int) }
data Node a = Node
{ node_ :: !(IORef (Node_ a))
, list_ :: !(List a) }
data Node_ a = Node_
{ prev_ :: !(IORef (Node_ a))
, next_ :: !(IORef (Node_ a))
, value_ :: a }
-- unsafe show instance: remove from production version
instance (Show a) => Show (List a) where
showsPrec d lst = showParen (d > 10) $ showString "fromList " . showsPrec 11 (unsafePerformIO $ toList lst)
value :: Node a -> IO a
value = fmap value_ . readIORef . node_
null :: List a -> IO Bool
null l = (==0) <$> length l
length :: List a -> IO Int
length = readIORef . length_
empty :: IO (List a)
empty = mdo
n <- newIORef (Node_ n n undefined)
List n <$> newIORef 0
prepend :: a -> List a -> IO (Node a)
prepend x l = insertAfter x (Node (headNode_ l) l)
append :: a -> List a -> IO (Node a)
append x l = insertBefore x (Node (headNode_ l) l)
insertBefore :: a -> Node a -> IO (Node a)
insertBefore x Node{node_=rnode2, list_} = do
Node_{prev_=rnode1} <- readIORef rnode2
insertBetween_ x list_ rnode1 rnode2
insertAfter :: a -> Node a -> IO (Node a)
insertAfter x Node{node_=rnode1, list_} = do
Node_{next_=rnode2} <- readIORef rnode1
insertBetween_ x list_ rnode1 rnode2
insertBetween_ :: a -> List a -> IORef (Node_ a) -> IORef (Node_ a) -> IO (Node a)
insertBetween_ x l rnode1 rnode2 = do
modifyIORef' (length_ l) succ
newnode <- newIORef (Node_ rnode1 rnode2 x)
modifyIORef' rnode1 (\n -> n{next_=newnode})
modifyIORef' rnode2 (\n -> n{prev_=newnode})
return $ Node newnode l
delete :: Node a -> IO ()
delete Node{node_,list_} = do
modifyIORef' (length_ list_) pred
Node_{next_, prev_} <- readIORef node_
modifyIORef' prev_ (\n -> n{next_=next_})
modifyIORef' next_ (\n -> n{prev_=prev_})
modify :: (a -> a) -> Node a -> IO ()
modify f Node{node_} = modifyIORef' node_ (\n -> n { value_ = f (value_ n) })
prev :: Node a -> IO (Maybe (Node a))
prev Node{node_, list_} = do
Node_{prev_} <- readIORef node_
return $ maybeNode_ prev_ list_
next :: Node a -> IO (Maybe (Node a))
next Node{node_, list_} = do
Node_{next_} <- readIORef node_
return $ maybeNode_ next_ list_
maybeNode_ :: IORef (Node_ a) -> List a -> Maybe (Node a)
maybeNode_ n l =
if n == headNode_ l
then Nothing
else Just (Node n l)
start :: List a -> IO (Maybe (Node a))
start l = next $ Node (headNode_ l) l
end :: List a -> IO (Maybe (Node a))
end l = prev $ Node (headNode_ l) l
toList :: List a -> IO [a]
toList = toList_ next_
toListRev :: List a -> IO [a]
toListRev = toList_ prev_
toList_ :: (Node_ a -> IORef (Node_ a)) -> List a -> IO [a]
toList_ dir l = go =<< readIORef h
where h = headNode_ l
go n = do
if dir n == h then return []
else do
n' <- readIORef (dir n)
(value_ n':) <$> go n'
ex1 :: IO (List Int)
ex1 = do
t <- empty
mapM_ (flip prepend t) [10,9..1]
mapM_ (flip append t) [11..20]
return t