簡化使用lambda表達式，並在國家單子

Question

記憶一個地圖，此功能是遠遠超過它的遞歸版本速度更快：

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] 

但是（第一個問題），我覺得像一些lambda表達式是可以避免的（沒有按」它看起來重複？特別看cost）。有沒有辦法編寫minimum？

另外，State Monad可以用來傳播地圖（而不是使用foldl？）。儘管儘管讀到State.>>=和State.id的行爲如何，但我不能100％確定簽名應該是什麼樣子（第二個問題）。

我想到了這個，狀態是「下一對要測量的字符串」，距離包含記憶的距離。

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

Answer 1

insertionPCost，deletionPCost，substitutionPCost和substitutionCostIfNEQ只從對方cost，並總是以相同的參數調用（保存substitutionCostIfNEQ不採取m）;所以我們可以重新排列它們是這樣的：

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 

而且明確lambda表達式沒有得到你什麼，所以重寫更清晰：

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 

---

要回答你的第二個問題，目前你有

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

如果你使用State代替，這將是

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

也就是說，editDistance將是一個函數，它(String,String)，併產生一些具有Distances狀態交互，並沒有其他有意義的結果。

但是。

首先，我沒有看到你使用foldl有任何問題。其次，你從來沒有真正使用累計值，那會是什麼狀態。你用它來創造一個新的價值，但你沒有看到任何東西。所以你不需要State，你只需要Writer。

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

也就是說，editDistance將是一個函數，它(String,String)，而產生的東西，增加了一個Distances蓄電池，並沒有其他有意義的結果。

（有一個微妙的位置：到Writer第一個參數必須是一個Monoid，它必須使用組合操作（mappend）這是對你有用;還有，Map s爲Monoid s，而其mappend是與原來的editDistance中使用的union相同，所以一切正常。）