Skip to content

Instantly share code, notes, and snippets.

@snoyberg

snoyberg/List.hs Secret

Created May 24, 2021
Embed
What would you like to do?
Doubly linked list in Haskell using knot tying
import Prelude hiding (last)
import Data.Maybe (fromJust) -- evil function! just for testing below
data Node a = Node
{ prev :: Maybe (Node a)
, value :: a
, next :: Maybe (Node a)
}
data List a = List
{ first :: Maybe (Node a)
, last :: Maybe (Node a)
}
buildList :: [a] -> List a
buildList [] = List Nothing Nothing
buildList [x] =
let node = Node Nothing x Nothing
in List (Just node) (Just node)
-- You can leave out this clause entirely. Only here for teaching purposes!
buildList [x, y] =
let firstNode = Node Nothing x (Just lastNode)
lastNode = Node (Just firstNode) y Nothing
in List (Just firstNode) (Just lastNode)
buildList (x:y:ys) =
let firstNode = Node Nothing x (Just secondNode)
(secondNode, lastNode) = buildNodes firstNode y ys
in List (Just firstNode) (Just lastNode)
-- | Takes the previous node in the list, the current value, and all following
-- values. Returns the current node as well as the final node constructed in
-- this list.
buildNodes :: Node a -> a -> [a] -> (Node a, Node a)
buildNodes prevNode value [] =
let node = Node (Just prevNode) value Nothing
in (node, node)
buildNodes prevNode value (x:xs) =
let node = Node (Just prevNode) value (Just nextNode)
(nextNode, lastNode) = buildNodes node x xs
in (node, lastNode)
main :: IO ()
main = do
let list = buildList [1..10]
print $ value $ fromJust $ next $ fromJust $ next $ fromJust $ first list
let list = buildList [1..2]
print $ value $ fromJust $ next $ fromJust $ first list
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment