hw-fingertree 0.1.0.1 → 0.1.0.2

raw patch · 6 files changed

+404/−560 lines, 6 filesdep −HUnitdep −QuickCheckdep −test-frameworkdep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies removed: HUnit, QuickCheck, test-framework, test-framework-hunit, test-framework-quickcheck2

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• LICENSE +2/−3
• hw-fingertree.cabal +38/−47
• src/HaskellWorks/Data/FingerTree.hs +292/−438
• src/HaskellWorks/Data/IntervalMap/FingerTree.hs +46/−45
• src/HaskellWorks/Data/PriorityQueue/FingerTree.hs +25/−26
• tests/HaskellWorks/Data/FingerTreeSpec.hs +1/−1

@@ -1,6 +1,5 @@-BSD 3-Clause License--Copyright (c) 2017, +Copyright John Ky (c) 2017-2018+Copyright Ross Paterson, Ralf Hinze (c) 2006  All rights reserved.  Redistribution and use in source and binary forms, with or without

@@ -1,11 +1,7 @@--- This file has been generated from package.yaml by hpack version 0.20.0.------ see: https://github.com/sol/hpack------ hash: 8cd50b9741a1c8a2bcc9297a6ee8ba24104ddc058fb32364d45037c5f0958bf1+cabal-version:  2.2  name:           hw-fingertree-version:        0.1.0.1+version:        0.1.0.2 synopsis:       Generic finger-tree structure, with example instances description:    A general sequence representation with arbitrary                 annotations, for use as a base for implementations of@@ -24,56 +20,51 @@ homepage:       https://github.com/haskell-works/hw-fingertree#readme bug-reports:    https://github.com/haskell-works/hw-fingertree/issues maintainer:     John Ky <newhoggy@gmail.com>-copyright:      (c) 2006 Ross Paterson,-                Ralf Hinze,-                (c) 2017-2018 John Ky-license:        BSD3+copyright:      (c) 2017-2019 John Ky+                (c) 2006 Ross Paterson, Ralf Hinze,+license:        BSD-3-Clause license-file:   LICENSE build-type:     Simple-cabal-version:  >= 1.10 +common base                       { build-depends: base                       >= 4          && < 5      }++common deepseq                    { build-depends: deepseq                                              }+common hedgehog                   { build-depends: hedgehog                                             }+common hspec                      { build-depends: hspec                                                }+common hw-fingertree              { build-depends: hw-fingertree                                        }+common hw-hspec-hedgehog          { build-depends: hw-hspec-hedgehog                                    }++common config+  default-language: Haskell2010+ source-repository head   type: git   location: https://github.com/haskell-works/hw-fingertree  library-  hs-source-dirs:-      src-  build-depends:-      base <6-    , deepseq+  import:   base, config+          , deepseq+  hs-source-dirs:     src+  other-modules:      Paths_hw_fingertree+  autogen-modules:    Paths_hw_fingertree   exposed-modules:-      HaskellWorks.Data.FingerTree-      HaskellWorks.Data.IntervalMap.FingerTree-      HaskellWorks.Data.PriorityQueue.FingerTree-  other-modules:-      Paths_hw_fingertree-  default-language: Haskell2010+    HaskellWorks.Data.FingerTree+    HaskellWorks.Data.IntervalMap.FingerTree+    HaskellWorks.Data.PriorityQueue.FingerTree  test-suite hw-fingertree-tests-  type: exitcode-stdio-1.0-  main-is: Spec.hs-  hs-source-dirs:-      tests-      src-  cpp-options: -DTESTING-  build-depends:-      HUnit-    , QuickCheck-    , base >=4.2 && <6-    , deepseq-    , hedgehog-    , hspec-    , hw-fingertree-    , hw-hspec-hedgehog-    , test-framework-    , test-framework-hunit-    , test-framework-quickcheck2+  import:   base, config+          , deepseq+          , hedgehog+          , hspec+          , hw-hspec-hedgehog+  build-depends:      hw-fingertree+  type:               exitcode-stdio-1.0+  main-is:            Spec.hs+  hs-source-dirs:     tests+  build-tools:        hspec-discover+  autogen-modules:    Paths_hw_fingertree   other-modules:-      HaskellWorks.Data.FingerTree.Gen-      HaskellWorks.Data.FingerTreeSpec-      HaskellWorks.Data.FingerTree-      HaskellWorks.Data.IntervalMap.FingerTree-      HaskellWorks.Data.PriorityQueue.FingerTree-      Paths_hw_fingertree-  default-language: Haskell2010+    HaskellWorks.Data.FingerTree.Gen+    HaskellWorks.Data.FingerTreeSpec+    Paths_hw_fingertree

@@ -3,7 +3,6 @@ {-# LANGUAGE DeriveGeneric          #-} {-# LANGUAGE FlexibleInstances      #-} {-# LANGUAGE FunctionalDependencies #-}-{-# LANGUAGE MultiParamTypeClasses  #-} {-# LANGUAGE UndecidableInstances   #-} #if __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Safe                   #-}@@ -42,36 +41,48 @@ -- ----------------------------------------------------------------------------- -module HaskellWorks.Data.FingerTree (-#if TESTING-    FingerTree(..), Digit(..), Node(..), deep, node2, node3,-#else-    FingerTree,-#endif-    Measured(..),-    -- * Construction-    empty, singleton,-    (<|), (|>), (><),-    fromList,-    -- * Deconstruction-    null,-    ViewL(..), ViewR(..), viewl, viewr,-    split, takeUntil, dropUntil,-    -- * Transformation-    reverse,-    fmap', fmapWithPos, unsafeFmap,-    traverse', traverseWithPos, unsafeTraverse-    -- * Example-    -- $example-    ) where--import Prelude hiding (null, reverse)+module HaskellWorks.Data.FingerTree+  ( FingerTree(..)+  , Digit(..)+  , Node(..)+  , deep+  , node2+  , node3+  , Measured(..)+  -- * Construction+  , empty+  , singleton+  , (<|)+  , (|>)+  , (><)+  , fromList+  -- * Deconstruction+  , null+  , ViewL(..)+  , ViewR(..)+  , viewl+  , viewr+  , split+  , takeUntil+  , dropUntil+  -- * Transformation+  , reverse+  , fmap'+  , fmapWithPos+  , unsafeFmap+  , traverse'+  , traverseWithPos+  , unsafeTraverse+  -- * Example+  -- $example+  ) where  import Control.Applicative (Applicative (pure, (<*>)), (<$>)) import Control.DeepSeq import Data.Foldable       (Foldable (foldMap), toList) import Data.Monoid import GHC.Generics        (Generic)+import Prelude             hiding (null, reverse)  import qualified Data.Semigroup as S @@ -81,24 +92,23 @@  -- | View of the left end of a sequence. data ViewL s a-    = EmptyL        -- ^ empty sequence-    | a :< s a      -- ^ leftmost element and the rest of the sequence-    deriving (Eq, Ord, Show, Read, Generic, NFData)+  = EmptyL        -- ^ empty sequence+  | a :< s a      -- ^ leftmost element and the rest of the sequence+  deriving (Eq, Ord, Show, Read, Generic, NFData)  -- | View of the right end of a sequence. data ViewR s a-    = EmptyR        -- ^ empty sequence-    | s a :> a      -- ^ the sequence minus the rightmost element,-                    -- and the rightmost element-    deriving (Eq, Ord, Show, Read, Generic, NFData)+  = EmptyR        -- ^ empty sequence+  | s a :> a      -- ^ the sequence minus the rightmost element, -- and the rightmost element+  deriving (Eq, Ord, Show, Read, Generic, NFData)  instance Functor s => Functor (ViewL s) where-    fmap _ EmptyL    = EmptyL-    fmap f (x :< xs) = f x :< fmap f xs+  fmap _ EmptyL    = EmptyL+  fmap f (x :< xs) = f x :< fmap f xs  instance Functor s => Functor (ViewR s) where-    fmap _ EmptyR    = EmptyR-    fmap f (xs :> x) = fmap f xs :> f x+  fmap _ EmptyR    = EmptyR+  fmap f (xs :> x) = fmap f xs :> f x  instance Measured v a => S.Semigroup (FingerTree v a) where   (<>) = (><)@@ -114,17 +124,17 @@ -- Explicit Digit type (Exercise 1)  data Digit a-    = One a-    | Two a a-    | Three a a a-    | Four a a a a-    deriving (Show, Generic, NFData)+  = One a+  | Two a a+  | Three a a a+  | Four a a a a+  deriving (Show, Generic, NFData)  instance Foldable Digit where-    foldMap f (One a)        = f a-    foldMap f (Two a b)      = f a `mappend` f b-    foldMap f (Three a b c)  = f a `mappend` f b `mappend` f c-    foldMap f (Four a b c d) = f a `mappend` f b `mappend` f c `mappend` f d+  foldMap f (One a)        = f a+  foldMap f (Two a b)      = f a `mappend` f b+  foldMap f (Three a b c)  = f a `mappend` f b `mappend` f c+  foldMap f (Four a b c d) = f a `mappend` f b `mappend` f c `mappend` f d  ------------------- -- 4.1 Measurements@@ -132,21 +142,21 @@  -- | Things that can be measured. class (Monoid v) => Measured v a | a -> v where-    measure :: a -> v+  measure :: a -> v  instance (Measured v a) => Measured v (Digit a) where-    measure = foldMap measure+  measure = foldMap measure  --------------------------- -- 4.2 Caching measurements ---------------------------  data Node v a = Node2 !v a a | Node3 !v a a a-    deriving (Show, Generic, NFData)+  deriving (Show, Generic, NFData)  instance Foldable (Node v) where-    foldMap f (Node2 _ a b)   = f a `mappend` f b-    foldMap f (Node3 _ a b c) = f a `mappend` f b `mappend` f c+  foldMap f (Node2 _ a b)   = f a `mappend` f b+  foldMap f (Node3 _ a b c) = f a `mappend` f b `mappend` f c  node2        ::  (Measured v a) => a -> a -> Node v a node2 a b    =   Node2 (measure a `mappend` measure b) a b@@ -155,8 +165,8 @@ node3 a b c  =   Node3 (measure a `mappend` measure b `mappend` measure c) a b c  instance (Monoid v) => Measured v (Node v a) where-    measure (Node2 v _ _)   =  v-    measure (Node3 v _ _ _) =  v+  measure (Node2 v _ _)   =  v+  measure (Node3 v _ _ _) =  v  nodeToDigit :: Node v a -> Digit a nodeToDigit (Node2 _ a b)   = Two a b@@ -174,57 +184,44 @@ -- A variety of abstract data types can be implemented by using different -- element types and measurements. data FingerTree v a-    = Empty-    | Single a-    | Deep !v !(Digit a) (FingerTree v (Node v a)) !(Digit a)-    deriving (-#if TESTING-    Show,-#endif-    Generic, NFData)+  = Empty+  | Single a+  | Deep !v !(Digit a) (FingerTree v (Node v a)) !(Digit a)+  deriving (Generic, NFData) -deep ::  (Measured v a) =>-     Digit a -> FingerTree v (Node v a) -> Digit a -> FingerTree v a+deep :: (Measured v a) => Digit a -> FingerTree v (Node v a) -> Digit a -> FingerTree v a deep pr m sf = Deep ((measure pr `mappendVal` m) `mappend` measure sf) pr m sf  -- | /O(1)/. The cached measure of a tree. instance (Measured v a) => Measured v (FingerTree v a) where-    measure Empty          =  mempty-    measure (Single x)     =  measure x-    measure (Deep v _ _ _) =  v+  measure Empty          =  mempty+  measure (Single x)     =  measure x+  measure (Deep v _ _ _) =  v  instance Foldable (FingerTree v) where-    foldMap _ Empty = mempty-    foldMap f (Single x) = f x-    foldMap f (Deep _ pr m sf) =-        foldMap f pr `mappend` foldMap (foldMap f) m `mappend` foldMap f sf+  foldMap _ Empty            = mempty+  foldMap f (Single x)       = f x+  foldMap f (Deep _ pr m sf) = foldMap f pr `mappend` foldMap (foldMap f) m `mappend` foldMap f sf  instance Eq a => Eq (FingerTree v a) where-    xs == ys = toList xs == toList ys+  xs == ys = toList xs == toList ys  instance Ord a => Ord (FingerTree v a) where-    compare xs ys = compare (toList xs) (toList ys)+  compare xs ys = compare (toList xs) (toList ys) -#if !TESTING instance Show a => Show (FingerTree v a) where-    showsPrec p xs = showParen (p > 10) $-        showString "fromList " . shows (toList xs)-#endif+  showsPrec p xs = showParen (p > 10) $ showString "fromList " . shows (toList xs)  -- | Like 'fmap', but with a more constrained type.-fmap' :: (Measured v1 a1, Measured v2 a2) =>-    (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2+fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 fmap' = mapTree -mapTree :: (Measured v2 a2) =>-    (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2-mapTree _ Empty = Empty-mapTree f (Single x) = Single (f x)-mapTree f (Deep _ pr m sf) =-    deep (mapDigit f pr) (mapTree (mapNode f) m) (mapDigit f sf)+mapTree :: (Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2+mapTree _ Empty            = Empty+mapTree f (Single x)       = Single (f x)+mapTree f (Deep _ pr m sf) = deep (mapDigit f pr) (mapTree (mapNode f) m) (mapDigit f sf) -mapNode :: (Measured v2 a2) =>-    (a1 -> a2) -> Node v1 a1 -> Node v2 a2+mapNode :: (Measured v2 a2) => (a1 -> a2) -> Node v1 a1 -> Node v2 a2 mapNode f (Node2 _ a b)   = node2 (f a) (f b) mapNode f (Node3 _ a b c) = node3 (f a) (f b) (f c) @@ -236,133 +233,114 @@  -- | Map all elements of the tree with a function that also takes the -- measure of the prefix of the tree to the left of the element.-fmapWithPos :: (Measured v1 a1, Measured v2 a2) =>-    (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2+fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 fmapWithPos f = mapWPTree f mempty -mapWPTree :: (Measured v1 a1, Measured v2 a2) =>-    (v1 -> a1 -> a2) -> v1 -> FingerTree v1 a1 -> FingerTree v2 a2+mapWPTree :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> v1 -> FingerTree v1 a1 -> FingerTree v2 a2 mapWPTree _ _ Empty = Empty mapWPTree f v (Single x) = Single (f v x)-mapWPTree f v (Deep _ pr m sf) =-    deep (mapWPDigit f v pr)-         (mapWPTree (mapWPNode f) vpr m)-         (mapWPDigit f vm sf)-  where-    vpr     =  v    `mappend`  measure pr-    vm      =  vpr  `mappendVal` m+mapWPTree f v (Deep _ pr m sf) = deep+  (mapWPDigit f v pr)+  (mapWPTree (mapWPNode f) vpr m)+  (mapWPDigit f vm sf)+  where vpr = v    `mappend`  measure pr+        vm  = vpr  `mappendVal` m -mapWPNode :: (Measured v1 a1, Measured v2 a2) =>-    (v1 -> a1 -> a2) -> v1 -> Node v1 a1 -> Node v2 a2+mapWPNode :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> v1 -> Node v1 a1 -> Node v2 a2 mapWPNode f v (Node2 _ a b) = node2 (f v a) (f va b)-  where-    va      = v `mappend` measure a+  where va = v `mappend` measure a mapWPNode f v (Node3 _ a b c) = node3 (f v a) (f va b) (f vab c)-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b+  where va  = v  `mappend` measure a+        vab = va `mappend` measure b  mapWPDigit :: (Measured v a) => (v -> a -> b) -> v -> Digit a -> Digit b-mapWPDigit f v (One a) = One (f v a)+mapWPDigit f v (One a  ) = One (f v a) mapWPDigit f v (Two a b) = Two (f v a) (f va b)-  where-    va      = v `mappend` measure a+  where va = v `mappend` measure a mapWPDigit f v (Three a b c) = Three (f v a) (f va b) (f vab c)-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b+  where va  = v  `mappend` measure a+        vab = va `mappend` measure b mapWPDigit f v (Four a b c d) = Four (f v a) (f va b) (f vab c) (f vabc d)-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b-    vabc    = vab `mappend` measure c+  where va    = v   `mappend` measure a+        vab   = va  `mappend` measure b+        vabc  = vab `mappend` measure c  -- | Like 'fmap', but safe only if the function preserves the measure. unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b-unsafeFmap _ Empty = Empty-unsafeFmap f (Single x) = Single (f x)-unsafeFmap f (Deep v pr m sf) =-    Deep v (mapDigit f pr) (unsafeFmap (unsafeFmapNode f) m) (mapDigit f sf)+unsafeFmap _ Empty            = Empty+unsafeFmap f (Single x)       = Single (f x)+unsafeFmap f (Deep v pr m sf) = Deep v (mapDigit f pr) (unsafeFmap (unsafeFmapNode f) m) (mapDigit f sf)  unsafeFmapNode :: (a -> b) -> Node v a -> Node v b unsafeFmapNode f (Node2 v a b)   = Node2 v (f a) (f b) unsafeFmapNode f (Node3 v a b c) = Node3 v (f a) (f b) (f c)  -- | Like 'traverse', but with a more constrained type.-traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) =>-    (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)+traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) traverse' = traverseTree -traverseTree :: (Measured v2 a2, Applicative f) =>-    (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)+traverseTree :: (Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) traverseTree _ Empty = pure Empty traverseTree f (Single x) = Single <$> f x-traverseTree f (Deep _ pr m sf) =-    deep <$> traverseDigit f pr <*> traverseTree (traverseNode f) m <*> traverseDigit f sf+traverseTree f (Deep _ pr m sf) = deep+  <$> traverseDigit f pr+  <*> traverseTree (traverseNode f) m+  <*> traverseDigit f sf -traverseNode :: (Measured v2 a2, Applicative f) =>-    (a1 -> f a2) -> Node v1 a1 -> f (Node v2 a2)+traverseNode :: (Measured v2 a2, Applicative f) => (a1 -> f a2) -> Node v1 a1 -> f (Node v2 a2) traverseNode f (Node2 _ a b)   = node2 <$> f a <*> f b traverseNode f (Node3 _ a b c) = node3 <$> f a <*> f b <*> f c  traverseDigit :: (Applicative f) => (a -> f b) -> Digit a -> f (Digit b)-traverseDigit f (One a)        = One <$> f a-traverseDigit f (Two a b)      = Two <$> f a <*> f b+traverseDigit f (One a)        = One   <$> f a+traverseDigit f (Two a b)      = Two   <$> f a <*> f b traverseDigit f (Three a b c)  = Three <$> f a <*> f b <*> f c-traverseDigit f (Four a b c d) = Four <$> f a <*> f b <*> f c <*> f d+traverseDigit f (Four a b c d) = Four  <$> f a <*> f b <*> f c <*> f d  -- | Traverse the tree with a function that also takes the -- measure of the prefix of the tree to the left of the element.-traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) =>-    (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)+traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) traverseWithPos f = traverseWPTree f mempty -traverseWPTree :: (Measured v1 a1, Measured v2 a2, Applicative f) =>-    (v1 -> a1 -> f a2) -> v1 -> FingerTree v1 a1 -> f (FingerTree v2 a2)+traverseWPTree :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> v1 -> FingerTree v1 a1 -> f (FingerTree v2 a2) traverseWPTree _ _ Empty = pure Empty traverseWPTree f v (Single x) = Single <$> f v x-traverseWPTree f v (Deep _ pr m sf) =-    deep <$> traverseWPDigit f v pr <*> traverseWPTree (traverseWPNode f) vpr m <*> traverseWPDigit f vm sf-  where-    vpr     =  v    `mappend`  measure pr-    vm      =  vpr  `mappendVal` m+traverseWPTree f v (Deep _ pr m sf) = deep+  <$> traverseWPDigit f v pr+  <*> traverseWPTree (traverseWPNode f) vpr m+  <*> traverseWPDigit f vm sf+  where vpr = v   `mappend`  measure pr+        vm  = vpr `mappendVal` m -traverseWPNode :: (Measured v1 a1, Measured v2 a2, Applicative f) =>-    (v1 -> a1 -> f a2) -> v1 -> Node v1 a1 -> f (Node v2 a2)+traverseWPNode :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> v1 -> Node v1 a1 -> f (Node v2 a2) traverseWPNode f v (Node2 _ a b) = node2 <$> f v a <*> f va b-  where-    va      = v `mappend` measure a+  where va = v `mappend` measure a traverseWPNode f v (Node3 _ a b c) = node3 <$> f v a <*> f va b <*> f vab c-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b+  where va  = v  `mappend` measure a+        vab = va `mappend` measure b -traverseWPDigit :: (Measured v a, Applicative f) =>-    (v -> a -> f b) -> v -> Digit a -> f (Digit b)+traverseWPDigit :: (Measured v a, Applicative f) => (v -> a -> f b) -> v -> Digit a -> f (Digit b) traverseWPDigit f v (One a) = One <$> f v a traverseWPDigit f v (Two a b) = Two <$> f v a <*> f va b-  where-    va      = v `mappend` measure a+  where va = v `mappend` measure a traverseWPDigit f v (Three a b c) = Three <$> f v a <*> f va b <*> f vab c-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b+  where va  = v  `mappend` measure a+        vab = va `mappend` measure b traverseWPDigit f v (Four a b c d) = Four <$> f v a <*> f va b <*> f vab c <*> f vabc d-  where-    va      = v `mappend` measure a-    vab     = va `mappend` measure b-    vabc    = vab `mappend` measure c+  where va   = v   `mappend` measure a+        vab  = va  `mappend` measure b+        vabc = vab `mappend` measure c  -- | Like 'traverse', but safe only if the function preserves the measure.-unsafeTraverse :: (Applicative f) =>-    (a -> f b) -> FingerTree v a -> f (FingerTree v b)+unsafeTraverse :: (Applicative f) => (a -> f b) -> FingerTree v a -> f (FingerTree v b) unsafeTraverse _ Empty = pure Empty unsafeTraverse f (Single x) = Single <$> f x-unsafeTraverse f (Deep v pr m sf) =-    Deep v <$> traverseDigit f pr <*> unsafeTraverse (unsafeTraverseNode f) m <*> traverseDigit f sf+unsafeTraverse f (Deep v pr m sf) = Deep v+  <$> traverseDigit f pr+  <*> unsafeTraverse (unsafeTraverseNode f) m+  <*> traverseDigit f sf -unsafeTraverseNode :: (Applicative f) =>-    (a -> f b) -> Node v a -> f (Node v b)+unsafeTraverseNode :: (Applicative f) => (a -> f b) -> Node v a -> f (Node v b) unsafeTraverseNode f (Node2 v a b)   = Node2 v <$> f a <*> f b unsafeTraverseNode f (Node3 v a b c) = Node3 v <$> f a <*> f b <*> f c @@ -385,34 +363,30 @@ -- | /O(1)/. Add an element to the left end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end. (<|) :: (Measured v a) => a -> FingerTree v a -> FingerTree v a-a <| Empty              =  Single a-a <| Single b           =  deep (One a) Empty (One b)-a <| Deep v (Four b c d e) m sf = m `seq`-    Deep (measure a `mappend` v) (Two a b) (node3 c d e <| m) sf-a <| Deep v pr m sf     =-    Deep (measure a `mappend` v) (consDigit a pr) m sf+a <| Empty                      = Single a+a <| Single b                   = deep (One a) Empty (One b)+a <| Deep v (Four b c d e) m sf = m `seq` Deep (measure a `mappend` v) (Two a b) (node3 c d e <| m) sf+a <| Deep v pr m sf             = Deep (measure a `mappend` v) (consDigit a pr) m sf  consDigit :: a -> Digit a -> Digit a consDigit a (One b)        = Two a b consDigit a (Two b c)      = Three a b c consDigit a (Three b c d)  = Four a b c d-consDigit _ (Four _ _ _ _) = illegal_argument "consDigit"+consDigit _ (Four _ _ _ _) = illegalArgument "consDigit"  -- | /O(1)/. Add an element to the right end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end. (|>) :: (Measured v a) => FingerTree v a -> a -> FingerTree v a-Empty |> a              =  Single a-Single a |> b           =  deep (One a) Empty (One b)-Deep v pr m (Four a b c d) |> e = m `seq`-    Deep (v `mappend` measure e) pr (m |> node3 a b c) (Two d e)-Deep v pr m sf |> x     =-    Deep (v `mappend` measure x) pr m (snocDigit sf x)+Empty |> a                      = Single a+Single a |> b                   = deep (One a) Empty (One b)+Deep v pr m (Four a b c d) |> e = m `seq` Deep (v `mappend` measure e) pr (m |> node3 a b c) (Two d e)+Deep v pr m sf |> x             = Deep (v `mappend` measure x) pr m (snocDigit sf x)  snocDigit :: Digit a -> a -> Digit a snocDigit (One a) b        = Two a b snocDigit (Two a b) c      = Three a b c snocDigit (Three a b c) d  = Four a b c d-snocDigit (Four _ _ _ _) _ = illegal_argument "snocDigit"+snocDigit (Four _ _ _ _) _ = illegalArgument "snocDigit"  -- | /O(1)/. Is this the empty sequence? null :: (Measured v a) => FingerTree v a -> Bool@@ -427,9 +401,9 @@ viewl (Deep _ pr m sf)      =  lheadDigit pr :< deep (ltailDigit pr) m sf  rotL :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> FingerTree v a-rotL m sf      =   case viewl m of-    EmptyL  ->  digitToTree sf-    a :< m' ->  Deep (measure m `mappend` measure sf) (nodeToDigit a) m' sf+rotL m sf = case viewl m of+  EmptyL  -> digitToTree sf+  a :< m' -> Deep (measure m `mappend` measure sf) (nodeToDigit a) m' sf  lheadDigit :: Digit a -> a lheadDigit (One a)        = a@@ -438,7 +412,7 @@ lheadDigit (Four a _ _ _) = a  ltailDigit :: Digit a -> Digit a-ltailDigit (One _)        = illegal_argument "ltailDigit"+ltailDigit (One _)        = illegalArgument "ltailDigit" ltailDigit (Two _ b)      = One b ltailDigit (Three _ b c)  = Two b c ltailDigit (Four _ b c d) = Three b c d@@ -452,8 +426,8 @@  rotR :: (Measured v a) => Digit a -> FingerTree v (Node v a) -> FingerTree v a rotR pr m = case viewr m of-    EmptyR  ->  digitToTree pr-    m' :> a ->  Deep (measure pr `mappendVal` m) pr m' (nodeToDigit a)+  EmptyR  -> digitToTree pr+  m' :> a -> Deep (measure pr `mappendVal` m) pr m' (nodeToDigit a)  rheadDigit :: Digit a -> a rheadDigit (One a)        = a@@ -462,7 +436,7 @@ rheadDigit (Four _ _ _ d) = d  rtailDigit :: Digit a -> Digit a-rtailDigit (One _)        = illegal_argument "rtailDigit"+rtailDigit (One _)        = illegalArgument "rtailDigit" rtailDigit (Two a _)      = One a rtailDigit (Three a b _)  = Two a b rtailDigit (Four a b c _) = Three a b c@@ -482,234 +456,129 @@ (><) =  appendTree0  appendTree0 :: (Measured v a) => FingerTree v a -> FingerTree v a -> FingerTree v a-appendTree0 Empty xs =-    xs-appendTree0 xs Empty =-    xs-appendTree0 (Single x) xs =-    x <| xs-appendTree0 xs (Single x) =-    xs |> x-appendTree0 (Deep _ pr1 m1 sf1) (Deep _ pr2 m2 sf2) =-    deep pr1 (addDigits0 m1 sf1 pr2 m2) sf2+appendTree0 Empty xs                                = xs+appendTree0 xs Empty                                = xs+appendTree0 (Single x) xs                           = x <| xs+appendTree0 xs (Single x)                           = xs |> x+appendTree0 (Deep _ pr1 m1 sf1) (Deep _ pr2 m2 sf2) = deep pr1 (addDigits0 m1 sf1 pr2 m2) sf2  addDigits0 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)-addDigits0 m1 (One a) (One b) m2 =-    appendTree1 m1 (node2 a b) m2-addDigits0 m1 (One a) (Two b c) m2 =-    appendTree1 m1 (node3 a b c) m2-addDigits0 m1 (One a) (Three b c d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits0 m1 (One a) (Four b c d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits0 m1 (Two a b) (One c) m2 =-    appendTree1 m1 (node3 a b c) m2-addDigits0 m1 (Two a b) (Two c d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits0 m1 (Two a b) (Three c d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits0 m1 (Two a b) (Four c d e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits0 m1 (Three a b c) (One d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits0 m1 (Three a b c) (Two d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits0 m1 (Three a b c) (Three d e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits0 m1 (Three a b c) (Four d e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits0 m1 (Four a b c d) (One e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits0 m1 (Four a b c d) (Two e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits0 m1 (Four a b c d) (Three e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits0 m1 (Four a b c d) (Four e f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2+addDigits0 m1 (One    a       ) (One    b       ) m2 = appendTree1 m1 (node2 a b  )                           m2+addDigits0 m1 (One    a       ) (Two    b c     ) m2 = appendTree1 m1 (node3 a b c)                           m2+addDigits0 m1 (One    a       ) (Three  b c d   ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )             m2+addDigits0 m1 (One    a       ) (Four   b c d e ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )             m2+addDigits0 m1 (Two    a b     ) (One    c       ) m2 = appendTree1 m1 (node3 a b c)                           m2+addDigits0 m1 (Two    a b     ) (Two    c d     ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )             m2+addDigits0 m1 (Two    a b     ) (Three  c d e   ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )             m2+addDigits0 m1 (Two    a b     ) (Four   c d e f ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)             m2+addDigits0 m1 (Three  a b c   ) (One    d       ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )             m2+addDigits0 m1 (Three  a b c   ) (Two    d e     ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )             m2+addDigits0 m1 (Three  a b c   ) (Three  d e f   ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)             m2+addDigits0 m1 (Three  a b c   ) (Four   d e f g ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g) m2+addDigits0 m1 (Four   a b c d ) (One    e       ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )             m2+addDigits0 m1 (Four   a b c d ) (Two    e f     ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)             m2+addDigits0 m1 (Four   a b c d ) (Three  e f g   ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g) m2+addDigits0 m1 (Four   a b c d ) (Four   e f g h ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2  appendTree1 :: (Measured v a) => FingerTree v a -> a -> FingerTree v a -> FingerTree v a-appendTree1 Empty a xs =-    a <| xs-appendTree1 xs a Empty =-    xs |> a-appendTree1 (Single x) a xs =-    x <| a <| xs-appendTree1 xs a (Single x) =-    xs |> a |> x-appendTree1 (Deep _ pr1 m1 sf1) a (Deep _ pr2 m2 sf2) =-    deep pr1 (addDigits1 m1 sf1 a pr2 m2) sf2+appendTree1 Empty a xs                                = a <| xs+appendTree1 xs a Empty                                = xs |> a+appendTree1 (Single x) a xs                           = x <| a <| xs+appendTree1 xs a (Single x)                           = xs |> a |> x+appendTree1 (Deep _ pr1 m1 sf1) a (Deep _ pr2 m2 sf2) = deep pr1 (addDigits1 m1 sf1 a pr2 m2) sf2  addDigits1 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)-addDigits1 m1 (One a) b (One c) m2 =-    appendTree1 m1 (node3 a b c) m2-addDigits1 m1 (One a) b (Two c d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits1 m1 (One a) b (Three c d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits1 m1 (One a) b (Four c d e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits1 m1 (Two a b) c (One d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits1 m1 (Two a b) c (Two d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits1 m1 (Two a b) c (Three d e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits1 m1 (Two a b) c (Four d e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits1 m1 (Three a b c) d (One e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits1 m1 (Three a b c) d (Two e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits1 m1 (Three a b c) d (Three e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits1 m1 (Three a b c) d (Four e f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits1 m1 (Four a b c d) e (One f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits1 m1 (Four a b c d) e (Two f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits1 m1 (Four a b c d) e (Three f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits1 m1 (Four a b c d) e (Four f g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2+addDigits1 m1 (One    a       ) b (One    c       ) m2 = appendTree1 m1 (node3 a b c)                             m2+addDigits1 m1 (One    a       ) b (Two    c d     ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )               m2+addDigits1 m1 (One    a       ) b (Three  c d e   ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )               m2+addDigits1 m1 (One    a       ) b (Four   c d e f ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)               m2+addDigits1 m1 (Two    a b     ) c (One    d       ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )               m2+addDigits1 m1 (Two    a b     ) c (Two    d e     ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )               m2+addDigits1 m1 (Two    a b     ) c (Three  d e f   ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)               m2+addDigits1 m1 (Two    a b     ) c (Four   d e f g ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  ) m2+addDigits1 m1 (Three  a b c   ) d (One    e       ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )               m2+addDigits1 m1 (Three  a b c   ) d (Two    e f     ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)               m2+addDigits1 m1 (Three  a b c   ) d (Three  e f g   ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  ) m2+addDigits1 m1 (Three  a b c   ) d (Four   e f g h ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  ) m2+addDigits1 m1 (Four   a b c d ) e (One    f       ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)               m2+addDigits1 m1 (Four   a b c d ) e (Two    f g     ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  ) m2+addDigits1 m1 (Four   a b c d ) e (Three  f g h   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  ) m2+addDigits1 m1 (Four   a b c d ) e (Four   f g h i ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2  appendTree2 :: (Measured v a) => FingerTree v a -> a -> a -> FingerTree v a -> FingerTree v a-appendTree2 Empty a b xs =-    a <| b <| xs-appendTree2 xs a b Empty =-    xs |> a |> b-appendTree2 (Single x) a b xs =-    x <| a <| b <| xs-appendTree2 xs a b (Single x) =-    xs |> a |> b |> x-appendTree2 (Deep _ pr1 m1 sf1) a b (Deep _ pr2 m2 sf2) =-    deep pr1 (addDigits2 m1 sf1 a b pr2 m2) sf2+appendTree2 Empty a b xs                                = a <| b <| xs+appendTree2 xs a b Empty                                = xs |> a |> b+appendTree2 (Single x) a b xs                           = x <| a <| b <| xs+appendTree2 xs a b (Single x)                           = xs |> a |> b |> x+appendTree2 (Deep _ pr1 m1 sf1) a b (Deep _ pr2 m2 sf2) = deep pr1 (addDigits2 m1 sf1 a b pr2 m2) sf2  addDigits2 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)-addDigits2 m1 (One a) b c (One d) m2 =-    appendTree2 m1 (node2 a b) (node2 c d) m2-addDigits2 m1 (One a) b c (Two d e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits2 m1 (One a) b c (Three d e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits2 m1 (One a) b c (Four d e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits2 m1 (Two a b) c d (One e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits2 m1 (Two a b) c d (Two e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits2 m1 (Two a b) c d (Three e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits2 m1 (Two a b) c d (Four e f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits2 m1 (Three a b c) d e (One f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits2 m1 (Three a b c) d e (Two f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits2 m1 (Three a b c) d e (Three f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits2 m1 (Three a b c) d e (Four f g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits2 m1 (Four a b c d) e f (One g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits2 m1 (Four a b c d) e f (Two g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits2 m1 (Four a b c d) e f (Three g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits2 m1 (Four a b c d) e f (Four g h i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2+addDigits2 m1 (One    a       ) b c (One    d       ) m2 = appendTree2 m1 (node2 a b  ) (node2 c d  )                           m2+addDigits2 m1 (One    a       ) b c (Two    d e     ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )                           m2+addDigits2 m1 (One    a       ) b c (Three  d e f   ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                           m2+addDigits2 m1 (One    a       ) b c (Four   d e f g ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits2 m1 (Two    a b     ) c d (One    e       ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )                           m2+addDigits2 m1 (Two    a b     ) c d (Two    e f     ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                           m2+addDigits2 m1 (Two    a b     ) c d (Three  e f g   ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits2 m1 (Two    a b     ) c d (Four   e f g h ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits2 m1 (Three  a b c   ) d e (One    f       ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                           m2+addDigits2 m1 (Three  a b c   ) d e (Two    f g     ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits2 m1 (Three  a b c   ) d e (Three  f g h   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits2 m1 (Three  a b c   ) d e (Four   f g h i ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)             m2+addDigits2 m1 (Four   a b c d ) e f (One    g       ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits2 m1 (Four   a b c d ) e f (Two    g h     ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits2 m1 (Four   a b c d ) e f (Three  g h i   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)             m2+addDigits2 m1 (Four   a b c d ) e f (Four   g h i j ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j) m2  appendTree3 :: (Measured v a) => FingerTree v a -> a -> a -> a -> FingerTree v a -> FingerTree v a-appendTree3 Empty a b c xs =-    a <| b <| c <| xs-appendTree3 xs a b c Empty =-    xs |> a |> b |> c-appendTree3 (Single x) a b c xs =-    x <| a <| b <| c <| xs-appendTree3 xs a b c (Single x) =-    xs |> a |> b |> c |> x-appendTree3 (Deep _ pr1 m1 sf1) a b c (Deep _ pr2 m2 sf2) =-    deep pr1 (addDigits3 m1 sf1 a b c pr2 m2) sf2+appendTree3 Empty a b c xs                                = a <| b <| c <| xs+appendTree3 xs a b c Empty                                = xs |> a |> b |> c+appendTree3 (Single x) a b c xs                           = x <| a <| b <| c <| xs+appendTree3 xs a b c (Single x)                           = xs |> a |> b |> c |> x+appendTree3 (Deep _ pr1 m1 sf1) a b c (Deep _ pr2 m2 sf2) = deep pr1 (addDigits3 m1 sf1 a b c pr2 m2) sf2  addDigits3 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)-addDigits3 m1 (One a) b c d (One e) m2 =-    appendTree2 m1 (node3 a b c) (node2 d e) m2-addDigits3 m1 (One a) b c d (Two e f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits3 m1 (One a) b c d (Three e f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits3 m1 (One a) b c d (Four e f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits3 m1 (Two a b) c d e (One f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits3 m1 (Two a b) c d e (Two f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits3 m1 (Two a b) c d e (Three f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits3 m1 (Two a b) c d e (Four f g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits3 m1 (Three a b c) d e f (One g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits3 m1 (Three a b c) d e f (Two g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits3 m1 (Three a b c) d e f (Three g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits3 m1 (Three a b c) d e f (Four g h i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2-addDigits3 m1 (Four a b c d) e f g (One h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits3 m1 (Four a b c d) e f g (Two h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits3 m1 (Four a b c d) e f g (Three h i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2-addDigits3 m1 (Four a b c d) e f g (Four h i j k) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k) m2+addDigits3 m1 (One    a       ) b c d (One    e       ) m2 = appendTree2 m1 (node3 a b c) (node2 d e  )                           m2+addDigits3 m1 (One    a       ) b c d (Two    e f     ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                           m2+addDigits3 m1 (One    a       ) b c d (Three  e f g   ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits3 m1 (One    a       ) b c d (Four   e f g h ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits3 m1 (Two    a b     ) c d e (One    f       ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                           m2+addDigits3 m1 (Two    a b     ) c d e (Two    f g     ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits3 m1 (Two    a b     ) c d e (Three  f g h   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits3 m1 (Two    a b     ) c d e (Four   f g h i ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)             m2+addDigits3 m1 (Three  a b c   ) d e f (One    g       ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )             m2+addDigits3 m1 (Three  a b c   ) d e f (Two    g h     ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits3 m1 (Three  a b c   ) d e f (Three  g h i   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)             m2+addDigits3 m1 (Three  a b c   ) d e f (Four   g h i j ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j) m2+addDigits3 m1 (Four   a b c d ) e f g (One    h       ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )             m2+addDigits3 m1 (Four   a b c d ) e f g (Two    h i     ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)             m2+addDigits3 m1 (Four   a b c d ) e f g (Three  h i j   ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j) m2+addDigits3 m1 (Four   a b c d ) e f g (Four   h i j k ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k) m2  appendTree4 :: (Measured v a) => FingerTree v a -> a -> a -> a -> a -> FingerTree v a -> FingerTree v a-appendTree4 Empty a b c d xs =-    a <| b <| c <| d <| xs-appendTree4 xs a b c d Empty =-    xs |> a |> b |> c |> d-appendTree4 (Single x) a b c d xs =-    x <| a <| b <| c <| d <| xs-appendTree4 xs a b c d (Single x) =-    xs |> a |> b |> c |> d |> x-appendTree4 (Deep _ pr1 m1 sf1) a b c d (Deep _ pr2 m2 sf2) =-    deep pr1 (addDigits4 m1 sf1 a b c d pr2 m2) sf2+appendTree4 Empty a b c d xs                                = a <| b <| c <| d <| xs+appendTree4 xs a b c d Empty                                = xs |> a |> b |> c |> d+appendTree4 (Single x) a b c d xs                           = x <| a <| b <| c <| d <| xs+appendTree4 xs a b c d (Single x)                           = xs |> a |> b |> c |> d |> x+appendTree4 (Deep _ pr1 m1 sf1) a b c d (Deep _ pr2 m2 sf2) = deep pr1 (addDigits4 m1 sf1 a b c d pr2 m2) sf2  addDigits4 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)-addDigits4 m1 (One a) b c d e (One f) m2 =-    appendTree2 m1 (node3 a b c) (node3 d e f) m2-addDigits4 m1 (One a) b c d e (Two f g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits4 m1 (One a) b c d e (Three f g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits4 m1 (One a) b c d e (Four f g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits4 m1 (Two a b) c d e f (One g) m2 =-    appendTree3 m1 (node3 a b c) (node2 d e) (node2 f g) m2-addDigits4 m1 (Two a b) c d e f (Two g h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits4 m1 (Two a b) c d e f (Three g h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits4 m1 (Two a b) c d e f (Four g h i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2-addDigits4 m1 (Three a b c) d e f g (One h) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2-addDigits4 m1 (Three a b c) d e f g (Two h i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits4 m1 (Three a b c) d e f g (Three h i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2-addDigits4 m1 (Three a b c) d e f g (Four h i j k) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k) m2-addDigits4 m1 (Four a b c d) e f g h (One i) m2 =-    appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2-addDigits4 m1 (Four a b c d) e f g h (Two i j) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2-addDigits4 m1 (Four a b c d) e f g h (Three i j k) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k) m2-addDigits4 m1 (Four a b c d) e f g h (Four i j k l) m2 =-    appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node3 j k l) m2+addDigits4 m1 (One    a       ) b c d e (One    f       ) m2 = appendTree2 m1 (node3 a b c) (node3 d e f)                             m2+addDigits4 m1 (One    a       ) b c d e (Two    f g     ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )               m2+addDigits4 m1 (One    a       ) b c d e (Three  f g h   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )               m2+addDigits4 m1 (One    a       ) b c d e (Four   f g h i ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)               m2+addDigits4 m1 (Two    a b     ) c d e f (One    g       ) m2 = appendTree3 m1 (node3 a b c) (node2 d e  ) (node2 f g  )               m2+addDigits4 m1 (Two    a b     ) c d e f (Two    g h     ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )               m2+addDigits4 m1 (Two    a b     ) c d e f (Three  g h i   ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)               m2+addDigits4 m1 (Two    a b     ) c d e f (Four   g h i j ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j  ) m2+addDigits4 m1 (Three  a b c   ) d e f g (One    h       ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h  )               m2+addDigits4 m1 (Three  a b c   ) d e f g (Two    h i     ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)               m2+addDigits4 m1 (Three  a b c   ) d e f g (Three  h i j   ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j  ) m2+addDigits4 m1 (Three  a b c   ) d e f g (Four   h i j k ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k  ) m2+addDigits4 m1 (Four   a b c d ) e f g h (One    i       ) m2 = appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i)               m2+addDigits4 m1 (Four   a b c d ) e f g h (Two    i j     ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h  ) (node2 i j  ) m2+addDigits4 m1 (Four   a b c d ) e f g h (Three  i j k   ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k  ) m2+addDigits4 m1 (Four   a b c d ) e f g h (Four   i j k l ) m2 = appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node3 j k l) m2  ---------------- -- 4.4 Splitting@@ -720,14 +589,12 @@ -- -- For predictable results, one should ensure that there is only one such -- point, i.e. that the predicate is /monotonic/.-split ::  (Measured v a) =>-      (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)+split :: (Measured v a) => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a) split _ Empty  =  (Empty, Empty) split p xs-  | p (measure xs) =  (l, x <| r)-  | otherwise   =  (xs, Empty)-  where-    Split l x r = splitTree p mempty xs+  | p (measure xs)  =  (l, x <| r)+  | otherwise       =  (xs, Empty)+  where Split l x r = splitTree p mempty xs  -- | /O(log(min(i,n-i)))/. -- Given a monotonic predicate @p@, @'takeUntil' p t@ is the largest@@ -747,9 +614,8 @@  data Split t a = Split t a t -splitTree :: (Measured v a) =>-    (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a-splitTree _ _ Empty = illegal_argument "splitTree"+splitTree :: (Measured v a) => (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a+splitTree _ _ Empty = illegalArgument "splitTree" splitTree _ _ (Single x) = Split Empty x Empty splitTree p i (Deep _ pr m sf)   | p vpr       =  let  Split l x r     =  splitDigit p i pr@@ -759,64 +625,54 @@                    in   Split (deepR pr  ml l) x (deepL r mr sf)   | otherwise   =  let  Split l x r     =  splitDigit p vm sf                    in   Split (deepR pr  m  l) x (maybe Empty digitToTree r)-  where-    vpr     =  i    `mappend`  measure pr-    vm      =  vpr  `mappendVal` m+  where vpr =  i    `mappend`  measure pr+        vm  =  vpr  `mappendVal` m  -- Avoid relying on right identity (cf Exercise 7) mappendVal :: (Measured v a) => v -> FingerTree v a -> v mappendVal v Empty = v mappendVal v t     = v `mappend` measure t -deepL :: (Measured v a) =>-    Maybe (Digit a) -> FingerTree v (Node v a) -> Digit a -> FingerTree v a+deepL :: (Measured v a) => Maybe (Digit a) -> FingerTree v (Node v a) -> Digit a -> FingerTree v a deepL Nothing m sf   =   rotL m sf deepL (Just pr) m sf =   deep pr m sf -deepR :: (Measured v a) =>-    Digit a -> FingerTree v (Node v a) -> Maybe (Digit a) -> FingerTree v a+deepR :: (Measured v a) => Digit a -> FingerTree v (Node v a) -> Maybe (Digit a) -> FingerTree v a deepR pr m Nothing   =   rotR pr m deepR pr m (Just sf) =   deep pr m sf -splitNode :: (Measured v a) => (v -> Bool) -> v -> Node v a ->-    Split (Maybe (Digit a)) a+splitNode :: (Measured v a) => (v -> Bool) -> v -> Node v a -> Split (Maybe (Digit a)) a splitNode p i (Node2 _ a b)-  | p va        = Split Nothing a (Just (One b))-  | otherwise   = Split (Just (One a)) b Nothing-  where-    va      = i `mappend` measure a+  | p va      = Split Nothing a (Just (One b))+  | otherwise = Split (Just (One a)) b Nothing+  where va = i `mappend` measure a splitNode p i (Node3 _ a b c)-  | p va        = Split Nothing a (Just (Two b c))-  | p vab       = Split (Just (One a)) b (Just (One c))-  | otherwise   = Split (Just (Two a b)) c Nothing-  where-    va      = i `mappend` measure a-    vab     = va `mappend` measure b+  | p va      = Split Nothing a (Just (Two b c))+  | p vab     = Split (Just (One a)) b (Just (One c))+  | otherwise = Split (Just (Two a b)) c Nothing+  where va  = i  `mappend` measure a+        vab = va `mappend` measure b -splitDigit :: (Measured v a) => (v -> Bool) -> v -> Digit a ->-    Split (Maybe (Digit a)) a+splitDigit :: (Measured v a) => (v -> Bool) -> v -> Digit a -> Split (Maybe (Digit a)) a splitDigit _ i (One a) = i `seq` Split Nothing a Nothing splitDigit p i (Two a b)   | p va        = Split Nothing a (Just (One b))   | otherwise   = Split (Just (One a)) b Nothing-  where-    va      = i `mappend` measure a+  where va = i `mappend` measure a splitDigit p i (Three a b c)   | p va        = Split Nothing a (Just (Two b c))   | p vab       = Split (Just (One a)) b (Just (One c))   | otherwise   = Split (Just (Two a b)) c Nothing-  where-    va      = i `mappend` measure a-    vab     = va `mappend` measure b+  where va  = i `mappend` measure a+        vab = va `mappend` measure b splitDigit p i (Four a b c d)   | p va        = Split Nothing a (Just (Three b c d))   | p vab       = Split (Just (One a)) b (Just (Two c d))   | p vabc      = Split (Just (Two a b)) c (Just (One d))   | otherwise   = Split (Just (Three a b c)) d Nothing-  where-    va      = i `mappend` measure a-    vab     = va `mappend` measure b-    vabc    = vab `mappend` measure c+  where va    = i `mappend` measure a+        vab   = va `mappend` measure b+        vabc  = vab `mappend` measure c  ------------------ -- Transformations@@ -827,10 +683,9 @@ reverse = reverseTree id  reverseTree :: (Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2-reverseTree _ Empty = Empty-reverseTree f (Single x) = Single (f x)-reverseTree f (Deep _ pr m sf) =-    deep (reverseDigit f sf) (reverseTree (reverseNode f) m) (reverseDigit f pr)+reverseTree _ Empty            = Empty+reverseTree f (Single x)       = Single (f x)+reverseTree f (Deep _ pr m sf) = deep (reverseDigit f sf) (reverseTree (reverseNode f) m) (reverseDigit f pr)  reverseNode :: (Measured v2 a2) => (a1 -> a2) -> Node v1 a1 -> Node v2 a2 reverseNode f (Node2 _ a b)   = node2 (f b) (f a)@@ -842,9 +697,8 @@ reverseDigit f (Three a b c)  = Three (f c) (f b) (f a) reverseDigit f (Four a b c d) = Four (f d) (f c) (f b) (f a) -illegal_argument :: String -> a-illegal_argument name =-    error $ "Logic error: " ++ name ++ " called with illegal argument"+illegalArgument :: String -> a+illegalArgument name = error $ "Logic error: " ++ name ++ " called with illegal argument"  {- $example 

@@ -35,14 +35,21 @@ -- ----------------------------------------------------------------------------- -module HaskellWorks.Data.IntervalMap.FingerTree (-    -- * Intervals-    Interval(..), point,+module HaskellWorks.Data.IntervalMap.FingerTree+  ( -- * Intervals+    Interval(..)+  , point     -- * Interval maps-    IntervalMap(..), empty, singleton, insert, union,+  , IntervalMap(..)+  , empty+  , singleton+  , insert+  , union     -- * Searching-    search, intersections, dominators-    ) where+  , search+  , intersections+  , dominators+  ) where  import Control.Applicative          ((<$>)) import Control.DeepSeq@@ -62,7 +69,7 @@ -- | A closed interval.  The lower bound should be less than or equal -- to the higher bound. data Interval v = Interval { low :: v, high :: v }-    deriving (Eq, Ord, Show, Generic, NFData)+  deriving (Eq, Ord, Show, Generic, NFData)  -- | An interval in which the lower and upper bounds are equal. point :: v -> Interval v@@ -71,13 +78,13 @@ data Node v a = Node (Interval v) a deriving (Generic, NFData)  instance Functor (Node v) where-    fmap f (Node i x) = Node i (f x)+  fmap f (Node i x) = Node i (f x)  instance Foldable (Node v) where-    foldMap f (Node _ x) = f x+  foldMap f (Node _ x) = f x  instance Traversable (Node v) where-    traverse f (Node i x) = Node i <$> f x+  traverse f (Node i x) = Node i <$> f x  -- rightmost interval (including largest lower bound) and largest upper bound. data IntInterval v = NoInterval | IntInterval (Interval v) v deriving (Generic, NFData)@@ -99,25 +106,24 @@   {-# INLINE mappend #-}  instance (Ord v) => Measured (IntInterval v) (Node v a) where-    measure (Node i _) = IntInterval i (high i)+  measure (Node i _) = IntInterval i (high i)  -- | Map of closed intervals, possibly with duplicates. -- The 'Foldable' and 'Traversable' instances process the intervals in -- lexicographical order. newtype IntervalMap v a =-    IntervalMap (FingerTree (IntInterval v) (Node v a))-    deriving (Generic, NFData)+  IntervalMap (FingerTree (IntInterval v) (Node v a))+  deriving (Generic, NFData) -- ordered lexicographically by interval  instance Functor (IntervalMap v) where-    fmap f (IntervalMap t) = IntervalMap (FT.unsafeFmap (fmap f) t)+  fmap f (IntervalMap t) = IntervalMap (FT.unsafeFmap (fmap f) t)  instance Foldable (IntervalMap v) where-    foldMap f (IntervalMap t) = foldMap (foldMap f) t+  foldMap f (IntervalMap t) = foldMap (foldMap f) t  instance Traversable (IntervalMap v) where-    traverse f (IntervalMap t) =-        IntervalMap <$> FT.unsafeTraverse (traverse f) t+  traverse f (IntervalMap t) = IntervalMap <$> FT.unsafeTraverse (traverse f) t  instance (Ord v) => S.Semigroup (IntervalMap v a) where   (<>) = union@@ -125,10 +131,10 @@  -- | 'empty' and 'union'. instance (Ord v) => Monoid (IntervalMap v a) where-    mempty = empty-    {-# INLINE mempty #-}-    mappend = union-    {-# INLINE mappend #-}+  mempty = empty+  {-# INLINE mempty #-}+  mappend = union+  {-# INLINE mappend #-}  -- | /O(1)/.  The empty interval map. empty :: (Ord v) => IntervalMap v a@@ -144,31 +150,27 @@ insert :: (Ord v) => Interval v -> a -> IntervalMap v a -> IntervalMap v a insert (Interval lo hi) _ m | lo > hi = m insert i x (IntervalMap t) = IntervalMap (l >< Node i x <| r)-  where-    (l, r) = FT.split larger t-    larger (IntInterval k _) = k >= i-    larger NoInterval        = error "larger NoInterval"+  where (l, r) = FT.split larger t+        larger (IntInterval k _) = k >= i+        larger NoInterval        = error "larger NoInterval"  -- | /O(m log (n/\//m))/.  Merge two interval maps. -- The map may contain duplicate intervals; entries with equal intervals -- are kept in the original order.-union  ::  (Ord v) => IntervalMap v a -> IntervalMap v a -> IntervalMap v a+union  :: (Ord v) => IntervalMap v a -> IntervalMap v a -> IntervalMap v a union (IntervalMap xs) (IntervalMap ys) = IntervalMap (merge1 xs ys)-  where-    merge1 as bs = case FT.viewl as of-        EmptyL                  -> bs-        a@(Node i _) :< as'     -> l >< a <| merge2 as' r-          where-            (l, r) = FT.split larger bs-            larger (IntInterval k _) = k >= i-            larger NoInterval        = error "larger NoInterval"-    merge2 as bs = case FT.viewl bs of-        EmptyL                  -> as-        b@(Node i _) :< bs'     -> l >< b <| merge1 r bs'-          where-            (l, r) = FT.split larger as-            larger (IntInterval k _) = k > i-            larger NoInterval        = error "larger NoInterval"+  where merge1 as bs = case FT.viewl as of+          EmptyL              -> bs+          a@(Node i _) :< as' -> l >< a <| merge2 as' r+            where (l, r) = FT.split larger bs+                  larger (IntInterval k _) = k >= i+                  larger NoInterval        = error "larger NoInterval"+        merge2 as bs = case FT.viewl bs of+          EmptyL              -> as+          b@(Node i _) :< bs' -> l >< b <| merge1 r bs'+            where (l, r) = FT.split larger as+                  larger (IntInterval k _) = k > i+                  larger NoInterval        = error "larger NoInterval"  -- | /O(k log (n/\//k))/.  All intervals that intersect with the given -- interval, in lexicographical order.@@ -189,10 +191,9 @@ -- interval, in lexicographical order. inRange :: (Ord v) => v -> v -> IntervalMap v a -> [(Interval v, a)] inRange lo hi (IntervalMap t) = matches (FT.takeUntil (greater hi) t)-  where-    matches xs  =  case FT.viewl (FT.dropUntil (atleast lo) xs) of-        EmptyL          ->  []-        Node i x :< xs' ->  (i, x) : matches xs'+  where matches xs  =  case FT.viewl (FT.dropUntil (atleast lo) xs) of+          EmptyL          ->  []+          Node i x :< xs' ->  (i, x) : matches xs'  atleast :: (Ord v) => v -> IntInterval v -> Bool atleast k (IntInterval _ hi) = k <= hi

@@ -39,20 +39,20 @@ -- ----------------------------------------------------------------------------- -module HaskellWorks.Data.PriorityQueue.FingerTree (-    PQueue,+module HaskellWorks.Data.PriorityQueue.FingerTree+  ( PQueue     -- * Construction-    empty,-    singleton,-    union,-    insert,-    add,-    fromList,+  , empty+  , singleton+  , union+  , insert+  , add+  , fromList     -- * Deconstruction-    null,-    minView,-    minViewWithKey-    ) where+  , null+  , minView+  , minViewWithKey+  ) where  import Control.Arrow                ((***)) import Data.Foldable                (Foldable (foldMap))@@ -66,10 +66,10 @@ data Entry k v = Entry k v  instance Functor (Entry k) where-    fmap f (Entry k v) = Entry k (f v)+  fmap f (Entry k v) = Entry k (f v)  instance Foldable (Entry k) where-    foldMap f (Entry _ v) = f v+  foldMap f (Entry _ v) = f v  data Prio k v = NoPrio | Prio k v @@ -84,24 +84,24 @@   {-# INLINE (<>) #-}  instance Ord k => Monoid (Prio k v) where-    mempty  = NoPrio-    {-# INLINE mempty #-}-    mappend = appendPrio-    {-# INLINE mappend #-}+  mempty  = NoPrio+  {-# INLINE mempty #-}+  mappend = appendPrio+  {-# INLINE mappend #-}  instance Ord k => Measured (Prio k v) (Entry k v) where-    measure (Entry k v) = Prio k v+  measure (Entry k v) = Prio k v  -- | Priority queues. newtype PQueue k v = PQueue (FingerTree (Prio k v) (Entry k v))  instance Ord k => Functor (PQueue k) where-    fmap f (PQueue xs) = PQueue (FT.fmap' (fmap f) xs)+  fmap f (PQueue xs) = PQueue (FT.fmap' (fmap f) xs)  instance Ord k => Foldable (PQueue k) where-    foldMap f q = case minView q of-        Nothing      -> mempty-        Just (v, q') -> f v `mappend` foldMap f q'+  foldMap f q = case minView q of+    Nothing      -> mempty+    Just (v, q') -> f v `mappend` foldMap f q'  instance Ord k => S.Semigroup (PQueue k v) where   (<>) = union@@ -187,9 +187,8 @@   | otherwise = Just ((k, v), case FT.viewl r of     _ :< r' -> PQueue (l >< r')     _       -> error "can't happen")-  where-    Prio k v = measure q-    (l, r) = FT.split (below k) q+  where Prio k v = measure q+        (l, r) = FT.split (below k) q  below :: Ord k => k -> Prio k v -> Bool below _ NoPrio      = False

@@ -24,7 +24,7 @@  {-# ANN module ("HLint: ignore Redundant do"        :: String) #-} {-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}-{-# ANN module ("HLint: redundant bracket"          :: String) #-}+{-# ANN module ("HLint: ignore Redundant bracket"   :: String) #-}  spec :: Spec spec = do