Skip to content

Instantly share code, notes, and snippets.

@snoyberg

snoyberg/List.hs Secret

Created May 24, 2021 06:27
Show Gist options
  • Save snoyberg/5de410aba87a4208b7c701e954c61d9d to your computer and use it in GitHub Desktop.
Save snoyberg/5de410aba87a4208b7c701e954c61d9d to your computer and use it in GitHub Desktop.
Mutable doubly linked list in Haskell
import Prelude hiding (last)
import Data.IORef
data Node a = Node
{ prev :: IORef (Maybe (Node a))
, value :: a
, next :: IORef (Maybe (Node a))
}
data List a = List
{ first :: IORef (Maybe (Node a))
, last :: IORef (Maybe (Node a))
}
newList :: IO (List a)
newList = List <$> newIORef Nothing <*> newIORef Nothing
pushBack :: List a -> a -> IO ()
pushBack list value = do
last' <- readIORef $ last list
case last' of
Nothing -> do
node <- Node <$> newIORef Nothing <*> pure value <*> newIORef Nothing
writeIORef (first list) (Just node)
writeIORef (last list) (Just node)
Just last' -> do
node <- Node <$> newIORef (Just last') <*> pure value <*> newIORef Nothing
writeIORef (next last') (Just node)
writeIORef (last list) (Just node)
popBack :: List a -> IO (Maybe a)
popBack list = do
last' <- readIORef (last list)
case last' of
Nothing -> pure Nothing
Just last' -> do
prev' <- readIORef $ prev last'
case prev' of
Nothing -> do
writeIORef (first list) Nothing
writeIORef (last list) Nothing
Just prev' -> do
writeIORef (next prev') Nothing
writeIORef (last list) (Just prev')
pure $ Just $ value last'
main :: IO ()
main = do
list <- newList
pushBack list 1
pushBack list 2
pushBack list 3
popBack list >>= print
popBack list >>= print
popBack list >>= print
popBack list >>= print
pushBack list 1
pushBack list 2
pushBack list 3
popBack list >>= print
popBack list >>= print
popBack list >>= print
popBack list >>= print
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment