From 50e46d9e9b0b025afe1b433805a6f6d5df55894e Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Mon, 7 May 2018 11:32:30 +0200 Subject: Really just need prefixes/suffixes --- edit-lens/src/Data/String/DFST/Lens.lhs | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'edit-lens') diff --git a/edit-lens/src/Data/String/DFST/Lens.lhs b/edit-lens/src/Data/String/DFST/Lens.lhs index 51ce970..2111ca4 100644 --- a/edit-lens/src/Data/String/DFST/Lens.lhs +++ b/edit-lens/src/Data/String/DFST/Lens.lhs @@ -74,7 +74,7 @@ Gegeben eine Sequenz (`StringEdits`) von zu übersetzenden Änderungen genügt e Wir definieren zunächst die \emph{Wirkung} eines DFST auf einen festen String als eine Abbildung `state -> (state, String)`, die den aktuellen Zustand vorm Parsen des Strings auf den Zustand danach und die (womöglich leere) Ausgabe schickt. Diese Wirkungen bilden einen Monoiden analog zu Endomorphismen, wobei die Resultat-Strings concateniert werden. -Die Unterliegende Idee ist nun im Komplement der edit-lens eine Liste von Wirkungen (eine für jedes Zeichen der Eingabe des DFSTs) und einen Cache aller möglichen monoidalen Summen von zusammenhängenden Teilstücke zu halten. +Die Unterliegende Idee ist nun im Komplement der edit-lens eine Liste von Wirkungen (eine für jedes Zeichen der Eingabe des DFSTs) und einen Cache der monoidalen Summen aller möglich Präfixe und Suffixe zu halten. Da wir wissen welche Stelle im input-String von einem gegebenen edit betroffen ist können wir, anhand der Wirkung des Teilstücks bis zu jener Stelle, den output-String in einen durch den edit unveränderten Prefix und einen womöglich betroffenen Suffix unterteilen. Die Wirkung ab der betroffenen Stelle im input-String können wir also Komposition der Wirkung der durch den edit betroffenen Stelle und derer aller Zeichen danach bestimmen. Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes im output-String und des aus der gerade berechneten Wirkung Bestimmten zu bestimmen. @@ -82,6 +82,8 @@ Nun gilt es nur noch die Differenz (als `StringEdits`) des vorherigen Suffixes i \begin{code} data DFSTAction state = DFSTBranch (Map state (state, String)) (DFSTAction state) (DFSTAction state) + +% TODO propL, Transduktor invertieren? | DFSTLeaf dfstLens :: forall state. Ord state => DFST state -> EditLens (DFSTAction state) StringEdits StringEdits -- cgit v1.2.3