Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# snoyberg/List.hs Secret

Created May 24, 2021
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
to join this conversation on GitHub. Already have an account? Sign in to comment