From 6d1f39826963890e9612b39f92843f134b6973f3 Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
Date: Mon, 5 Feb 2018 17:02:55 +0100
Subject: Framework for DFST edit lens

---
 edit-lens/src/Data/String/DFST.hs | 25 +++++++++++++------------
 1 file changed, 13 insertions(+), 12 deletions(-)

(limited to 'edit-lens/src/Data/String/DFST.hs')

diff --git a/edit-lens/src/Data/String/DFST.hs b/edit-lens/src/Data/String/DFST.hs
index 8a22dd3..75ca1cd 100644
--- a/edit-lens/src/Data/String/DFST.hs
+++ b/edit-lens/src/Data/String/DFST.hs
@@ -8,7 +8,7 @@ Description: Deterministic finite state transducers
 -}
 module Data.String.DFST
   ( DFST(..)
-  , runDFST
+  , runDFST, runDFST'
   ) where
 
 import Data.Map.Strict (Map, (!?))
@@ -17,6 +17,8 @@ import qualified Data.Map.Strict as Map
 import Data.Set (Set)
 import qualified Data.Set as Set
 
+import Control.Monad
+
 data DFST state = DFST
   { stInitial :: state
   , stTransition :: Map (state, Char) (state, Maybe Char)
@@ -25,14 +27,13 @@ data DFST state = DFST
   }
   
 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
+runDFST dfst@DFST{..} str = let (finalState, str') = runDFST' dfst stInitial str id
+                            in str' "" <$ guard (finalState `Set.member` stAccept)
+
+runDFST' :: forall state. Ord state => DFST state -> state -> String -> (String -> String) -> (state, (String -> String))
+runDFST' _ st [] acc = (st, acc)
+runDFST' dfst@DFST{..} st (c:cs) acc
+  | Just (st', mc') <- stTransition !? (st, c)
+  = runDFST' dfst st' cs $ acc . maybe id (:) mc'
+  | otherwise
+  = runDFST' dfst st cs acc
-- 
cgit v1.2.3