Created
February 28, 2024 22:33
-
-
Save Janiczek/a442e9fcb84aacfb1452e538abf57bab to your computer and use it in GitHub Desktop.
Random access lists in Elm (WIP)
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
| module RAList exposing (RAList, cons, empty, fromList, head, isEmpty, lookup, tail, update) | |
| {-| Okasaki, Random Access Lists | |
| <https://dl.acm.org/doi/pdf/10.1145/224164.224187> | |
| O(1) list operations (cons, head, tail) | |
| O(log\_2 n) array operations (lookup, update) | |
| -} | |
| import Tree exposing (Tree(..)) | |
| type RAList a | |
| = RAList (List ( {- size -} Int, Tree a )) | |
| empty : RAList a | |
| empty = | |
| RAList [] | |
| isEmpty : RAList a -> Bool | |
| isEmpty (RAList xs) = | |
| List.isEmpty xs | |
| cons : a -> RAList a -> RAList a | |
| cons x (RAList xs) = | |
| case xs of | |
| ( size1, t1 ) :: ( size2, t2 ) :: rest -> | |
| if size1 == size2 then | |
| RAList (( 1 + size1 + size2, Node t1 x t2 ) :: rest) | |
| else | |
| RAList (( 1, Leaf x ) :: xs) | |
| _ -> | |
| RAList (( 1, Leaf x ) :: xs) | |
| fromList : List a -> RAList a | |
| fromList xs = | |
| List.foldl cons empty xs | |
| head : RAList a -> Maybe a | |
| head (RAList xs) = | |
| case xs of | |
| [] -> | |
| Nothing | |
| ( _, Leaf x ) :: _ -> | |
| Just x | |
| ( _, Node _ x _ ) :: _ -> | |
| Just x | |
| tail : RAList a -> Maybe (RAList a) | |
| tail (RAList xs) = | |
| case xs of | |
| [] -> | |
| Nothing | |
| ( _, Leaf _ ) :: rest -> | |
| Just (RAList rest) | |
| ( size, Node t1 _ t2 ) :: rest -> | |
| let | |
| size_ = | |
| size // 2 | |
| in | |
| ( size_, t1 ) :: ( size_, t2 ) :: rest | |
| lookup : Int -> RAList a -> Maybe a | |
| lookup i (RAList xs) = | |
| if i < size then | |
| Tree.lookup size i t | |
| else | |
| RAList.lookup (i - size) (RAList rest) | |
| update : Int -> a -> RAList a -> RAList a | |
| update i value (RAList xs) = | |
| if i < size then | |
| RAList (( size, Tree.update size i y t ) :: rest) | |
| else | |
| RAList (( size, t ) :: RAList.update (i - size) y (RAList rest)) |
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
| module Tree exposing (Tree(..), lookup, update) | |
| type Tree a | |
| = Leaf a | |
| | Node (Tree a) a (Tree a) | |
| lookup : Int -> Int -> Tree a -> Maybe a | |
| lookup size index tree = | |
| case ( tree, index ) of | |
| ( Leaf x, 0 ) -> | |
| Just x | |
| ( Leaf x, _ ) -> | |
| Nothing | |
| ( Node _ x _, 0 ) -> | |
| Just x | |
| ( Node t1 x t2, _ ) -> | |
| let | |
| size_ = | |
| size // 2 | |
| in | |
| if index <= size_ then | |
| lookup size_ (index - 1) t1 | |
| else | |
| lookup size_ (index - size_ - 1) t2 | |
| update : Int -> Int -> a -> Tree a -> Tree a | |
| update size index value tree = | |
| case ( tree, index ) of | |
| ( Leaf x, 0 ) -> | |
| Leaf value | |
| ( Leaf x, _ ) -> | |
| tree | |
| ( Node t1 x t2, 0 ) -> | |
| Node t1 value t2 | |
| ( Node t1 x t2, _ ) -> | |
| let | |
| size_ = | |
| size // 2 | |
| in | |
| if index <= size_ then | |
| Node (update size_ (index - 1) value t1) x t2 | |
| else | |
| Node t1 x (update size_ (index - size_ - 1) value t2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment