\begin{comment}
\begin{code}
module Control.Edit.Container
  ( Container(..), Shape, Content
  , FoldableContainer(..)
  , ContainerEdit(..), ContainerEdits
  , module Control.Edit
  ) where

import Control.Edit
import Data.Set (Set)
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq

import Control.Monad

import Control.Lens
\end{code}
\end{comment}

\citeauthor{hofmann2012edit} stellen \emph{container} vor—eine systematische Sicht auf Datenstrukturen, die es erlaubt eine generische edit-language zu definieren, im folgenden wiederholen wir die dortigen Definitionen.

Intuitiv zerlegt die Darstellung als container eine polymorphe Datenstruktur in ihre \emph{Form} (\emph{shape}), ordnet der Form eine Menge von \emph{Positionen} zu und belegt jede Position mit einem Wert:

\begin{defn}[Container-Typen]
Ein container-type ist ein Tupel $(I, P, \text{positions})$ aus einem Modul von \emph{shapes} mit partiell geordnetem Träger $\Dom I$, einer Menge von \emph{Positionen} $P$, und einer Abbildung\footnote{In \cite{hofmann2012edit} genannt $\text{live}$} $\text{positions} \colon \Dom I \to \powerset(P)$, die jeder Form eine Menge von Positionen zuordnet, die in einem container jener Form belegt sind.

Wir forden zudem, dass $\text{positions}$ monoton sein soll bzgl. der partiellen Ordnung auf $\Dom I$ und $\subseteq$ auf $\powerset P$\footnote{$\text{positions}$ ist ein Funktor von der Kategorie gegeben durch die Partielle Ordnung auf $\Dom I$ in die Kategorie von Teilmengen von $\powerset(P)$ mit Injektionen als Morphismen}.
\end{defn}

\begin{defn}[Container]
Ein container vom Typ $(I, P, \text{positions})$ mit Werten in $X$ ist ein Tupel $(i, c)$ aus einer Form $i \in \Dom I$ und einer Funktion $c \colon \text{positions}(i) \to X$, die jeder in $i$ vorkommenden Position einen Wert aus $X$ zuweist.

In Haskell sagen wir ein Typ \texttt{c} sei ein container gdw. wir einen Isomorphismus\footnote{Wir verwenden den Typ für Isomorphismen aus \cite[\texttt{Control.Lens.Iso}]{lens}, dessen genau Definition unerheblich ist für diese Arbeit} angeben können zwischen \texttt{c} und Tupeln $(i, c)$ für einen container-typ $(I, P, \text{positions})$.

Hierfür unterdrücken wir den inheränten Polymorphismus von containern zunächst und ordnen stattdessen jedem monomorph instanziierten container-typ \texttt{c} einen Typ \texttt{Content c} zu.
Polymorphe container können so mit universell quantifizierten Instanzen beschrieben werden.

Wir beschränken uns zudem auf monomorphe container deren Werte-Typ der Träger eines Moduls ist, da dies, als unglückliche Folge unserer charakterisierung von Moduln durch den Typ ihrer edits, für die spätere Definition von container-edits notwendig ist.

\begin{code}
class ( Module (ModShape c)
      , Module (ModContent c)
      , Ord (Position c) -- ^ Neccessary to form 'Set's of 'Position's
      ) => Container c where
  -- | Since we characterise 'Module's by the type of their edits we have to associate that type with @c@.
  --   We later introduce a type synonym for @Domain (ModShape c)@ later.
  type ModShape c :: *

  type Position c :: *

  type ModContent c :: *
  -- ^ Analogous to 'ModShape'

  -- | Compute the live positions of a shape
  positions :: Shape c -> Set (Position c)

  -- | Convert between the natural representation @c@ and a view as container, that is a 'Shape c' and a value function
  deconstructed :: Iso' c (Shape c, Position c -> Content c) 

constructed :: Container c => Iso' (Shape c, Position c -> Content c) c
-- ^ Inverse of 'deconstructed', for convenience
constructed = from deconstructed

type Shape c = Domain (ModShape c)
type Content c = Domain (ModContent c)
\end{code}
\end{defn}

TODO
\begin{code}
class Container c => FoldableContainer c where
  containerContent :: Fold c (Content c)
\end{code}

\begin{defn}[Klassifikation von edits auf shapes]
Für einen container-typ $(I, P, \text{postitions})$ klassifizieren wir die edits $\partial i \in \partial I$ wie folgt:

\begin{description}
  \item[insertions] $\forall i \in \Dom (\partial i) \colon i \cdot \partial i \geq i$
  \item[deletions] $\forall i \in \Dom (\partial i) \colon i \cdot \partial i \leq i$
  \item[rearrangements] $\forall i \in \Dom (\partial i) \colon \size{\text{positions}(i \cdot \partial i)} = \size{\text{positions}(i)}$
\end{description}

Für ein rearrangement $\partial i$ nennen wir eine Funktion $f \colon I \to P \to P$ \emph{kompatibel} mit $\partial i$ gdw:

$$\forall i \in \Dom(\partial i) \colon f(i) \upharpoonright \text{positions}(i) \leftrightarrow \text{positions}(i \cdot \partial i)$$

D.h. $f(i)$ ist, eingeschränkt auf die Positionen, die in $i$ belegt sind, eine Bijektion auf die in $i \cdot \partial i$ belegten Positionen.
\end{defn}

\begin{defn}[container-edits]
  Für eine Instanz eines container-typs $(I, P, \text{positions})$ dessen Inhalt Elemente eines Moduls $X$ sind können wir aus den edits auf die shapes $\partial I$ des containers und denen auf seinen Inhalt $\partial X$ edits für den container konstruieren:

\[
\begin{array}{lll}
  & \{ \text{fail} \} & \\
  \cup & \{ \text{mod}(p, \partial x) & \mid p \in P, \partial x \in \partial X \} \\
  \cup & \{ \text{ins}(\partial i) & \mid \text{$\partial i$ ist insertion} \} \\
  \cup & \{ \text{del}(\partial i) & \mid \text{$\partial i$ ist deletion} \} \\
  \cup & \{ \text{rearr}(\partial i, f) & \mid \text{$\partial i$ ist rearrangement und kompatibel mit $f$} \} \\
\end{array}
\]

In Haskell verzichten wir auf die Klassifikation von shape-edits und fassen daher $\text{ins}$, $\text{del}$, und $\text{rearr}$ zusammen.

\begin{code}
data ContainerEdit c where
  Fail       :: ContainerEdit c
  ModContent :: Position c -> ModContent c -> ContainerEdit c
  ModShape   :: ModShape c -> (Shape c -> Position c -> Position c) -> ContainerEdit c

type ContainerEdits c = Seq (ContainerEdit c)
\end{code}
\end{defn}

\begin{defn}[Wirkung von container-edits]
  TODO
\begin{code}
instance Container c => Module (ContainerEdits c) where
  type Domain (ContainerEdits c) = c
  apply fs = over mapped (view constructed) . flip (foldM apply') fs . view deconstructed
    where
      apply' :: Container c
             => (Shape c, Position c -> Content c)
             -> ContainerEdit c
             -> Maybe (Shape c, Position c -> Content c)
      apply' _       Fail = Nothing
      apply' (s, cf) (ModContent p dc) = do
        c' <- dc `apply` cf p
        let cf' x
              | x == p    = c'
              | otherwise = cf x
        return (s, cf')
      apply' (s, cf) (ModShape ds dcf) = (, cf . dcf s) <$> ds `apply` s
  initial = view constructed (initial @(ModShape c), \_ -> initial @(ModContent c))
  divInit x =
    let
      x'@(s, cf) = x ^. deconstructed
      (ds, dcf) = over _1 divInit $ over (_2.mapped) divInit x'
    in
      foldMap (\p -> Seq.singleton . ModContent p $ dcf p) (positions @c s) |> (ModShape ds $ const id)
\end{code}
\end{defn}