content: {-# LANGUAGE FlexibleContexts #-}
  {-# LANGUAGE FlexibleInstances #-}
  {-# LANGUAGE FunctionalDependencies #-}
  {-# LANGUAGE MultiParamTypeClasses #-}
  {-# LANGUAGE UndecidableInstances #-}
  module T13429a where -- Originally FingerTree.hs from the ticket
  
  import Data.Semigroup (Semigroup(..))
  
  class (Monoid v) => Measured v a | a -> v where
      measure :: a -> v
  
  instance (Measured v a) => Measured v (Digit a) where
      measure = foldMap measure
  
  instance (Monoid v) => Measured v (Node v a) where
      measure (Node2 v _ _)    =  v
      measure (Node3 v _ _ _)  =  v
  
  instance (Measured v a) => Measured v (FingerTree v a) where
      measure Empty           =  mempty
      measure (Single x)      =  measure x
      measure (Deep v _ _ _)  =  v
  
  data FingerTree v a
      = Empty
      | Single a
      | Deep !v !(Digit a) (FingerTree v (Node v a)) !(Digit a)
    deriving Show
  
  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
  
  instance Measured v a => Semigroup (FingerTree v a) where
      (<>) = (><)
  
  instance Measured v a => Monoid (FingerTree v a) where
      mempty = empty
  
  empty :: Measured v a => FingerTree v a
  empty = Empty
  
  infixr 5 ><
  infixr 5 <|
  infixl 5 |>
  
  (<|) :: (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
  
  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"
  
  (|>) :: (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)
  
  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"
  
  (><) :: (Measured v a) => FingerTree v a -> FingerTree v a -> FingerTree v a
  (><) =  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  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
  
  data Digit a
      = One a
      | Two a a
      | Three a a a
      | Four a a a a
      deriving Show
  
  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
  
  data Node v a = Node2 !v a a | Node3 !v a a a
      deriving Show
  
  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
  
  node2        ::  (Measured v a) => a -> a -> Node v a
  node2 a b    =   Node2 (measure a `mappend` measure b) a b
  
  node3        ::  (Measured v a) => a -> a -> a -> Node v a
  node3 a b c  =   Node3 (measure a `mappend` measure b `mappend` measure c) a b c
  
  mappendVal :: (Measured v a) => v -> FingerTree v a -> v
  mappendVal v Empty = v
  mappendVal v t = v `mappend` measure t
  
  illegal_argument :: String -> a
  illegal_argument name =
      error $ "Logic error: " ++ name ++ " called with illegal argument"
  