4 ms·
I know this is a big claim, but there are mathematical reasons to support why it works. And it works, at least on my computer.
by daniel-cussen 16y ago
I know this is a big claim, but there are mathematical reasons to support why it works. And it works, at least on my computer.
- daniel-cussen 16y agoAlso, I'd like to talk about what it does for those that don't feel like reading the GitHub. It's almost exactly like linked lists, except for two things: one, it is less flexible, and two, it is much faster. Most of its functions work in logarithmic time whereas those of linked lists work in linear time. Other than that, it's made of the same things (cons cells), it is navigated the same way (cars and cdrs) it is sequential, so it has clearly delimited first, second, and third elements, and it nests.
- jbapple 16y ago> I know this is a big claim Perhaps, but it needn't be to get the same asymptotic performance. Okasaki's simplest random access list has performance proofs that depend only on the simplest properties of binary numbers, rather than those of the Exponential-Golumb coding, and the code is very easy to write: data BRAL a = Empty | Full (Maybe a) (BRAL (a,a)) deriving (Show) cons :: a -> BRAL a -> BRAL a cons x Empty = Full (Just x) Empty cons x (Full Nothing ys) = Full (Just x) ys cons x (Full (Just y) ys) = Full Nothing (cons (x,y) ys) nth :: Integer -> BRAL a -> a nth 0 (Full (Just x) _) = x nth 0 (Full Nothing xs) = fst (nth 0 xs) nth n (Full (Just _) xs) = nth (n-1) (Full Nothing xs) nth n (Full Nothing xs) = let pair = nth (n`div`2) xs in if n`mod`2 == 0 then fst pair else snd pair