summaryrefslogtreecommitdiff
path: root/edit-lens
diff options
context:
space:
mode:
Diffstat (limited to 'edit-lens')
-rw-r--r--edit-lens/src/Control/DFST.lhs4
-rw-r--r--edit-lens/src/Control/DFST/Lens.lhs25
-rw-r--r--edit-lens/src/Control/Edit.lhs8
-rw-r--r--edit-lens/src/Control/Edit/String.lhs4
-rw-r--r--edit-lens/src/Control/Edit/String/Affected.lhs2
-rw-r--r--edit-lens/src/Control/FST.lhs33
-rw-r--r--edit-lens/src/Control/FST/Lens.tex4
-rw-r--r--edit-lens/src/Control/Lens/Edit.lhs12
8 files changed, 46 insertions, 46 deletions
diff --git a/edit-lens/src/Control/DFST.lhs b/edit-lens/src/Control/DFST.lhs
index eb838ae..48feaf9 100644
--- a/edit-lens/src/Control/DFST.lhs
+++ b/edit-lens/src/Control/DFST.lhs
@@ -41,7 +41,7 @@ import Text.Dot
41\begin{defn}[deterministic finite state transducer] 41\begin{defn}[deterministic finite state transducer]
42 Wir nennen einen FST \emph{deterministic}, wenn jedes Paar aus Ausgabezustand und Eingabesymbol maximal eine Transition zulässt, $\epsilon$-Transitionen keine Schleifen bilden und die Menge von initialen Zuständen einelementig ist. 42 Wir nennen einen FST \emph{deterministic}, wenn jedes Paar aus Ausgabezustand und Eingabesymbol maximal eine Transition zulässt, $\epsilon$-Transitionen keine Schleifen bilden und die Menge von initialen Zuständen einelementig ist.
43 43
44 Zusätzlich ändern wir die Darstellung indem wir $\epsilon$-Transitionen kontrahieren. 44 Zusätzlich ändern wir die Darstellung, indem wir $\epsilon$-Transitionen kontrahieren.
45 Wir erweitern hierfür die Ausgabe pro Transition von einem einzelnen Zeichen zu einem Wort beliebiger Länge und fügen, bei jeder Kontraktion einer $\epsilon$-Transition $A \rightarrow B$, die Ausgabe der Transition vorne an die Ausgabe aller Transitionen $B \rightarrow \ast$ von $B$ an. 45 Wir erweitern hierfür die Ausgabe pro Transition von einem einzelnen Zeichen zu einem Wort beliebiger Länge und fügen, bei jeder Kontraktion einer $\epsilon$-Transition $A \rightarrow B$, die Ausgabe der Transition vorne an die Ausgabe aller Transitionen $B \rightarrow \ast$ von $B$ an.
46\end{defn} 46\end{defn}
47 47
@@ -92,7 +92,7 @@ toFST DFST{..} = flip execState initialFST $ forM_ (Map.toList stTransition) han
92\end{comment} 92\end{comment}
93 93
94Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST. 94Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST.
95Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs um den Determinismus bereits im Typsystem zu kodieren. 95Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs, um den Determinismus bereits im Typsystem zu kodieren.
96 96
97\begin{code} 97\begin{code}
98runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output) 98runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output)
diff --git a/edit-lens/src/Control/DFST/Lens.lhs b/edit-lens/src/Control/DFST/Lens.lhs
index 56f37a0..04dade5 100644
--- a/edit-lens/src/Control/DFST/Lens.lhs
+++ b/edit-lens/src/Control/DFST/Lens.lhs
@@ -68,7 +68,7 @@ import Data.Universe (Finite(..))
68\begin{defn}[Ausgabe-Wirkung von DFSTs] 68\begin{defn}[Ausgabe-Wirkung von DFSTs]
69Wir definieren zunächst die \emph{Ausgabe-Wirkung}\footnote{Wir schreiben im Folgenden auch nur \emph{Wirkung}} eines DFST auf einen festen String als eine Abbildung \texttt{state -> (Seq output, Maybe state)}, die den aktuellen Zustand vor dem Parsen des Strings auf den Zustand danach und die (womöglich leere) Ausgabe schickt. 69Wir definieren zunächst die \emph{Ausgabe-Wirkung}\footnote{Wir schreiben im Folgenden auch nur \emph{Wirkung}} eines DFST auf einen festen String als eine Abbildung \texttt{state -> (Seq output, Maybe state)}, die den aktuellen Zustand vor dem Parsen des Strings auf den Zustand danach und die (womöglich leere) Ausgabe schickt.
70Wir annotieren Wirkungen zudem mit dem konsumierten String. 70Wir annotieren Wirkungen zudem mit dem konsumierten String.
71Diese Wirkungen bilden einen Monoiden analog zu Endomorphismen, wobei die Resultat-Strings concateniert werden. 71Diese Wirkungen bilden einen Monoiden analog zu Endomorphismen, wobei die Resultat-Strings konkateniert werden.
72 72
73\begin{code} 73\begin{code}
74data DFSTAction state input output = DFSTAction 74data DFSTAction state input output = DFSTAction
@@ -132,13 +132,13 @@ Wir bedienen uns hierbei einer bestehenden Programmbibliothek \cite{composition-
132 \begin{figure}[H] 132 \begin{figure}[H]
133 \centering 133 \centering
134 \pinclude{presentation/switchdfst.tex} 134 \pinclude{presentation/switchdfst.tex}
135 \caption{\label{fig:switchdfst} Ein einfacher DFST, der zwischen zwei Zustanden wechselt und Ausgabe abhängig vom aktuellen Zustand erzeugt} 135 \caption{\label{fig:switchdfst} Ein einfacher DFST, der zwischen zwei Zuständen wechselt und Ausgabe abhängig vom aktuellen Zustand erzeugt}
136 \end{figure} 136 \end{figure}
137 137
138 Auf $s$ wechselt der DFST seinen Zustand, auf $p$ produziert er, abhängig vom aktuellen Zustand, genau ein Zeichen. 138 Auf $s$ wechselt der DFST seinen Zustand, auf $p$ produziert er, abhängig vom aktuellen Zustand, genau ein Zeichen.
139 139
140 Wir stellen die Wirkung des DFST auf den Eingabe-String $spp$ grafisch analog zur Baumstruktur von \texttt{Compositions} dar. 140 Wir stellen die Wirkung des DFST auf den Eingabe-String $spp$ grafisch analog zur Baumstruktur von \texttt{Compositions} dar.
141 Wir bedienen uns hier der Darstellung von Automaten-Wirkungen als \emph{Schaltboxen} aus \cite{hofmann2011automatentheorie}, angepasst für DFSTs indem wir die Ausgabe des transducers an den Pfaden innerhalb der Schaltbox annotieren. 141 Wir bedienen uns hier der Darstellung von Automaten-Wirkungen als \emph{Schaltboxen} aus \cite{hofmann2011automatentheorie}, angepasst für DFSTs, indem wir die Ausgabe des transducers an den Pfaden innerhalb der Schaltbox annotieren.
142 142
143 \begin{figure}[H] 143 \begin{figure}[H]
144 \centering 144 \centering
@@ -160,22 +160,23 @@ dfstaProduces = fmap fst . runDFSTAction'
160\end{code} 160\end{code}
161\end{comment} 161\end{comment}
162 162
163Für $\Rrightarrow$ können wir die alte DFST-Wirkung zunächst anhand des Intervalls in dem der input-String von allen gegebenen edits betroffen ist (\texttt{affected}) in einen unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen. 163Für $\Rrightarrow$ können wir die alte DFST-Wirkung zunächst, anhand des Intervalls, in dem der input-String von allen gegebenen edits betroffen ist (\texttt{affected}), in einen unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen.
164 164
165Da wir wissen welche Stelle im input-String vom ersten gegebenen edit betroffen ist können wir, anhand der Wirkung des Teilstücks bis zu jener Stelle, den betroffenen Suffix wiederum teilen. 165Da wir wissen welche Stelle im input-String vom ersten gegebenen edit betroffen ist, können wir, anhand der Wirkung des Teilstücks bis zu jener Stelle, den betroffenen Suffix wiederum teilen.
166Die Wirkung ab der betroffenen Stelle im input-String können wir als Komposition der Wirkung der durch den edit betroffenen Stelle und derer aller Zeichen danach bestimmen. 166Die Wirkung ab der betroffenen Stelle im input-String können wir als Komposition der Wirkung der durch den edit betroffenen Stelle und derer aller Zeichen danach bestimmen.
167Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes im output-String und des aus der gerade berechneten Wirkung zu bestimmen, wir bedienen uns hierzu dem Unix Standard-Diff-Algorithmus zwischen der ursprünglichen Ausgabe und dem Ergebnis der Iteration des Verfahrens auf alle gegebenen edits. 167Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes im output-String und des aus der gerade berechneten Wirkung zu bestimmen.
168Wir bedienen uns hierzu dem Unix Standard-Diff-Algorithmus zwischen der ursprünglichen Ausgabe und dem Ergebnis der Iteration des Verfahrens auf alle gegebenen edits.
168 169
169Für die asymmetrische edit-lens entgegen der DFST-Richtung $\Lleftarrow$ verwenden wir Breitensuche über die Zustände des DFST innerhalb des von allen gegeben edits betroffenen Intervalls: 170Für die asymmetrische edit-lens entgegen der DFST-Richtung $\Lleftarrow$ verwenden wir Breitensuche über die Zustände des DFST innerhalb des von allen gegeben edits betroffenen Intervalls:
170 171
171Wir unterteilen zunächst das Komplement an den Grenzen des betroffenen Intervalls im output-String in drei Teile (durch Akkumulation der Elemente des Komplements bis die gewünschte Länge erreicht ist). 172Wir unterteilen zunächst das Komplement an den Grenzen des betroffenen Intervalls im output-String in drei Teile durch Akkumulation der Elemente des Komplements bis die gewünschte Länge erreicht ist.
172 173
173Wir transformieren dann den DFST in einen FST, dessen Ausgabe wir mit \texttt{restrictOutput} auf das gewünschte Fragment einschränken, setzen als initialen Zustand des FST den Zustand am linken Rand des von den edits betroffenen Intervalls und akzeptieren jene Zustände, von denen aus das Komplement-Fragment ab dem rechten Rand des betroffenen Intervalls zu einem im ursprünglichen DFST akzeptierenden Zustand führt. 174Wir transformieren dann den DFST in einen FST, dessen Ausgabe wir mit \texttt{restrictOutput} auf das gewünschte Fragment einschränken, setzen als initialen Zustand des FST den Zustand am linken Rand des von den edits betroffenen Intervalls und akzeptieren jene Zustände, von denen aus das Komplement-Fragment ab dem rechten Rand des betroffenen Intervalls zu einem im ursprünglichen DFST akzeptierenden Zustand führt.
174 175
175Wir verwenden dann gewöhnliche Breitensuche über die Zustände und Transitionen des soeben konstruierten FSTs um einen Lauffragment zu bestimmen, dass wir in das betroffene Intervall einsetzen können. 176Wir verwenden dann gewöhnliche Breitensuche über die Zustände und Transitionen des soeben konstruierten FSTs, um einen Lauffragment zu bestimmen, das wir in das betroffene Intervall einsetzen können.
176Hierbei sind sämtliche Randbedingungen (korrekte Ausgabe, Übereinstimmung an den Intervallgrenzen) bereits in den FST kodiert sodass wir nur noch prüfen müssen, dass der gefunde Lauf in einem akzeptierenden Zustand endet. 177Hierbei sind sämtliche Randbedingungen (korrekte Ausgabe, Übereinstimmung an den Intervallgrenzen) bereits in den FST kodiert, sodass wir nur noch prüfen müssen, dass der gefundene Lauf in einem akzeptierenden Zustand endet.
177 178
178Die input-edits können nun wiederum, unter Beachtung der Verschiebung der Indices um die Länge der Eingabe vor der linken Intervallgrenze, mit dem Unix Standard-Diff-Algorithmus berechnet werden. 179Die input-edits können nun wiederum, unter Beachtung der Verschiebung der Indizes um die Länge der Eingabe vor der linken Intervallgrenze, mit dem Unix Standard-Diff-Algorithmus berechnet werden.
179 180
180\begin{comment} 181\begin{comment}
181\begin{code} 182\begin{code}
@@ -323,7 +324,7 @@ bfs outgoing predicate
323 Wie auch im ursprünglichen DFST sind alle Zustände akzeptierend. 324 Wie auch im ursprünglichen DFST sind alle Zustände akzeptierend.
324 325
325 Wir müssen nun bestimmen welche Zustände, unter $\text{act}_\text{R}$, zu einem akzeptierenden Zustand führen. 326 Wir müssen nun bestimmen welche Zustände, unter $\text{act}_\text{R}$, zu einem akzeptierenden Zustand führen.
326 Da alle Zustände akzeptieren ist hier jeder Zustand geeignet. 327 Da alle Zustände akzeptieren, ist hier jeder Zustand geeignet.
327 328
328 Wir müssen nun (vermöge Breitensuche) den kürzesten Pfad im Produkt-FST zwischen $Q_\text{L}$ und einem der Zustände finden, der unter $\text{act}_\text{R}$ zu einem akzeptierenden Zustand im ursprünglichen transducer führt. 329 Wir müssen nun (vermöge Breitensuche) den kürzesten Pfad im Produkt-FST zwischen $Q_\text{L}$ und einem der Zustände finden, der unter $\text{act}_\text{R}$ zu einem akzeptierenden Zustand im ursprünglichen transducer führt.
329 Der leere Pfad ist geeignet. 330 Der leere Pfad ist geeignet.
@@ -339,7 +340,7 @@ bfs outgoing predicate
339 \text{\tt \textbackslash n} \cdot e = \epsilon 340 \text{\tt \textbackslash n} \cdot e = \epsilon
340 \end{equation*} 341 \end{equation*}
341 Man beachte das $\text{\tt \textbackslash n}$ und $\epsilon$ hierbei die \emph{Eingaben} von $\text{act}_{e^\prime}$ bzw. $\text{act}_0$ sind. 342 Man beachte das $\text{\tt \textbackslash n}$ und $\epsilon$ hierbei die \emph{Eingaben} von $\text{act}_{e^\prime}$ bzw. $\text{act}_0$ sind.
342 Nach Behandlung der Indices ergibt sich $e = \rho_{80}$. 343 Nach Behandlung der Indizes ergibt sich $e = \rho_{80}$.
343 344
344 Als neues Komplement erhalten wir: 345 Als neues Komplement erhalten wir:
345 346
diff --git a/edit-lens/src/Control/Edit.lhs b/edit-lens/src/Control/Edit.lhs
index 80c143a..98fa8c4 100644
--- a/edit-lens/src/Control/Edit.lhs
+++ b/edit-lens/src/Control/Edit.lhs
@@ -6,10 +6,10 @@ module Control.Edit
6\end{code} 6\end{code}
7\end{comment} 7\end{comment}
8 8
9Um das intuitive Verhalten von Änderungen auf Texten\footnote{Im folgenden \emph{edits}} und ihre interne algebraische Struktur zu fassen formalisieren wir sie als \emph{Moduln}: 9Um das intuitive Verhalten von Änderungen auf Texten\footnote{Im folgenden \emph{edits}} und ihre interne algebraische Struktur zu fassen, formalisieren wir sie als \emph{Moduln}:
10 10
11\begin{defn}[Moduln] 11\begin{defn}[Moduln]
12Ein \emph{Modul} $M$ ist eine partielle Monoidwirkung zusammen mit einem schwach-initialen Element\footnote{Gemeint ist hier die übliche Definition von \emph{schwach-initial} aus der Kategorientheorie—ein Modul $M$ bildet eine Kategorie mit Objekten aus $\Dom M$ und Morphismen von $x$ nach $y$ den Monoidelementen $\partial x \in \partial M$ sodass $x \cdot \partial x = y$} (bzgl. der Monoidwirkung) auf dem Träger, d.h. $M = (\Dom M, \partial M, \init_M)$ ist ein Tupel aus einer Trägermenge $\Dom M$, einem Monoid $\partial M$ zusammen mit mit einer partiellen Funktion $\cdot \colon \Dom M \times \partial M \to \Dom$, die \emph{kompatibel} ist mit der Monoid-Struktur: 12Ein \emph{Modul} $M$ ist eine partielle Monoidwirkung zusammen mit einem schwach-initialen Element\footnote{Gemeint ist hier die übliche Definition von \emph{schwach-initial} aus der Kategorientheorie—ein Modul $M$ bildet eine Kategorie mit Objekten aus $\Dom M$ und Morphismen von $x$ nach $y$ den Monoidelementen $\partial x \in \partial M$ sodass $x \cdot \partial x = y$} (bzgl. der Monoidwirkung) auf dem Träger. D.h. $M = (\Dom M, \partial M, \init_M)$ ist ein Tupel aus einer Trägermenge $\Dom M$, einem Monoid $\partial M$ zusammen mit einer partiellen Funktion $\cdot \colon \Dom M \times \partial M \to \Dom M$, die \emph{kompatibel} ist mit der Monoid-Struktur:
13 13
14\begin{itemize} 14\begin{itemize}
15 \item $\forall m \in \Dom M \colon m \cdot 1_{\partial M} = m$ 15 \item $\forall m \in \Dom M \colon m \cdot 1_{\partial M} = m$
@@ -22,7 +22,7 @@ $$\forall m \in \Dom M \ \exists \partial m \in \partial M \colon m = \init_M \c
22 22
23Wir führen außerdem eine Abbildung $(\init_M \cdot)^{-1} \colon \Dom M \to \partial m$ ein, die ein $m$ auf ein arbiträr gewähltes $\partial m$ abbildet für das $\init_M \cdot \partial m = m$ gilt. 23Wir führen außerdem eine Abbildung $(\init_M \cdot)^{-1} \colon \Dom M \to \partial m$ ein, die ein $m$ auf ein arbiträr gewähltes $\partial m$ abbildet für das $\init_M \cdot \partial m = m$ gilt.
24 24
25In Haskell charakterisieren wir Moduln über ihren Monoid, d.h. die Wahl des Monoiden \texttt{m} legt den Träger \texttt{Domain m}, die Wirkung \texttt{apply}, das initiale Element \texttt{init} und $(\init_M \cdot)^{-1}$ eindeutig fest\footnote{Betrachten wir mehrere Moduln über dem selben Träger (oder mit verschiedenen Wirkungen) führen wir neue, isomorphe Typen ein (\texttt{newtype}-Wrapper)}. 25In Haskell charakterisieren wir Moduln über ihren Monoid, d.h. die Wahl des Monoiden \texttt{m} legt den Träger \texttt{Domain m}, die Wirkung \texttt{apply}, das initiale Element \texttt{init} und $(\init_M \cdot)^{-1}$ eindeutig fest\footnote{Betrachten wir mehrere Moduln über dem selben Träger (oder mit verschiedenen Wirkungen), führen wir neue, isomorphe Typen ein (\texttt{newtype}-Wrapper)}.
26Eine Repräsentierung als Typklasse bietet sich an: 26Eine Repräsentierung als Typklasse bietet sich an:
27 27
28\begin{code} 28\begin{code}
@@ -50,7 +50,7 @@ apply' md e = flip apply e =<< md
50\end{code} 50\end{code}
51\end{defn} 51\end{defn}
52 52
53Wir weichen von der originalen Definition von Moduln aus \cite{hofmann2012edit} darin ab, dass wir für das ausgezeichnete Element $\init_X$ des Trägers explizit (und konstruktiv\footnote{$(\init_M \cdot)^{-1}$}) fordern, dass es ein schwach-initiales Element bzgl. der Monoidwirkung sei. 53Wir weichen von der originalen Definition von Moduln aus \cite{hofmann2012edit} ab, indem wir für das ausgezeichnete Element $\init_X$ des Trägers explizit (und konstruktiv\footnote{$(\init_M \cdot)^{-1}$}) fordern, dass es ein schwach-initiales Element bzgl. der Monoidwirkung sei.
54 54
55\begin{comment} 55\begin{comment}
56\begin{defn}[Modulhomomorphismen] 56\begin{defn}[Modulhomomorphismen]
diff --git a/edit-lens/src/Control/Edit/String.lhs b/edit-lens/src/Control/Edit/String.lhs
index c1411cf..f0ca588 100644
--- a/edit-lens/src/Control/Edit/String.lhs
+++ b/edit-lens/src/Control/Edit/String.lhs
@@ -24,7 +24,7 @@ import Data.Monoid
24\end{comment} 24\end{comment}
25 25
26\begin{defn}[Atomare edits of strings] 26\begin{defn}[Atomare edits of strings]
27Wir betrachten, zur Einfachheit, ein minimiales Set von Edits auf Strings\footnote{Wie in der Konstruktion zum Longest Common Subsequence Problem}, bestehend nur aus Einfügung eines einzelnen Zeichens $\sigma$ an einer bestimmten Position $\iota_n(\sigma)$ und löschen des Zeichens an einer einzelnen Position $\rho_n$: 27Wir betrachten zur Einfachheit ein minimiales Set von Edits auf Strings\footnote{Wie in der Konstruktion zum Longest Common Subsequence Problem} bestehend nur aus Einfügung eines einzelnen Zeichens $\sigma$ an einer bestimmten Position $\iota_n(\sigma)$ und löschen des Zeichens an einer einzelnen Position $\rho_n$:
28 28
29\begin{code} 29\begin{code}
30data StringEdit pos char = Insert { _sePos :: pos, _seInsertion :: char } 30data StringEdit pos char = Insert { _sePos :: pos, _seInsertion :: char }
@@ -38,7 +38,7 @@ data StringEdit pos char = Insert { _sePos :: pos, _seInsertion :: char }
38makeLenses ''StringEdit 38makeLenses ''StringEdit
39\end{code} 39\end{code}
40 40
41Atomare edits werden, als Liste, zu edits komponiert. 41Atomare edits werden als Liste zu edits komponiert.
42Wir führen einen speziellen edit ein, der nicht-Anwendbarkeit der edits repräsentiert: 42Wir führen einen speziellen edit ein, der nicht-Anwendbarkeit der edits repräsentiert:
43\begin{code} 43\begin{code}
44data StringEdits pos char = StringEdits (Seq (StringEdit pos char)) 44data StringEdits pos char = StringEdits (Seq (StringEdit pos char))
diff --git a/edit-lens/src/Control/Edit/String/Affected.lhs b/edit-lens/src/Control/Edit/String/Affected.lhs
index 851267b..15f73af 100644
--- a/edit-lens/src/Control/Edit/String/Affected.lhs
+++ b/edit-lens/src/Control/Edit/String/Affected.lhs
@@ -29,7 +29,7 @@ import Data.Maybe (fromMaybe, maybeToList, listToMaybe, catMaybes, isNothing, is
29\end{comment} 29\end{comment}
30 30
31Um eine obere Schranke an das von einer Serie von edits betroffene Intervall zu bestimmen ordnen wir zunächst jeder von mindestens einem atomaren edit betroffenen Position $n$ im Eingabe-Wort einen $\text{offset}_n = \text{\# deletions} - \text{\# inserts}$ zu. 31Um eine obere Schranke an das von einer Serie von edits betroffene Intervall zu bestimmen ordnen wir zunächst jeder von mindestens einem atomaren edit betroffenen Position $n$ im Eingabe-Wort einen $\text{offset}_n = \text{\# deletions} - \text{\# inserts}$ zu.
32Das gesuchte Intervall ist nun $(\text{minK}, \text{maxK})$, mit $\text{minK}$ der Position im Eingabe-Wort mit niedrigstem $\text{offset}$ und $\text{maxK}$ die Position im Eingabe-Wort mit höchstem $\text{offset}$, $\text{maxK}^\prime$, modifiziert um das Maximum aus $\{ 0 \} \cup \{ \text{maxK}_n \colon n \in \{ 0 \ldots \text{maxK}^\prime \} \}$ wobei $\text{maxK}_n = -1 \cdot (n + \text{offset}_n)$ an Position $n$ ist. 32Das gesuchte Intervall ist nun $(\text{minK}, \text{maxK})$, mit $\text{minK}$ der Position im Eingabe-Wort mit niedrigstem $\text{offset}$ und $\text{maxK}$ die Position im Eingabe-Wort mit höchstem $\text{offset}$ $\text{maxK}^\prime$ modifiziert um das Maximum aus $\{ 0 \} \cup \{ \text{maxK}_n \colon n \in \{ 0 \ldots \text{maxK}^\prime \} \}$ wobei $\text{maxK}_n = -1 \cdot (n + \text{offset}_n)$ an Position $n$ ist.
33 33
34\begin{code} 34\begin{code}
35affected :: forall char. StringEdits Natural char -> Maybe (Interval Natural) 35affected :: forall char. StringEdits Natural char -> Maybe (Interval Natural)
diff --git a/edit-lens/src/Control/FST.lhs b/edit-lens/src/Control/FST.lhs
index 9cc7524..165f247 100644
--- a/edit-lens/src/Control/FST.lhs
+++ b/edit-lens/src/Control/FST.lhs
@@ -47,12 +47,12 @@ import Text.Dot
47\end{comment} 47\end{comment}
48 48
49\begin{defn}[Finite State Transducers] 49\begin{defn}[Finite State Transducers]
50Unter einem \emph{finite state transducer} verstehen wir ein 6-Tupel $(\Sigma, \Delta, Q, I, F, E)$ mit $\Sigma$ dem endlichen Eingabe-Alphabet, $\Delta$ dem endlichen Ausgabe-Alphabet, $Q$ einer endlichen Menge an Zuständen, $I \subset Q$ der Menge von initialen Zuständen, $F \subset Q$ der Menge von akzeptierenden Endzuständen, und $E \subset Q \times (\Sigma \cup \{ \epsilon \}) \times (\Delta \cup \{ \epsilon \}) \times Q$ der Transitionsrelation. 50Unter einem \emph{finite state transducer} verstehen wir ein 6-Tupel $(\Sigma, \Delta, Q, I, F, E)$ mit $\Sigma$ dem endlichen Eingabe-Alphabet, $\Delta$ dem endlichen Ausgabe-Alphabet, $Q$ einer endlichen Menge an Zuständen, $I \subset Q$ der Menge von initialen Zuständen, $F \subset Q$ der Menge von akzeptierenden Endzuständen und $E \subset Q \times (\Sigma \cup \{ \epsilon \}) \times (\Delta \cup \{ \epsilon \}) \times Q$ der Transitionsrelation.
51 51
52Semantisch ist ein finite state transducer ein endlicher Automat erweitert um die Fähigkeit bei Zustandsübergängen ein Symbol aus seinem Ausgabe-Alphabet an ein Ausgabe-Wort anzuhängen. 52Semantisch ist ein finite state transducer ein endlicher Automat, erweitert um die Fähigkeit bei Zustandsübergängen ein Symbol aus seinem Ausgabe-Alphabet an ein Ausgabe-Wort anzuhängen (Siehe Definition \ref{defn:fst-eval}).
53 53
54In Haskell lockern wir die Anforderung, dass die Ein- und Ausgabe-Alphabete endlich sein müssen und annotieren sie nur im Typsystem. 54In Haskell lockern wir die Anforderung, dass die Ein- und Ausgabe-Alphabete endlich sein müssen und annotieren sie nur im Typsystem.
55Zudem speichern wir die Transitionsrelation als multimap um effiziente lookups von Zustand-Eingabe-Paaren zu ermöglichen. 55Zudem speichern wir die Transitionsrelation als multimap, um effiziente lookups von Zustand-Eingabe-Paaren zu ermöglichen.
56 56
57\begin{code} 57\begin{code}
58data FST state input output = FST 58data FST state input output = FST
@@ -64,7 +64,7 @@ data FST state input output = FST
64\end{defn} 64\end{defn}
65 65
66\begin{eg} \label{eg:linebreak} 66\begin{eg} \label{eg:linebreak}
67 Als wiederkehrendes Beispiel betrachten wir einen Transducer $L_{80} = (\Sigma, \Delta, Q, I, F, E)$, der für ein beliebiges Alphabet $\Sigma \supseteq \{ \text{\tt ' '}, \text{\tt \textbackslash n} \}$ durch Umwandlung zwischen Leerzeichen und Zeilenumbrüchen sicherstellt, dass jede Zeile des Ausgabetextes möglichst wenige aber mindestens 80 Zeichen enthält, und nur an Wortgrenzen umbricht: 67 Als wiederkehrendes Beispiel betrachten wir einen Transducer $L_{80} = (\Sigma, \Delta, Q, I, F, E)$, der für ein beliebiges Alphabet $\Sigma \supseteq \{ \text{\tt ' '}, \text{\tt \textbackslash n} \}$ durch Umwandlung zwischen Leerzeichen und Zeilenumbrüchen sicherstellt, dass jede Zeile des Ausgabetextes möglichst wenige, aber mindestens 80 Zeichen enthält und nur an Wortgrenzen umbricht:
68 68
69 \begin{align*} 69 \begin{align*}
70 \Delta & = \Sigma \\ 70 \Delta & = \Sigma \\
@@ -103,7 +103,7 @@ data FST state input output = FST
103 \draw[-] (rest)--(i.north); 103 \draw[-] (rest)--(i.north);
104 \draw[-] (rest)--(si.west); 104 \draw[-] (rest)--(si.west);
105 \end{tikzpicture} 105 \end{tikzpicture}
106 \caption{\label{fig:linebreak} Ein Transducer der, durch Übersetzung zwischen Leerzeichen und Zeilenumbrüchen, sicher stellt, dass jede Zeile eines Texts mindestens 80 Zeichen hat} 106 \caption{\label{fig:linebreak} Ein Transducer der durch Übersetzung zwischen Leerzeichen und Zeilenumbrüchen sicher stellt, dass jede Zeile eines Texts mindestens 80 Zeichen hat}
107 \end{figure} 107 \end{figure}
108\end{eg} 108\end{eg}
109 109
@@ -131,8 +131,8 @@ instance (Show state, Show input, Show output, Ord state, Ord input, Ord output)
131\end{code} 131\end{code}
132\end{comment} 132\end{comment}
133 133
134\begin{defn}[Auswertung von FSTs] 134\begin{defn}[Auswertung von FSTs] \label{defn:fst-eval}
135Wir definieren die \emph{Auswertung} von finite state transducers induktiv indem wir zunächst angeben wie ein einzelner Auswertungs-Schritt erfolgt. 135Wir definieren die \emph{Auswertung} von finite state transducers induktiv, indem wir zunächst angeben, wie ein einzelner Auswertungs-Schritt erfolgt.
136 136
137Hierzu kommentieren wir die Haskell-Implementierung eines Auswertungs-Schritts. 137Hierzu kommentieren wir die Haskell-Implementierung eines Auswertungs-Schritts.
138Notwendigerweise ist die Auswertung eines FSTs nicht deterministisch, wir produzieren daher eine Liste von möglichen Resultaten in keiner besonderen Reihenfolge. 138Notwendigerweise ist die Auswertung eines FSTs nicht deterministisch, wir produzieren daher eine Liste von möglichen Resultaten in keiner besonderen Reihenfolge.
@@ -145,7 +145,7 @@ step :: forall input output state. (Ord input, Ord output, Ord state)
145 -> [(Maybe input, state, Maybe output)] -- ^ Tuples of unconsumed input, next state, and produced output 145 -> [(Maybe input, state, Maybe output)] -- ^ Tuples of unconsumed input, next state, and produced output
146step FST{..} Nothing inS = (\s -> (inS, s, Nothing)) <$> Set.toList stInitial 146step FST{..} Nothing inS = (\s -> (inS, s, Nothing)) <$> Set.toList stInitial
147\end{code} 147\end{code}
148Ist kein vorheriger Schritt erfolgt so wählen wir einen initialen Zustand, konsumieren keine Eingabe, und produzieren keine Ausgabe. 148Ist kein vorheriger Schritt erfolgt, so wählen wir einen initialen Zustand, konsumieren keine Eingabe und produzieren keine Ausgabe.
149 149
150\begin{code} 150\begin{code}
151step FST{..} (Just c) inS = let 151step FST{..} (Just c) inS = let
@@ -154,7 +154,7 @@ step FST{..} (Just c) inS = let
154 in Set.toList $ Set.map (\(n, mOut) -> (Nothing, n, mOut)) consuming `Set.union` Set.map (\(n, mOut) -> (inS, n, mOut)) unconsuming 154 in Set.toList $ Set.map (\(n, mOut) -> (Nothing, n, mOut)) consuming `Set.union` Set.map (\(n, mOut) -> (inS, n, mOut)) unconsuming
155\end{code} 155\end{code}
156Ansonsten wählen wir einen Eintrag aus der Transitionstabelle für den aktuellen Zustand, der entweder keine oder die gegebene Eingabe konsumiert. 156Ansonsten wählen wir einen Eintrag aus der Transitionstabelle für den aktuellen Zustand, der entweder keine oder die gegebene Eingabe konsumiert.
157Im Ergebnis geben wir den nächsten Zustand, die Ausgabe aus der Transitionstabelle, und ob die Eingabe konsumiert wurde an. 157Im Ergebnis geben wir den nächsten Zustand, die Ausgabe aus der Transitionstabelle und ob die Eingabe konsumiert wurde, an.
158 158
159\begin{code} 159\begin{code}
160runFST' :: forall input output state. (Ord input, Ord output, Ord state) 160runFST' :: forall input output state. (Ord input, Ord output, Ord state)
@@ -199,9 +199,8 @@ akzeptierenden Endzustände liegt.
199\end{comment} 199\end{comment}
200\end{defn} 200\end{defn}
201 201
202Es ist gelegentlich nützlich nur die möglichen Ausgaben eines FST auf gegebener 202Es ist gelegentlich nützlich nur die möglichen Ausgaben eines FST auf gegebener Eingabe zu bestimmen.
203Eingabe zu bestimmen, wir führen eine Hilfsfunktion auf Basis von 203Wir führen eine Hilfsfunktion auf Basis von {\ttfamily runFST'} ein:
204{\ttfamily runFST'} ein:
205 204
206\begin{code} 205\begin{code}
207runFST :: forall input output state. (Ord input, Ord output, Ord state) => FST state input output -> Seq input -> [Seq output] 206runFST :: forall input output state. (Ord input, Ord output, Ord state) => FST state input output -> Seq input -> [Seq output]
@@ -216,14 +215,14 @@ runFST = fmap (map $ catMaybes . fmap (view _2) . view _2) . runFST'
216\end{comment} 215\end{comment}
217 216
218Wir können das Produkt zweier FSTs definieren. 217Wir können das Produkt zweier FSTs definieren.
219Intuitiv wollen wir beide FSTs gleichzeitig ausführen und dabei sicherstellen, dass Ein- und Ausgabe der FSTs übereinstimmen\footnote{Da wir $\epsilon$-Transitionen in FSTs erlauben müssen wir uns festlegen wann eine $\epsilon$-Transition übereinstimmt mit einer anderen Transition. Wir definieren, dass $\epsilon$ als Eingabe ausschließlich mit $\epsilon$ übereinstimmt.}. 218Intuitiv wollen wir beide FSTs gleichzeitig ausführen und dabei sicherstellen, dass Ein- und Ausgabe der FSTs übereinstimmen\footnote{Da wir $\epsilon$-Transitionen in FSTs erlauben, müssen wir uns festlegen, wann eine $\epsilon$-Transition übereinstimmt mit einer anderen Transition. Wir definieren, dass $\epsilon$ als Eingabe ausschließlich mit $\epsilon$ übereinstimmt.}.
220 219
221Hierfür berechnen wir das Graphen-Produkt der FSTs: 220Hierfür berechnen wir das Graphen-Produkt der FSTs:
222 221
223\begin{defn}[FST-Produkt] 222\begin{defn}[FST-Produkt]
224 Gegeben zwei finite state transducer $T = (\Sigma, \Delta, Q, I, F, E)$ und $T^\prime = (\Sigma^\prime, \Delta^\prime, Q^\prime, I^\prime, F^\prime, E^\prime)$ nennen wir $T^\times = (\Sigma^\times, \Delta^\times, Q^\times, I^\times, F^\times, E^\times)$ das Produkt $T^\times = T \times T^\prime$ von $T$ und $T^\prime$. 223 Gegeben zwei finite state transducer $T = (\Sigma, \Delta, Q, I, F, E)$ und $T^\prime = (\Sigma^\prime, \Delta^\prime, Q^\prime, I^\prime, F^\prime, E^\prime)$ nennen wir $T^\times = (\Sigma^\times, \Delta^\times, Q^\times, I^\times, F^\times, E^\times)$ das Produkt $T^\times = T \times T^\prime$ von $T$ und $T^\prime$.
225 224
226 $T^\times$ bestimmt sich als das Graphenprodukt der beiden, die FSTs unterliegenden, Graphen wobei wir die Zustandsübergänge als Kanten mit Gewichten aus dem Boolschen Semiring auffassen: 225 $T^\times$ wird bestimmt als das Graphenprodukt der beiden die FSTs unterliegenden Graphen wobei wir die Zustandsübergänge als Kanten mit Gewichten aus dem Boolschen Semiring auffassen:
227 226
228 \begin{align*} 227 \begin{align*}
229 \Sigma^\times & = \Sigma \cap \Sigma^\prime \\ 228 \Sigma^\times & = \Sigma \cap \Sigma^\prime \\
@@ -271,7 +270,7 @@ productFST fst1 fst2 = FST
271Es ist später erforderlich einen FST derart einzuschränken, dass er eine gegebene Ausgabe produziert. 270Es ist später erforderlich einen FST derart einzuschränken, dass er eine gegebene Ausgabe produziert.
272 271
273Hierzu nehmen wir das FST-Produkt mit einem FST, der, ungeachtet der Eingabe, immer die gewünschte Ausgabe produziert. 272Hierzu nehmen wir das FST-Produkt mit einem FST, der, ungeachtet der Eingabe, immer die gewünschte Ausgabe produziert.
274Da die Ausgaben der beiden FSTs übereinstimmen müssen produziert das Produkt mit einem derartigen FST (solange dessen Ausgabe in keinem Sinne von der Eingabe abhängt) die gewünschte Ausgabe. 273Da die Ausgaben der beiden FSTs übereinstimmen müssen, produziert das Produkt mit einem derartigen FST (solange dessen Ausgabe in keinem Sinne von der Eingabe abhängt) die gewünschte Ausgabe.
275 274
276Zur Konstruktion eines derartigen \emph{Wort-FST}s nehmen wir Indizes im Ausgabe-Wort (natürliche Zahlen) als Zustände. 275Zur Konstruktion eines derartigen \emph{Wort-FST}s nehmen wir Indizes im Ausgabe-Wort (natürliche Zahlen) als Zustände.
277Übergänge sind immer entweder der Form $n \rightarrow \text{succ}(n)$, konsumieren keine Eingabe ($\epsilon$) und produzieren als Ausgabe das Zeichen am Index $n$ im Ausgabe-Wort, oder der Form $n \overset{(\sigma, \epsilon)}{\rightarrow} n$, für jedes Eingabesymbol $\sigma$ (um die Unabhängigkeit von der Eingabe sicherzustellen). 276Übergänge sind immer entweder der Form $n \rightarrow \text{succ}(n)$, konsumieren keine Eingabe ($\epsilon$) und produzieren als Ausgabe das Zeichen am Index $n$ im Ausgabe-Wort, oder der Form $n \overset{(\sigma, \epsilon)}{\rightarrow} n$, für jedes Eingabesymbol $\sigma$ (um die Unabhängigkeit von der Eingabe sicherzustellen).
@@ -335,7 +334,7 @@ wordFST inps outs = FST
335 \end{figure} 334 \end{figure}
336\end{eg} 335\end{eg}
337 336
338Da \texttt{wordFST} zur Konstruktion eine komprehensive Menge aller Eingabesymbole benötigt verwenden wir im folgenden eine optimierte Variante des Produkts mit einem Wort-FST. 337Da \texttt{wordFST} zur Konstruktion eine komprehensive Menge aller Eingabesymbole benötigt, verwenden wir im Folgenden eine optimierte Variante des Produkts mit einem Wort-FST.
339 338
340\begin{code} 339\begin{code}
341restrictOutput :: forall state input output. (Ord state, Ord input, Ord output) => Seq output -> FST state input output -> FST (Natural, state) input output 340restrictOutput :: forall state input output. (Ord state, Ord input, Ord output) => Seq output -> FST state input output -> FST (Natural, state) input output
@@ -381,7 +380,7 @@ restrictOutput :: forall state input output. (Ord state, Ord input, Ord output)
381\begin{rem} 380\begin{rem}
382 Es ist bemerkenswert, dass in Beispiel \ref{eg:l80timesw100} die zirkuläre Struktur von $L_{80}$ durch das Produkt mit einem Wort verloren geht. 381 Es ist bemerkenswert, dass in Beispiel \ref{eg:l80timesw100} die zirkuläre Struktur von $L_{80}$ durch das Produkt mit einem Wort verloren geht.
383 382
384 I.\@A.\@ ist das Produkt eines beliebigen FST mit einem Wort-FST zwar nicht azyklisch, erbt jedoch die lineare Struktur des Wort-FST in dem Sinne, dass Fortschritt in Richtung der akzeptierenden Zustände nur möglich ist indem der $(i, \sigma, w_i, i + 1)$-Klasse von Transitionen des Wort-FSTs gefolgt wird. 383 I.\@A.\@ ist das Produkt eines beliebigen FST mit einem Wort-FST zwar nicht azyklisch, erbt jedoch die lineare Struktur des Wort-FST in dem Sinne, dass Fortschritt in Richtung der akzeptierenden Zustände nur möglich ist, indem der $(i, \sigma, w_i, i + 1)$-Klasse von Transitionen des Wort-FSTs gefolgt wird.
385\end{rem} 384\end{rem}
386 385
387\begin{comment} 386\begin{comment}
diff --git a/edit-lens/src/Control/FST/Lens.tex b/edit-lens/src/Control/FST/Lens.tex
index 31af317..7e9e9e3 100644
--- a/edit-lens/src/Control/FST/Lens.tex
+++ b/edit-lens/src/Control/FST/Lens.tex
@@ -1,4 +1,4 @@
1Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nondeterminische finite state transducers anwenden lässt. 1Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nicht determinische finite state transducers anwenden lässt.
2 2
3Eine natürlich Erweiterung von \texttt{DFSTAction} wäre: 3Eine natürlich Erweiterung von \texttt{DFSTAction} wäre:
4\begin{lstlisting}[language=Haskell] 4\begin{lstlisting}[language=Haskell]
@@ -9,7 +9,7 @@ data FSTAction state input output = FSTAction
9\end{lstlisting} 9\end{lstlisting}
10wobei die Liste aller möglichen output-Strings in der rechten Seite von \texttt{runFSTAction} in aller Regel unendlich ist. 10wobei die Liste aller möglichen output-Strings in der rechten Seite von \texttt{runFSTAction} in aller Regel unendlich ist.
11 11
12$\Rrightarrow$ würde sich notwendigerweise arbiträr auf einen der möglichen output-Strings festlegen aber ansonsten wohl identisch zum DFST-Fall implementieren lassen. 12$\Rrightarrow$ würde sich notwendigerweise arbiträr auf einen der möglichen output-Strings festlegen, aber ansonsten wohl identisch zum DFST-Fall implementieren lassen.
13 13
14$\Lleftarrow$ basiert fundamental darauf im Komplement anhand der erzeugten output-Strings zu suchen (um das betroffene Intervall im output-String auf das Komplement zu übertragen). 14$\Lleftarrow$ basiert fundamental darauf im Komplement anhand der erzeugten output-Strings zu suchen (um das betroffene Intervall im output-String auf das Komplement zu übertragen).
15Um sicher zu stellen, dass jene Suche immer terminiert, müsste die Aufzählung der i.A. unendlich vielen zulässigen output-Strings in \texttt{FSTAction} geschickt gewählt sein. 15Um sicher zu stellen, dass jene Suche immer terminiert, müsste die Aufzählung der i.A. unendlich vielen zulässigen output-Strings in \texttt{FSTAction} geschickt gewählt sein.
diff --git a/edit-lens/src/Control/Lens/Edit.lhs b/edit-lens/src/Control/Lens/Edit.lhs
index 5cf8662..84216bd 100644
--- a/edit-lens/src/Control/Lens/Edit.lhs
+++ b/edit-lens/src/Control/Lens/Edit.lhs
@@ -12,7 +12,7 @@ import Control.Edit
12\end{comment} 12\end{comment}
13 13
14\begin{defn}[Zustandsbehaftete Monoidhomomorphismen] 14\begin{defn}[Zustandsbehaftete Monoidhomomorphismen]
15Gegeben eine Menge $C$ von \emph{Komplementen} und zwei Monoiden $M$ und $N$ nennen wir eine partielle Funktion $\psi \colon C \times M \to C \times N$ einen \emph{zustandsbehafteten Monoidhomomorphismus} wenn sie den folgenden Ansprüchen genügt: 15Gegeben eine Menge $C$ von \emph{Komplementen} und zwei Monoiden $M$ und $N$ nennen wir eine partielle Funktion $\psi \colon C \times M \to C \times N$ einen \emph{zustandsbehafteten Monoidhomomorphismus}, wenn sie den folgenden Ansprüchen genügt:
16 16
17\begin{itemize} 17\begin{itemize}
18 \item $\forall c \in C \colon \psi(1_M, c) = (1_N, c)$ 18 \item $\forall c \in C \colon \psi(1_M, c) = (1_N, c)$
@@ -28,7 +28,7 @@ type StateMonoidHom s m n = (s, m) -> (s, n)
28\end{defn} 28\end{defn}
29 29
30\begin{defn}[edit-lenses] 30\begin{defn}[edit-lenses]
31Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$ und $N$ aus zwei zustandsbehafteten Monoidhomomorphismen $\Rrightarrow \colon C \times \partial M \to C \times \partial N$ und $\Lleftarrow \colon C \times \partial N \to C \times \partial M$, mit kompatiblem Komplement $C$, einem ausgezeichneten Element $\ground_C \in C$ und einer \emph{Konsistenzrelation} $K \subset \Dom M \times C \times \Dom N$ sodass gilt: 31Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$ und $N$ aus zwei zustandsbehafteten Monoidhomomorphismen $\Rrightarrow \colon C \times \partial M \to C \times \partial N$ und $\Lleftarrow \colon C \times \partial N \to C \times \partial M$, mit kompatiblem Komplement $C$, einem ausgezeichneten Element $\ground_C \in C$ und einer \emph{Konsistenzrelation} $K \subset \Dom M \times C \times \Dom N$, sodass gilt:
32 32
33\begin{itemize} 33\begin{itemize}
34 \item $(\init_M, \ground_C, \init_N) \in K$ 34 \item $(\init_M, \ground_C, \init_N) \in K$
@@ -43,7 +43,7 @@ Für Moduln $M$ und $N$ besteht eine \emph{symmetrische edit-lens} zwischen $M$
43 43
44Wir schreiben auch nur \emph{edit-lens} für den symmetrischen Fall\footnote{Für den asymmetrischen Fall siehe \cite{johnson2016unifying}}. 44Wir schreiben auch nur \emph{edit-lens} für den symmetrischen Fall\footnote{Für den asymmetrischen Fall siehe \cite{johnson2016unifying}}.
45 45
46In Haskell erwähnen wir die Konsistenzrelation nicht in der Erwartung, dass $\Rrightarrow$ und $\Lleftarrow$ nur auf konsistente Zustände angewandt werden (und somit auch entweder einen konsistenten Zustand erzeugen oder nicht definiert sind): 46In Haskell erwähnen wir die Konsistenzrelation nicht, in der Erwartung, dass $\Rrightarrow$ und $\Lleftarrow$ nur auf konsistente Zustände angewandt werden (und somit auch entweder einen konsistenten Zustand erzeugen oder nicht definiert sind):
47 47
48\begin{code} 48\begin{code}
49data EditLens c m n where 49data EditLens c m n where
@@ -67,12 +67,12 @@ instance (Module m, Module n) => HasEditLens (EditLens c m n) m n where
67\end{code} 67\end{code}
68\end{defn} 68\end{defn}
69 69
70\subsection{Kompatibilität mit bestehenden lens frameworks} 70\subsection{Kompatibilität mit bestehenden lens Frameworks}
71 71
72Das einschlägige bestehende lens framework \cite{lens} konstruiert seine Linsen à la \citeauthor{laarhoven} wie folgt: 72Das einschlägige bestehende lens framework \cite{lens} konstruiert seine Linsen à la \citeauthor{laarhoven} wie folgt:
73 73
74\begin{defn}[lenses à la Laarhoven] 74\begin{defn}[lenses à la Laarhoven]
75Für Typen $n$ und $m$ ist eine \emph{lens} $\ell$ von $n$ in $m$ eine Abbildung\footnote{Gdw. die betrachtete Linse einen Isomorphismus kodiert wird auch über den verwendeten Profunktor anstatt $\to$ quantifiziert} folgender Struktur: 75Für Typen $n$ und $m$ ist eine \emph{lens} $\ell$ von $n$ in $m$ eine Abbildung\footnote{Gdw. die betrachtete Linse einen Isomorphismus kodiert, wird auch über den verwendeten Profunktor anstatt $\to$ quantifiziert} folgender Struktur:
76 76
77$$ \forall f \, \text{Funktor} \colon \left ( \ell \colon \left ( m \to f(m) \right ) \to \left ( n \to f(n) \right ) \right )$$ 77$$ \forall f \, \text{Funktor} \colon \left ( \ell \colon \left ( m \to f(m) \right ) \to \left ( n \to f(n) \right ) \right )$$
78 78
@@ -80,7 +80,7 @@ Durch geschickte Wahl des Funktors\footnote{\texttt{Const m} bzw. \texttt{Identi
80\end{defn} 80\end{defn}
81 81
82Es liegt nun nahe $\nearrow \colon (m \to m) \to (n \to n)$ mit $\Rrightarrow \colon \partial m \to \partial n$ zu identifizieren. 82Es liegt nun nahe $\nearrow \colon (m \to m) \to (n \to n)$ mit $\Rrightarrow \colon \partial m \to \partial n$ zu identifizieren.
83Und in der Tat, eine Funktion $\text{map} \colon (o \to o) \to \partial o$ für $o \in \{ m, n \}$ würde van Laarhoven-lenses in edit-lenses einbetten. 83In der Tat, eine Funktion $\text{map} \colon (o \to o) \to \partial o$ für $o \in \{ m, n \}$ würde van Laarhoven-lenses in edit-lenses einbetten.
84Die charakteristische Eigenschaft der Betrachtung als edit-lens, nämlich die algebraische Struktur von $\partial o$, würde hierbei jedoch notwendigerweise verloren gehen. 84Die charakteristische Eigenschaft der Betrachtung als edit-lens, nämlich die algebraische Struktur von $\partial o$, würde hierbei jedoch notwendigerweise verloren gehen.
85 85
86Wegen diesem Argument haben wir entschieden keine Komponierbarkeit (durch $\text{id} \colon a \to a$ und $\circ \colon (b \to c) \to (a \to b) \to (a \to c)$, wie in \cite{lens}) von edit-lenses mit van Laarhoven-lenses anzustreben. 86Wegen diesem Argument haben wir entschieden keine Komponierbarkeit (durch $\text{id} \colon a \to a$ und $\circ \colon (b \to c) \to (a \to b) \to (a \to c)$, wie in \cite{lens}) von edit-lenses mit van Laarhoven-lenses anzustreben.