榆樹中最長的常見子序列與記憶

Question

我想在榆樹中製作一個高效版本的LCS算法。 我喜歡這個ocaml版本，但它使用副作用來緩存結果。

let lcs xs ys = 
    let cache = Hashtbl.create 16 in 
    let rec lcs xs ys = 
    try Hashtbl.find cache (xs, ys) with 
    | Not_found -> 
     let result = 
      match xs, ys with 
      | [], _ -> [] 
      | _, [] -> [] 
      | x :: xs, y :: ys when x = y -> 
       x :: lcs xs ys 
      | _ :: xs_rest, _ :: ys_rest -> 
       let a = lcs xs_rest ys in 
       let b = lcs xs  ys_rest in 
       if (List.length a) > (List.length b) then a else b 
     in 
     Hashtbl.add cache (xs, ys) result; 
     result 
    in 
    lcs xs ys 

我應該怎麼做，如果我想在榆樹中使用memoization？

Answer 1

吉爾伯特凱南在slack給了我，似乎效果更好版本：

lcs : List a -> List a -> List a 
lcs xs ys = 
    lcsHelper xs ys (0, 0) Dict.empty 
     |> Dict.get (0, 0) 
     |> Maybe.map Tuple.second 
     |> Maybe.withDefault [] 


lcsHelper : List a -> List a -> (Int, Int) -> Dict (Int, Int) (Int, List a) -> Dict (Int, Int) (Int, List a) 
lcsHelper xs ys position memo = 
    case (Dict.get position memo, xs, ys) of 
     (Nothing, x :: xRest, y :: yRest) -> 
      let 
       nextYPos = 
        Tuple.mapSecond ((+) 1) position 

       nextXPos = 
        Tuple.mapFirst ((+) 1) position 

       newMemo = 
        memo 
         |> lcsHelper xs yRest nextYPos 
         |> lcsHelper xRest ys nextXPos 

       best = 
        maxListTuple 
         (get nextXPos newMemo) 
         (get nextYPos newMemo) 
         |> consIfEqual x y 
      in 
       Dict.insert position best newMemo 

     _ -> 
      memo 

get : (Int, Int) -> Dict (Int, Int) (Int, List a) -> (Int, List a) 
get position memo = 
    Dict.get position memo |> Maybe.withDefault (0, []) 


maxListTuple : (Int, List a) -> (Int, List a) -> (Int, List a) 
maxListTuple (xLen, xs) (yLen, ys) = 
    if yLen > xLen then 
     (yLen, ys) 
    else 
     (xLen, xs) 


consIfEqual : a -> a -> (Int, List a) -> (Int, List a) 
consIfEqual x y (listLen, list) = 
    if x == y then 
     (listLen + 1, x :: list) 
    else 
     (listLen, list) 

它使用一本字典，因爲它進入緩存結果。

Answer 2

您可能想要使用自動記憶的Lazy package或使用明確記憶的elm-lazy package。

通過在Lazy中包裝內部遞歸函數，可以減少評估次數。在我的示例https://ellie-app.com/4hXx2X753wfa1/0中，約有300個Debug日誌條目用於懶惰版本，而大約700個條目用於非懶惰版本。