Verwendung von Lambda-Ausdrücke Vereinfachen und eine Karte in dem Staat Monad

Question

Diese Funktion memoizing ist viel schneller als seine rekursive Version:

crossSubstrings :: String -> String -> [(String,String)] 
crossSubstrings string1 string2 = [(substr1,substr2) | substr1 <- inits string1, 
                 substr2 <- inits string2] 

type Distances = Map.Map (String,String) Int 

editDistanceMemoized :: String -> String -> Int 
editDistanceMemoized s1 s2 = 
    let 
    substrings = s1 `crossSubstrings` s2 
    distances = foldl (editDistance) emptyMap substrings 
    in 
    distances Map.! (s1,s2) 
    where 
    emptyMap = Map.fromList [] 
    editDistance :: Distances -> (String,String) -> Distances 
    editDistance map ([],s1) = map `Map.union` getMap [] s1 (length s1) 
    editDistance map (s1,[]) = map `Map.union` getMap s1 [] (length s1) 
    editDistance map (s1,s2) = map `Map.union` getMap s1 s2 (cost map s1 s2) 
    getMap s1 s2 d = Map.fromList [((s1,s2),d)] 
    insertionPCost = \m -> \s1 -> \s2 -> m Map.! (s1, init s2) + 1 
    deletionPCost = \m -> \s1 -> \s2 -> m Map.! (init s1, s2) + 1 
    substitutionPCost = \m -> \s1 -> \s2 -> m Map.! (init s1, init s2) 
              + substitutionCostIfNEQ s1 s2 
    substitutionCostIfNEQ = \s1 -> \s2 -> if (last s1 == last s2) then 0 else 2 
    cost = \m -> \s1 -> \s2 -> minimum [insertionPCost m s1 s2, 
             deletionPCost m s1 s2, 
             substitutionPCost m s1 s2] 

jedoch (erste Frage), ich fühle mich wie einige lambdas vermieden werden könnte (doesn‘ t es sich wiederholend aussehen? schauen Sie besonders an cost). Gibt es eine Möglichkeit, minimum zu komponieren?

Darüber hinaus könnte die State Monad verwendet werden, um die Karte zu propagieren (anstelle von ?). Trotz der Lektüre, wie sich State.>>= und State.id verhalten, bin ich mir nicht 100% ig sicher, wie die Signatur aussehen soll (zweite Frage).

Ich dachte an diese, wo der Staat ist "das nächste Paar von Strings gemessen werden soll" und Entfernungen enthält die Memo-Distanzen.

editDistance :: State Distances (String,String) -> State Distances()? 

Answer 1

insertionPCost, deletionPCost, substitutionPCost und substitutionCostIfNEQ sind nur voneinander und cost, genannt und immer mit den gleichen Argumenten (außer dass substitutionCostIfNEQ nicht m dauern); so können wir sie wie folgt neu angeordnet:

cost = \m -> \s1 -> \s2 -> minimum [insertionPCost, deletionPCost, substitutionPCost] 
    where insertionPCost = m Map.! (s1, init s2) + 1 
     deletionPCost = m Map.! (init s1, s2) + 1 
     substitutionPCost = m Map.! (init s1, init s2) + substitutionCostIfNEQ 
     substitutionCostIfNEQ = if (last s1 == last s2) then 0 else 2 

Und die expliziten lambdas werden Sie nichts bekommen, so umschreiben klarer sein:

cost m s1 s2 = minimum [insertionPCost, deletionPCost, substitutionPCost] 
    where insertionPCost = m Map.! (s1, init s2) + 1 
     deletionPCost = m Map.! (init s1, s2) + 1 
     substitutionPCost = m Map.! (init s1, init s2) + substitutionCostIfNEQ 
     substitutionCostIfNEQ = if (last s1 == last s2) then 0 else 2 

---

Um Ihre zweite Frage zu beantworten, zur Zeit Sie haben

editDistance :: Distances -> (String,String) -> Distances 

Wenn Sie State stattdessen verwenden waren, das wäre

editDistance :: (String,String) -> State Distances() 

Das heißt, würde editDistance eine Funktion sein, die (String,String) nimmt, und liefert etwas, das mit einem Distances Zustand interagiert, und kein anderes sinnvolles Ergebnis.

Aber.

Erstens sehe ich nicht, dass irgendetwas mit der Verwendung von foldl falsch ist.

Zweitens verwenden Sie nie wirklich den akkumulierten Wert, was wäre der Staat. Sie verwenden es, um einen neuen Wert zu bilden, aber Sie sehen darin nichts aus. Sie brauchen also nicht State, Sie brauchen nur Writer.

editDistance :: (String,String) -> Writer Distances() 

Das heißt, würde editDistance eine Funktion sein, die (String,String) nimmt, und liefert etwas, das zu einem Distances Akkumulator addiert, und kein anderes sinnvolles Ergebnis.

(Es gibt eine Feinheit hier: der erste Parameter Writer ein Monoid sein muss, und es hat die Kombinationsoperation zu verwenden (mappend), das ist nützlich für Sie, gut, Map s sind Monoid s, und ihre mappend ist die das gleiche union, dass Sie in Ihrem ursprünglichen editDistance verwenden, so funktioniert alles gut.)