    --------------------------------------------------------------------
    -- |
    -- Module    : Text.XML.Light.Cursor
    -- Copyright : (c) Galois, Inc. 2008
    -- License   : BSD3
    --
    -- Maintainer: Iavor S. Diatchki <diatchki@galois.com>
    -- Stability : provisional
    -- Portability: portable
    --
    -- XML cursors for working XML content withing the context of
    -- an XML document.  This implementation is based on the general
    -- tree zipper written by Krasimir Angelov and Iavor S. Diatchki.
    --

    module Text.XML.Light.Cursor
      ( Tag(..), getTag, setTag, fromTag
      , Cursor(..), Path

      -- * Conversions
      , fromContent
      , fromElement
      , fromForest
      , toForest
      , toTree

      -- * Moving around
      , parent
      , root
      , getChild
      , firstChild
      , lastChild
      , left
      , right
      , nextDF

      -- ** Searching
      , findChild
      , findLeft
      , findRight
      , findRec

      -- * Node classification
      , isRoot
      , isFirst
      , isLast
      , isLeaf
      , isChild
      , hasChildren
      , getNodeIndex

      -- * Updates
      , setContent
      , modifyContent
      , modifyContentM

      -- ** Inserting content
      , insertLeft
      , insertRight
      , insertGoLeft
      , insertGoRight

      -- ** Removing content
      , removeLeft
      , removeRight
      , removeGoLeft
      , removeGoRight
      , removeGoUp

      ) where

    import Text.XML.Light.Types
    import Data.Maybe(isNothing)
    import Control.Monad(mplus)

    data Tag = Tag { Tag -> QName
    tagName    :: QName
                   , Tag -> [Attr]
    tagAttribs :: [Attr]
                   , Tag -> Maybe Line
    tagLine    :: Maybe Line
                   } deriving (Int -> Tag -> ShowS
    [Tag] -> ShowS
    Tag -> String
    (Int -> Tag -> ShowS)
    -> (Tag -> String) -> ([Tag] -> ShowS) -> Show Tag
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Tag -> ShowS
    showsPrec :: Int -> Tag -> ShowS
    $cshow :: Tag -> String
    show :: Tag -> String
    $cshowList :: [Tag] -> ShowS
    showList :: [Tag] -> ShowS
    Show)

    getTag :: Element -> Tag
    getTag :: Element -> Tag
    getTag Element
    e = Tag { tagName :: QName
    tagName = Element -> QName
    elName Element
    e
                   , tagAttribs :: [Attr]
    tagAttribs = Element -> [Attr]
    elAttribs Element
    e
                   , tagLine :: Maybe Line
    tagLine = Element -> Maybe Line
    elLine Element
    e
                   }

    setTag :: Tag -> Element -> Element
    setTag :: Tag -> Element -> Element
    setTag Tag
    t Element
    e = Tag -> [Content] -> Element
    fromTag Tag
    t (Element -> [Content]
    elContent Element
    e)

    fromTag :: Tag -> [Content] -> Element
    fromTag :: Tag -> [Content] -> Element
    fromTag Tag
    t [Content]
    cs = Element { elName :: QName
    elName    = Tag -> QName
    tagName Tag
    t
                           , elAttribs :: [Attr]
    elAttribs = Tag -> [Attr]
    tagAttribs Tag
    t
                           , elLine :: Maybe Line
    elLine    = Tag -> Maybe Line
    tagLine Tag
    t
                           , elContent :: [Content]
    elContent = [Content]
    cs
                           }

    type Path = [([Content],Tag,[Content])]

    -- | The position of a piece of content in an XML document.
    data Cursor = Cur
      { Cursor -> Content
    current :: Content      -- ^ The currently selected content.
      , Cursor -> [Content]
    lefts   :: [Content]    -- ^ Siblings on the left, closest first.
      , Cursor -> [Content]
    rights  :: [Content]    -- ^ Siblings on the right, closest first.
      , Cursor -> Path
    parents :: Path -- ^ The contexts of the parent elements of this location.
      } deriving (Int -> Cursor -> ShowS
    [Cursor] -> ShowS
    Cursor -> String
    (Int -> Cursor -> ShowS)
    -> (Cursor -> String) -> ([Cursor] -> ShowS) -> Show Cursor
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Cursor -> ShowS
    showsPrec :: Int -> Cursor -> ShowS
    $cshow :: Cursor -> String
    show :: Cursor -> String
    $cshowList :: [Cursor] -> ShowS
    showList :: [Cursor] -> ShowS
    Show)

    -- Moving around ---------------------------------------------------------------

    -- | The parent of the given location.
    parent :: Cursor -> Maybe Cursor
    parent :: Cursor -> Maybe Cursor
    parent Cursor
    loc =
      case Cursor -> Path
    parents Cursor
    loc of
        ([Content]
    pls,Tag
    v,[Content]
    prs) : Path
    ps -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just
          Cur { current :: Content
    current = Element -> Content
    Elem
                        (Tag -> [Content] -> Element
    fromTag Tag
    v
                        ([Content] -> Content -> [Content] -> [Content]
    forall a. [a] -> a -> [a] -> [a]
    combChildren (Cursor -> [Content]
    lefts Cursor
    loc) (Cursor -> Content
    current Cursor
    loc) (Cursor -> [Content]
    rights Cursor
    loc)))
              , lefts :: [Content]
    lefts = [Content]
    pls, rights :: [Content]
    rights = [Content]
    prs, parents :: Path
    parents = Path
    ps
              }
        [] -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | The top-most parent of the given location.
    root :: Cursor -> Cursor
    root :: Cursor -> Cursor
    root Cursor
    loc = Cursor -> (Cursor -> Cursor) -> Maybe Cursor -> Cursor
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Cursor
    loc Cursor -> Cursor
    root (Cursor -> Maybe Cursor
    parent Cursor
    loc)

    -- | The left sibling of the given location.
    left :: Cursor -> Maybe Cursor
    left :: Cursor -> Maybe Cursor
    left Cursor
    loc =
      case Cursor -> [Content]
    lefts Cursor
    loc of
        Content
    t : [Content]
    ts -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cursor
    loc { current = t, lefts = ts
                                        , rights = current loc : rights loc }
        []     -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | The right sibling of the given location.
    right :: Cursor -> Maybe Cursor
    right :: Cursor -> Maybe Cursor
    right Cursor
    loc =
      case Cursor -> [Content]
    rights Cursor
    loc of
        Content
    t : [Content]
    ts -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cursor
    loc { current = t, lefts = current loc : lefts loc
                                        , rights = ts }
        []     -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | The first child of the given location.
    firstChild :: Cursor -> Maybe Cursor
    firstChild :: Cursor -> Maybe Cursor
    firstChild Cursor
    loc =
      do (Content
    t : [Content]
    ts, Path
    ps) <- Cursor -> Maybe ([Content], Path)
    downParents Cursor
    loc
         Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cur { current :: Content
    current = Content
    t, lefts :: [Content]
    lefts = [], rights :: [Content]
    rights = [Content]
    ts , parents :: Path
    parents = Path
    ps }

    -- | The last child of the given location.
    lastChild :: Cursor -> Maybe Cursor
    lastChild :: Cursor -> Maybe Cursor
    lastChild Cursor
    loc =
      do ([Content]
    ts, Path
    ps) <- Cursor -> Maybe ([Content], Path)
    downParents Cursor
    loc
         case [Content] -> [Content]
    forall a. [a] -> [a]
    reverse [Content]
    ts of
           Content
    l : [Content]
    ls -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cur { current :: Content
    current = Content
    l, lefts :: [Content]
    lefts = [Content]
    ls, rights :: [Content]
    rights = []
                                                         , parents :: Path
    parents = Path
    ps }
           [] -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | Find the next left sibling that satisfies a predicate.
    findLeft :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findLeft :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findLeft Cursor -> Bool
    p Cursor
    loc = do Cursor
    loc1 <- Cursor -> Maybe Cursor
    left Cursor
    loc
                        if Cursor -> Bool
    p Cursor
    loc1 then Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cursor
    loc1 else (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findLeft Cursor -> Bool
    p Cursor
    loc1

    -- | Find the next right sibling that satisfies a predicate.
    findRight :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRight :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRight Cursor -> Bool
    p Cursor
    loc = do Cursor
    loc1 <- Cursor -> Maybe Cursor
    right Cursor
    loc
                         if Cursor -> Bool
    p Cursor
    loc1 then Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cursor
    loc1 else (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRight Cursor -> Bool
    p Cursor
    loc1

    -- | The first child that satisfies a predicate.
    findChild :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findChild :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findChild Cursor -> Bool
    p Cursor
    loc =
      do Cursor
    loc1 <- Cursor -> Maybe Cursor
    firstChild Cursor
    loc
         if Cursor -> Bool
    p Cursor
    loc1 then Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cursor
    loc1 else (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRight Cursor -> Bool
    p Cursor
    loc1

    -- | The next position in a left-to-right depth-first traversal of a document:
    -- either the first child, right sibling, or the right sibling of a parent that
    -- has one.
    nextDF :: Cursor -> Maybe Cursor
    nextDF :: Cursor -> Maybe Cursor
    nextDF Cursor
    c = Cursor -> Maybe Cursor
    firstChild Cursor
    c Maybe Cursor -> Maybe Cursor -> Maybe Cursor
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` Cursor -> Maybe Cursor
    up Cursor
    c
      where up :: Cursor -> Maybe Cursor
    up Cursor
    x = Cursor -> Maybe Cursor
    right Cursor
    x Maybe Cursor -> Maybe Cursor -> Maybe Cursor
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` (Cursor -> Maybe Cursor
    up (Cursor -> Maybe Cursor) -> Maybe Cursor -> Maybe Cursor
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Cursor -> Maybe Cursor
    parent Cursor
    x)

    -- | Perform a depth first search for a descendant that satisfies the
    -- given predicate.
    findRec :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRec :: (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRec Cursor -> Bool
    p Cursor
    c = if Cursor -> Bool
    p Cursor
    c then Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cursor
    c else (Cursor -> Bool) -> Cursor -> Maybe Cursor
    findRec Cursor -> Bool
    p (Cursor -> Maybe Cursor) -> Maybe Cursor -> Maybe Cursor
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Cursor -> Maybe Cursor
    nextDF Cursor
    c

    -- | The child with the given index (starting from 0).
    getChild :: Int -> Cursor -> Maybe Cursor
    getChild :: Int -> Cursor -> Maybe Cursor
    getChild Int
    n Cursor
    loc =
      do ([Content]
    ts,Path
    ps) <- Cursor -> Maybe ([Content], Path)
    downParents Cursor
    loc
         ([Content]
    ls,Content
    t,[Content]
    rs) <- [Content] -> Int -> Maybe ([Content], Content, [Content])
    forall a. [a] -> Int -> Maybe ([a], a, [a])
    splitChildren [Content]
    ts Int
    n
         Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Cur { current :: Content
    current = Content
    t, lefts :: [Content]
    lefts = [Content]
    ls, rights :: [Content]
    rights = [Content]
    rs, parents :: Path
    parents = Path
    ps }

    -- | private: computes the parent for "down" operations.
    downParents :: Cursor -> Maybe ([Content], Path)
    downParents :: Cursor -> Maybe ([Content], Path)
    downParents Cursor
    loc =
      case Cursor -> Content
    current Cursor
    loc of
        Elem Element
    e -> ([Content], Path) -> Maybe ([Content], Path)
    forall a. a -> Maybe a
    Just ( Element -> [Content]
    elContent Element
    e
                       , (Cursor -> [Content]
    lefts Cursor
    loc, Element -> Tag
    getTag Element
    e, Cursor -> [Content]
    rights Cursor
    loc) ([Content], Tag, [Content]) -> Path -> Path
    forall a. a -> [a] -> [a]
    : Cursor -> Path
    parents Cursor
    loc
                       )
        Content
    _      -> Maybe ([Content], Path)
    forall a. Maybe a
    Nothing

    -- Conversions -----------------------------------------------------------------

    -- | A cursor for the given content.
    fromContent :: Content -> Cursor
    fromContent :: Content -> Cursor
    fromContent Content
    t = Cur { current :: Content
    current = Content
    t, lefts :: [Content]
    lefts = [], rights :: [Content]
    rights = [], parents :: Path
    parents = [] }

    -- | A cursor for the given element.
    fromElement :: Element -> Cursor
    fromElement :: Element -> Cursor
    fromElement Element
    e = Content -> Cursor
    fromContent (Element -> Content
    Elem Element
    e)

    -- | The location of the first tree in a forest.
    fromForest :: [Content] -> Maybe Cursor
    fromForest :: [Content] -> Maybe Cursor
    fromForest (Content
    t:[Content]
    ts) = Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cur { current :: Content
    current = Content
    t, lefts :: [Content]
    lefts = [], rights :: [Content]
    rights = [Content]
    ts
                                                          , parents :: Path
    parents = [] }
    fromForest []     = Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | Computes the tree containing this location.
    toTree :: Cursor -> Content
    toTree :: Cursor -> Content
    toTree Cursor
    loc = Cursor -> Content
    current (Cursor -> Cursor
    root Cursor
    loc)

    -- | Computes the forest containing this location.
    toForest :: Cursor -> [Content]
    toForest :: Cursor -> [Content]
    toForest Cursor
    loc = let r :: Cursor
    r = Cursor -> Cursor
    root Cursor
    loc in [Content] -> Content -> [Content] -> [Content]
    forall a. [a] -> a -> [a] -> [a]
    combChildren (Cursor -> [Content]
    lefts Cursor
    r) (Cursor -> Content
    current Cursor
    r) (Cursor -> [Content]
    rights Cursor
    r)

    -- Queries ---------------------------------------------------------------------

    -- | Are we at the top of the document?
    isRoot :: Cursor -> Bool
    isRoot :: Cursor -> Bool
    isRoot Cursor
    loc = Path -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null (Cursor -> Path
    parents Cursor
    loc)

    -- | Are we at the left end of the the document?
    isFirst :: Cursor -> Bool
    isFirst :: Cursor -> Bool
    isFirst Cursor
    loc = [Content] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null (Cursor -> [Content]
    lefts Cursor
    loc)

    -- | Are we at the right end of the document?
    isLast :: Cursor -> Bool
    isLast :: Cursor -> Bool
    isLast Cursor
    loc = [Content] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null (Cursor -> [Content]
    rights Cursor
    loc)

    -- | Are we at the bottom of the document?
    isLeaf :: Cursor -> Bool
    isLeaf :: Cursor -> Bool
    isLeaf Cursor
    loc = Maybe ([Content], Path) -> Bool
    forall a. Maybe a -> Bool
    isNothing (Cursor -> Maybe ([Content], Path)
    downParents Cursor
    loc)

    -- | Do we have a parent?
    isChild :: Cursor -> Bool
    isChild :: Cursor -> Bool
    isChild Cursor
    loc = Bool -> Bool
    not (Cursor -> Bool
    isRoot Cursor
    loc)

    -- | Get the node index inside the sequence of children
    getNodeIndex :: Cursor -> Int
    getNodeIndex :: Cursor -> Int
    getNodeIndex Cursor
    loc = [Content] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length (Cursor -> [Content]
    lefts Cursor
    loc)

    -- | Do we have children?
    hasChildren :: Cursor -> Bool
    hasChildren :: Cursor -> Bool
    hasChildren Cursor
    loc = Bool -> Bool
    not (Cursor -> Bool
    isLeaf Cursor
    loc)

    -- Updates ---------------------------------------------------------------------

    -- | Change the current content.
    setContent :: Content -> Cursor -> Cursor
    setContent :: Content -> Cursor -> Cursor
    setContent Content
    t Cursor
    loc = Cursor
    loc { current = t }

    -- | Modify the current content.
    modifyContent :: (Content -> Content) -> Cursor -> Cursor
    modifyContent :: (Content -> Content) -> Cursor -> Cursor
    modifyContent Content -> Content
    f Cursor
    loc = Content -> Cursor -> Cursor
    setContent (Content -> Content
    f (Cursor -> Content
    current Cursor
    loc)) Cursor
    loc

    -- | Modify the current content, allowing for an effect.
    modifyContentM :: Monad m => (Content -> m Content) -> Cursor -> m Cursor
    modifyContentM :: forall (m :: * -> *).
    Monad m =>
    (Content -> m Content) -> Cursor -> m Cursor
    modifyContentM Content -> m Content
    f Cursor
    loc = do Content
    x <- Content -> m Content
    f (Cursor -> Content
    current Cursor
    loc)
                              Cursor -> m Cursor
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Content -> Cursor -> Cursor
    setContent Content
    x Cursor
    loc)

    -- | Insert content to the left of the current position.
    insertLeft :: Content -> Cursor -> Cursor
    insertLeft :: Content -> Cursor -> Cursor
    insertLeft Content
    t Cursor
    loc = Cursor
    loc { lefts = t : lefts loc }

    -- | Insert content to the right of the current position.
    insertRight :: Content -> Cursor -> Cursor
    insertRight :: Content -> Cursor -> Cursor
    insertRight Content
    t Cursor
    loc = Cursor
    loc { rights = t : rights loc }

    -- | Remove the content on the left of the current position, if any.
    removeLeft :: Cursor -> Maybe (Content,Cursor)
    removeLeft :: Cursor -> Maybe (Content, Cursor)
    removeLeft Cursor
    loc = case Cursor -> [Content]
    lefts Cursor
    loc of
                       Content
    l : [Content]
    ls -> (Content, Cursor) -> Maybe (Content, Cursor)
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Content
    l,Cursor
    loc { lefts = ls })
                       [] -> Maybe (Content, Cursor)
    forall a. Maybe a
    Nothing

    -- | Remove the content on the right of the current position, if any.
    removeRight :: Cursor -> Maybe (Content,Cursor)
    removeRight :: Cursor -> Maybe (Content, Cursor)
    removeRight Cursor
    loc = case Cursor -> [Content]
    rights Cursor
    loc of
                        Content
    l : [Content]
    ls -> (Content, Cursor) -> Maybe (Content, Cursor)
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Content
    l,Cursor
    loc { rights = ls })
                        [] -> Maybe (Content, Cursor)
    forall a. Maybe a
    Nothing

    -- | Insert content to the left of the current position.
    -- The new content becomes the current position.
    insertGoLeft :: Content -> Cursor -> Cursor
    insertGoLeft :: Content -> Cursor -> Cursor
    insertGoLeft Content
    t Cursor
    loc = Cursor
    loc { current = t, rights = current loc : rights loc }

    -- | Insert content to the right of the current position.
    -- The new content becomes the current position.
    insertGoRight :: Content -> Cursor -> Cursor
    insertGoRight :: Content -> Cursor -> Cursor
    insertGoRight Content
    t Cursor
    loc = Cursor
    loc { current = t, lefts = current loc : lefts loc }

    -- | Remove the current element.
    -- The new position is the one on the left.
    removeGoLeft :: Cursor -> Maybe Cursor
    removeGoLeft :: Cursor -> Maybe Cursor
    removeGoLeft Cursor
    loc = case Cursor -> [Content]
    lefts Cursor
    loc of
                         Content
    l : [Content]
    ls -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cursor
    loc { current = l, lefts = ls }
                         []     -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | Remove the current element.
    -- The new position is the one on the right.
    removeGoRight :: Cursor -> Maybe Cursor
    removeGoRight :: Cursor -> Maybe Cursor
    removeGoRight Cursor
    loc = case Cursor -> [Content]
    rights Cursor
    loc of
                         Content
    l : [Content]
    ls -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just Cursor
    loc { current = l, rights = ls }
                         []     -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | Remove the current element.
    -- The new position is the parent of the old position.
    removeGoUp :: Cursor -> Maybe Cursor
    removeGoUp :: Cursor -> Maybe Cursor
    removeGoUp Cursor
    loc =
      case Cursor -> Path
    parents Cursor
    loc of
        ([Content]
    pls,Tag
    v,[Content]
    prs) : Path
    ps -> Cursor -> Maybe Cursor
    forall a. a -> Maybe a
    Just
          Cur { current :: Content
    current = Element -> Content
    Elem (Tag -> [Content] -> Element
    fromTag Tag
    v ([Content] -> [Content]
    forall a. [a] -> [a]
    reverse (Cursor -> [Content]
    lefts Cursor
    loc) [Content] -> [Content] -> [Content]
    forall a. [a] -> [a] -> [a]
    ++ Cursor -> [Content]
    rights Cursor
    loc))
              , lefts :: [Content]
    lefts = [Content]
    pls, rights :: [Content]
    rights = [Content]
    prs, parents :: Path
    parents = Path
    ps
              }
        [] -> Maybe Cursor
    forall a. Maybe a
    Nothing

    -- | private: Gets the given element of a list.
    -- Also returns the preceding elements (reversed) and the following elements.
    splitChildren :: [a] -> Int -> Maybe ([a],a,[a])
    splitChildren :: forall a. [a] -> Int -> Maybe ([a], a, [a])
    splitChildren [a]
    _ Int
    n | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0 = Maybe ([a], a, [a])
    forall a. Maybe a
    Nothing
    splitChildren [a]
    cs Int
    pos = [a] -> [a] -> Int -> Maybe ([a], a, [a])
    forall {a} {a}.
    (Eq a, Num a) =>
    [a] -> [a] -> a -> Maybe ([a], a, [a])
    loop [] [a]
    cs Int
    pos
      where loop :: [a] -> [a] -> a -> Maybe ([a], a, [a])
    loop [a]
    acc (a
    x:[a]
    xs) a
    0 = ([a], a, [a]) -> Maybe ([a], a, [a])
    forall a. a -> Maybe a
    Just ([a]
    acc,a
    x,[a]
    xs)
            loop [a]
    acc (a
    x:[a]
    xs) a
    n = [a] -> [a] -> a -> Maybe ([a], a, [a])
    loop (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    acc) [a]
    xs (a -> Maybe ([a], a, [a])) -> a -> Maybe ([a], a, [a])
    forall a b. (a -> b) -> a -> b
    $! a
    na -> a -> a
    forall a. Num a => a -> a -> a
    -a
    1
            loop [a]
    _ [a]
    _ a
    _        = Maybe ([a], a, [a])
    forall a. Maybe a
    Nothing

    -- | private: combChildren ls x ys = reverse ls ++ [x] ++ ys
    combChildren :: [a] -> a -> [a] -> [a]
    combChildren :: forall a. [a] -> a -> [a] -> [a]
    combChildren [a]
    ls a
    t [a]
    rs = ([a] -> a -> [a]) -> [a] -> [a] -> [a]
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl ((a -> [a] -> [a]) -> [a] -> a -> [a]
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (:)) (a
    ta -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    rs) [a]
    ls