    {-# LANGUAGE DeriveFunctor, GeneralizedNewtypeDeriving #-}

    module General.ListBuilder(
        ListBuilder, runListBuilder, newListBuilder,
        Tree(..), flattenTree, unflattenTree
        ) where

    import Data.Semigroup
    import Prelude

    -- ListBuilder is opaque outside this module
    newtype ListBuilder a = ListBuilder (Tree a)
        deriving (b -> ListBuilder a -> ListBuilder a
    NonEmpty (ListBuilder a) -> ListBuilder a
    ListBuilder a -> ListBuilder a -> ListBuilder a
    (ListBuilder a -> ListBuilder a -> ListBuilder a)
    -> (NonEmpty (ListBuilder a) -> ListBuilder a)
    -> (forall b. Integral b => b -> ListBuilder a -> ListBuilder a)
    -> Semigroup (ListBuilder a)
    forall b. Integral b => b -> ListBuilder a -> ListBuilder a
    forall a. NonEmpty (ListBuilder a) -> ListBuilder a
    forall a. ListBuilder a -> ListBuilder a -> ListBuilder a
    forall a.
    (a -> a -> a)
    -> (NonEmpty a -> a)
    -> (forall b. Integral b => b -> a -> a)
    -> Semigroup a
    forall a b. Integral b => b -> ListBuilder a -> ListBuilder a
    stimes :: b -> ListBuilder a -> ListBuilder a
    $cstimes :: forall a b. Integral b => b -> ListBuilder a -> ListBuilder a
    sconcat :: NonEmpty (ListBuilder a) -> ListBuilder a
    $csconcat :: forall a. NonEmpty (ListBuilder a) -> ListBuilder a
    <> :: ListBuilder a -> ListBuilder a -> ListBuilder a
    $c<> :: forall a. ListBuilder a -> ListBuilder a -> ListBuilder a
    Semigroup, Semigroup (ListBuilder a)
    ListBuilder a
    Semigroup (ListBuilder a) =>
    ListBuilder a
    -> (ListBuilder a -> ListBuilder a -> ListBuilder a)
    -> ([ListBuilder a] -> ListBuilder a)
    -> Monoid (ListBuilder a)
    [ListBuilder a] -> ListBuilder a
    ListBuilder a -> ListBuilder a -> ListBuilder a
    forall a. Semigroup (ListBuilder a)
    forall a. ListBuilder a
    forall a.
    Semigroup a =>
    a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
    forall a. [ListBuilder a] -> ListBuilder a
    forall a. ListBuilder a -> ListBuilder a -> ListBuilder a
    mconcat :: [ListBuilder a] -> ListBuilder a
    $cmconcat :: forall a. [ListBuilder a] -> ListBuilder a
    mappend :: ListBuilder a -> ListBuilder a -> ListBuilder a
    $cmappend :: forall a. ListBuilder a -> ListBuilder a -> ListBuilder a
    mempty :: ListBuilder a
    $cmempty :: forall a. ListBuilder a
    $cp1Monoid :: forall a. Semigroup (ListBuilder a)
    Monoid, a -> ListBuilder b -> ListBuilder a
    (a -> b) -> ListBuilder a -> ListBuilder b
    (forall a b. (a -> b) -> ListBuilder a -> ListBuilder b)
    -> (forall a b. a -> ListBuilder b -> ListBuilder a)
    -> Functor ListBuilder
    forall a b. a -> ListBuilder b -> ListBuilder a
    forall a b. (a -> b) -> ListBuilder a -> ListBuilder b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    <$ :: a -> ListBuilder b -> ListBuilder a
    $c<$ :: forall a b. a -> ListBuilder b -> ListBuilder a
    fmap :: (a -> b) -> ListBuilder a -> ListBuilder b
    $cfmap :: forall a b. (a -> b) -> ListBuilder a -> ListBuilder b
    Functor)

    data Tree a
        = Empty
        | Leaf a
        | Branch (Tree a) (Tree a)
          deriving (a -> Tree b -> Tree a
    (a -> b) -> Tree a -> Tree b
    (forall a b. (a -> b) -> Tree a -> Tree b)
    -> (forall a b. a -> Tree b -> Tree a) -> Functor Tree
    forall a b. a -> Tree b -> Tree a
    forall a b. (a -> b) -> Tree a -> Tree b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    <$ :: a -> Tree b -> Tree a
    $c<$ :: forall a b. a -> Tree b -> Tree a
    fmap :: (a -> b) -> Tree a -> Tree b
    $cfmap :: forall a b. (a -> b) -> Tree a -> Tree b
    Functor,Tree a -> Tree a -> Bool
    (Tree a -> Tree a -> Bool)
    -> (Tree a -> Tree a -> Bool) -> Eq (Tree a)
    forall a. Eq a => Tree a -> Tree a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    /= :: Tree a -> Tree a -> Bool
    $c/= :: forall a. Eq a => Tree a -> Tree a -> Bool
    == :: Tree a -> Tree a -> Bool
    $c== :: forall a. Eq a => Tree a -> Tree a -> Bool
    Eq,Eq (Tree a)
    Eq (Tree a) =>
    (Tree a -> Tree a -> Ordering)
    -> (Tree a -> Tree a -> Bool)
    -> (Tree a -> Tree a -> Bool)
    -> (Tree a -> Tree a -> Bool)
    -> (Tree a -> Tree a -> Bool)
    -> (Tree a -> Tree a -> Tree a)
    -> (Tree a -> Tree a -> Tree a)
    -> Ord (Tree a)
    Tree a -> Tree a -> Bool
    Tree a -> Tree a -> Ordering
    Tree a -> Tree a -> Tree a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (Tree a)
    forall a. Ord a => Tree a -> Tree a -> Bool
    forall a. Ord a => Tree a -> Tree a -> Ordering
    forall a. Ord a => Tree a -> Tree a -> Tree a
    min :: Tree a -> Tree a -> Tree a
    $cmin :: forall a. Ord a => Tree a -> Tree a -> Tree a
    max :: Tree a -> Tree a -> Tree a
    $cmax :: forall a. Ord a => Tree a -> Tree a -> Tree a
    >= :: Tree a -> Tree a -> Bool
    $c>= :: forall a. Ord a => Tree a -> Tree a -> Bool
    > :: Tree a -> Tree a -> Bool
    $c> :: forall a. Ord a => Tree a -> Tree a -> Bool
    <= :: Tree a -> Tree a -> Bool
    $c<= :: forall a. Ord a => Tree a -> Tree a -> Bool
    < :: Tree a -> Tree a -> Bool
    $c< :: forall a. Ord a => Tree a -> Tree a -> Bool
    compare :: Tree a -> Tree a -> Ordering
    $ccompare :: forall a. Ord a => Tree a -> Tree a -> Ordering
    $cp1Ord :: forall a. Ord a => Eq (Tree a)
    Ord,Int -> Tree a -> ShowS
    [Tree a] -> ShowS
    Tree a -> String
    (Int -> Tree a -> ShowS)
    -> (Tree a -> String) -> ([Tree a] -> ShowS) -> Show (Tree a)
    forall a. Show a => Int -> Tree a -> ShowS
    forall a. Show a => [Tree a] -> ShowS
    forall a. Show a => Tree a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    showList :: [Tree a] -> ShowS
    $cshowList :: forall a. Show a => [Tree a] -> ShowS
    show :: Tree a -> String
    $cshow :: forall a. Show a => Tree a -> String
    showsPrec :: Int -> Tree a -> ShowS
    $cshowsPrec :: forall a. Show a => Int -> Tree a -> ShowS
    Show)

    instance Semigroup (Tree a) where
        Empty <> :: Tree a -> Tree a -> Tree a
    <> x :: Tree a
    x = Tree a
    x
        x :: Tree a
    x <> Empty = Tree a
    x
        x :: Tree a
    x <> y :: Tree a
    y = Tree a -> Tree a -> Tree a
    forall a. Tree a -> Tree a -> Tree a
    Branch Tree a
    x Tree a
    y

    instance Monoid (Tree a) where
        mempty :: Tree a
    mempty = Tree a
    forall a. Tree a
    Empty
        mappend :: Tree a -> Tree a -> Tree a
    mappend = Tree a -> Tree a -> Tree a
    forall a. Semigroup a => a -> a -> a
    (<>)

    flattenTree :: Tree a -> [a]
    flattenTree :: Tree a -> [a]
    flattenTree x :: Tree a
    x = Tree a -> [a] -> [a]
    forall a. Tree a -> [a] -> [a]
    f Tree a
    x []
        where
            f :: Tree a -> [a] -> [a]
    f Empty acc :: [a]
    acc = [a]
    acc
            f (Leaf x :: a
    x) acc :: [a]
    acc = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    acc
            f (Branch x :: Tree a
    x y :: Tree a
    y) acc :: [a]
    acc = Tree a -> [a] -> [a]
    f Tree a
    x (Tree a -> [a] -> [a]
    f Tree a
    y [a]
    acc)

    unflattenTree :: Tree a -> [b] -> Tree b
    unflattenTree :: Tree a -> [b] -> Tree b
    unflattenTree t :: Tree a
    t xs :: [b]
    xs = (Tree b, [b]) -> Tree b
    forall a b. (a, b) -> a
    fst ((Tree b, [b]) -> Tree b) -> (Tree b, [b]) -> Tree b
    forall a b. (a -> b) -> a -> b
    $ Tree a -> [b] -> (Tree b, [b])
    forall a a. Tree a -> [a] -> (Tree a, [a])
    f Tree a
    t [b]
    xs
        where
            f :: Tree a -> [a] -> (Tree a, [a])
    f Empty xs :: [a]
    xs = (Tree a
    forall a. Tree a
    Empty, [a]
    xs)
            f Leaf{} (x :: a
    x:xs :: [a]
    xs) = (a -> Tree a
    forall a. a -> Tree a
    Leaf a
    x, [a]
    xs)
            f (Branch a :: Tree a
    a b :: Tree a
    b) xs :: [a]
    xs = (Tree a -> Tree a -> Tree a
    forall a. Tree a -> Tree a -> Tree a
    Branch Tree a
    a2 Tree a
    b2, [a]
    xs3)
                where (a2 :: Tree a
    a2, xs2 :: [a]
    xs2) = Tree a -> [a] -> (Tree a, [a])
    f Tree a
    a [a]
    xs
                      (b2 :: Tree a
    b2, xs3 :: [a]
    xs3) = Tree a -> [a] -> (Tree a, [a])
    f Tree a
    b [a]
    xs2

    newListBuilder :: a -> ListBuilder a
    newListBuilder :: a -> ListBuilder a
    newListBuilder = Tree a -> ListBuilder a
    forall a. Tree a -> ListBuilder a
    ListBuilder (Tree a -> ListBuilder a) -> (a -> Tree a) -> a -> ListBuilder a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Tree a
    forall a. a -> Tree a
    Leaf

    runListBuilder :: ListBuilder a -> [a]
    runListBuilder :: ListBuilder a -> [a]
    runListBuilder (ListBuilder x :: Tree a
    x) = Tree a -> [a]
    forall a. Tree a -> [a]
    flattenTree Tree a
    x