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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
\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}
|
