The first tree's root is the first element. Deleting that root either discards a singleton or exposes two equal-sized child trees:For a node of size , both children have size . Their order agrees with the old preorder traversal, and they become the sole permitted initial duplicate. The rest of the forest was no smaller than the old root tree. Thus both operations preserve the representation invariant and take worst-case time on a nonempty skew-binary random-access list.
head :: List a -> a
head (List ((_,Leaf x):_)) = x
head (List ((_,Node x _ _):_)) = x
head (List []) = error "head: empty list"
tail :: List a -> List a
tail (List ((_,Leaf _):ts)) = List ts
tail (List ((w,Node _ l r):ts)) =
let h = w `div` 2 in List ((h,l):(h,r):ts)
tail (List []) = error "tail: empty list" Articles by others on the same topic
There are currently no matching articles.