úÎNoIü4      !"#$%&'()*+,-./0123(C) 2012-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> provisionalportableSafeProvides a consistent + for peeling off the bottom node of a path.456456(C) 2012-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe A compressed $ as a skew binary random access list7Complete binary trees/NB: 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 8.O(n) Re-annotate a 0 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 8- homomorphism, that is to say you must ensure f a `mappend' f b = f (a `mappend' b) f 9 = 9  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)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  h_, and provide a monoidal summary of the dropped elements using a supplied monoid homomorphism.O(log (h - k)) to  k elements of  of  hXThis 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_problemO(log k) to  k elements from a O(log k) to drop k elements from a \ and provide a monoidal summary of the dropped elements using a suplied monoid homomorphismO(log h) xs ` isAncestorOf' ys holds when xs* is a prefix starting at the root of path ys.O(1)3 Compare to see if two trees have the same leaf keyO(log h)0 Compute the lowest common ancestor of two pathsO(log h)’ Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails using the supplied monoid homomorphisms.":;7<=>?@ABC DE    :;7<=>?@ABC DE>(C) 2011-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe An 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)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)3 Compare to see if two trees have the same leaf key&O(h)0 Compute the lowest common ancestor of two pathsF !"#$%&GHI !"#$%& !$&"#%F !"#$%&GHI%(C) 2011-2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimentalportableSafe'6Compressed paths using skew binary random access listsJComplete 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)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 / k elements of ' of  hXThis 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_problem0O(log k) to 0 k elements from a '1O(log h) xs 1 ys holds when xs% is a prefix starting at the root of ' ys.2O(1)3 Compare to see if two trees have the same leaf key3O(log h)1 Compute the lowest common ancestor of two paths.'KLJMNOP()*+,-./0123QRSTUV'()*+,-./0123'3+,-.1/0*()2'KLJMNOP()*+,-./0123QRSTUV2W        !"#$%&%'()*+,-./0123 425$()*+/04256378lca_2BWyY7IO3sWDhjUXimg8kzData.LCA.Online.Monoidal Data.LCA.ViewData.LCA.Online.NaiveData.LCA.Onlinebase Data.FoldablelengthnullViewRootNodePathmeasuremap mapWithKeymapHomtoListfromListtraverseWithKeytraverseemptyconsunconsviewmkeepkeepdropmdrop isAncestorOf~=lcamlca$fTraversableView$fFoldableView $fFunctorViewTreeGHC.BaseMonoidmemptyNilConsBinTip<>measureTbinsameTconsTconsN$fFoldablePath$fFoldableTree$fTraversablePath $fFunctorPath$fTraversableTree $fFunctorTree