-
-
Save snoyberg/5de410aba87a4208b7c701e954c61d9d to your computer and use it in GitHub Desktop.
Mutable doubly linked list in Haskell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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