Define DFSTs

4 files changed, 42 insertions, 3 deletions

diff --git a/edit-lens/package.yaml b/edit-lens/package.yaml
index db1f021..5e8c2d2 100644
--- a/edit-lens/package.yaml
+++ b/edit-lens/package.yaml
@@ -23,8 +23,10 @@ library:
   dependencies:
     - base
     - lens
+    - containers
   exposed-modules:
     - Control.Edit
-    - Control.Edit.Tree
+    - Data.String.DFST
     - Control.Lens.Edit
+    
   
diff --git a/edit-lens/src/Data/String/DFST.hs b/edit-lens/src/Data/String/DFST.hs
new file mode 100644
index 0000000..8a22dd3
--- /dev/null
+++ b/edit-lens/src/Data/String/DFST.hs
@@ -0,0 +1,38 @@
+{-# LANGUAGE RecordWildCards
+           , PatternGuards
+           , ScopedTypeVariables
+#-}
+
+{-|
+Description: Deterministic finite state transducers
+-}
+module Data.String.DFST
+  ( DFST(..)
+  , runDFST
+  ) where
+
+import Data.Map.Strict (Map, (!?))
+import qualified Data.Map.Strict as Map
+
+import Data.Set (Set)
+import qualified Data.Set as Set
+
+data DFST state = DFST
+  { stInitial :: state
+  , stTransition :: Map (state, Char) (state, Maybe Char)
+    -- ^ All @(s, c)@-combinations not mapped are assumed to map to @(s, Nothing)@
+  , stAccept :: Set state
+  }
+  
+runDFST :: forall state. Ord state => DFST state -> String -> Maybe String
+runDFST DFST{..} str = ($ []) <$> go stInitial str id
+  where
+    go :: state -> String -> (String -> String) -> Maybe (String -> String)
+    go st [] acc
+      | st `Set.member` stAccept = Just acc
+      | otherwise = Nothing
+    go st (c:cs) acc
+      | Just (st', mc') <- stTransition !? (st, c)
+      = go st' cs $ acc . maybe id (:) mc'
+      | otherwise
+      = go st cs acc
diff --git a/stack.yaml b/stack.yaml
index 125d9fb..2e6ea32 100644
--- a/stack.yaml
+++ b/stack.yaml
@@ -1,4 +1,4 @@
-resolver: lts-9.9
+resolver: lts-10.4
 packages:
   - edit-lens
 nix:
diff --git a/thesis.tex b/thesis.tex
index f975ba7..6b94318 100644
--- a/thesis.tex
+++ b/thesis.tex
@@ -3,4 +3,3 @@ Dabei werden wir die Definitionen aus \cite{hofmann2012edit} sowohl in natürlic
 
 \input{./edit-lens/src/Control/Edit.lhs}
 \input{./edit-lens/src/Control/Lens/Edit.lhs}
-\input{./edit-lens/src/Control/Edit/Tree.lhs}