Упрощение использования лямбда-выражений и запоминание карты в государственной монаде - PullRequest
Новая
       10

Упрощение использования лямбда-выражений и запоминание карты в государственной монаде

0 голосов
/ 01 апреля 2012

Эта функция намного быстрее, чем ее рекурсивная версия: 

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]

Однако (первый вопрос) я чувствую, что некоторых лямбд можно избежать (разве это не выглядит многократно? Посмотрите специально на cost).Есть ли способ сочинения minimum?

Кроме того, для распространения карты можно использовать Государственную монаду (вместо использования foldl?).Несмотря на то, что я прочитал, как ведут себя State.>>= и State.id, я не уверен на 100%, как должна выглядеть подпись (второй вопрос).

Я думал об этой, где состояние «следующее»пара строк для измерения "и Расстояния содержат запомненные расстояния. 

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

1 Ответ

1 голос
/ 01 апреля 2012

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

И явные лямбды ничего вам не дают, поэтому перепишите, чтобы было яснее: 

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 - это то же самое union, которое вы используете в своем оригинальном editDistance, так что все работает нормально. *

...