NDI8      !"#$%&'()*+,-./01234567portable provisionalEdward Kmett <ekmett@gmail.com> Safe-InferredProvides a consistent , for peeling off the bottom node of a path. 89:89:portable experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred A compressed % as a skew binary random access list ;Complete binary trees 0NB: we could ensure the complete tree invariant  Extract a monoidal summary of a . O(n) Re-annotate a + full of monoidal values using a different <. O(n) Re-annotate a 1 full of monoidal values with access to the key. O(n) Re-annotate a  full of monoidal values/ Unlike ,  f assumes that f is a <. homomorphism, that is to say you must ensure   f a  `'mappend'` f b = f (a  `'mappend'` b)  f = = =  Convert a  to a list of  (ID, value) pairs. Build a  from a list of  (ID, value) pairs.  Traverse a  with access to the node IDs.  Traverse a % yielding a new monoidal annotation.  The empty  O(1) Determine the   of a . O(1) Returns > iff the path is  . O(1)1 Invariant: most operations assume that the keys k are globally unique  Extend the  with a new node ID and value. O(1); Extract the node ID and value from the newest node on the . O(1); Extract the node ID and value from the newest node on the , slightly faster than . O(log (h - k)) to keep k elements of  of   h9, and provide a monoidal summary of the dropped elements O(log (h - k)) to  k elements of  of   h &This solves the online version of the "level ancestor problem" with no preprocessing in O(log h) time, $ improving known complexity bounds.  3http://en.wikipedia.org/wiki/Level_ancestor_problem O(log k) to  k elements from a  O(log k) to drop k elements from a 8 and provide a monoidal summary of the dropped elements O(log h) xs `'isAncestorOf'` ys holds when xs* is a prefix starting at the root of path ys. O(1)4 Compare to see if two trees have the same leaf key O(log h)1 Compute the lowest common ancestor of two paths O(log h)j Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails. $?@;ABCDEFGH IJ     @?;BACDEFGH IJportable experimentalEdward Kmett <ekmett@gmail.com> Safe-InferredAn uncompressed  with memoized length.  Convert a  to a list of  (ID, value) pairs. Build a  from a list of  (ID, value) pairs.  Traverse a  with access to the node IDs.  The empty  O(1) Determine the length of a . O(1) Returns > iff the  is . !O(1)1 Invariant: most operations assume that the keys k are globally unique .Extend the path with a new node ID and value. "O(1); Extract the node ID and value from the newest node on the . #O(1); Extract the node ID and value from the newest node on the , slightly faster than ". $O(h - k) to $ k elements of  of  h %O(k) to % k elements from a  &O(h) xs & ys holds when xs% is a prefix starting at the root of  ys. 'O(1)4 Compare to see if two trees have the same leaf key (O(h)1 Compute the lowest common ancestor of two paths K !"#$%&'(LMN !"#$%&'(!"# &($%'K !"#$%&'(LMNportable experimentalEdward Kmett <ekmett@gmail.com> Safe-Inferred)7Compressed paths using skew binary random access lists OComplete binary trees * Convert a ) to a list of  (ID, value) pairs. +Build a ) from a list of  (ID, value) pairs. , Traverse a ) with access to the node IDs. -The - ) .O(1) Determine the . of a ). /O(1) Returns > iff the path is -. 0O(1)1 Invariant: most operations assume that the keys k are globally unique  Extend the ) with a new node ID and value. 1O(1); Extract the node ID and value from the newest node on the ). 2O(1); Extract the node ID and value from the newest node on the ), slightly faster than 1. 3O(log (h - k)) to 3 k elements of ) of . h &This solves the online version of the "level ancestor problem" with no preprocessing in O(log h) time, $ improving known complexity bounds.  3http://en.wikipedia.org/wiki/Level_ancestor_problem 4O(log k) to 4 k elements from a ) 5O(log h) xs 5 ys holds when xs% is a prefix starting at the root of ) ys. 6O(1)4 Compare to see if two trees have the same leaf key 7O(log h)2 Compute the lowest common ancestor of two paths. )PQORSTU*+,-./01234567VWXYZ[)*+,-./01234567)7-012/.534,*+6)QPOSRTU*+,-./01234567VWXYZ[\        !"#$%#$&'()*+,-./012345647"*+,-12647859: lca-0.2.3 Data.LCA.ViewData.LCA.Online.MonoidalData.LCA.Online.NaiveData.LCA.OnlineViewNodeRootPathmeasuremap mapWithKeymapHomtoListfromListtraverseWithKeytraverseemptylengthnullconsunconsviewmkeepkeepdropmdrop isAncestorOf~=lcamlca$fTraversableView$fFoldableView $fFunctorViewTreebase Data.MonoidMonoidmemptyghc-prim GHC.TypesTrueConsNilTipBin<>measureTbinsameTconsTconsN$fFoldablePath$fFoldableTree$fTraversablePath $fFunctorPath$fTraversableTree $fFunctorTree