1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
\begin{comment}
\begin{code}
module Control.Edit.Container
( Container(..), Shape, Content
, ContainerEdit(..)
, 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.
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}
\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}
\end{defn}
\begin{defn}[container-edits]
TODO
\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}
|
