修復用舊版F＃編寫的示例＃

Question

我在這裏找到了一篇很酷的博客文章，內容是關於使用Tries修復拼寫錯誤，但是它是用舊版本的F＃編寫的。
http://blog.lab49.com/archives/2841 我已經修復了大部分的問題，除非我已經在所有大寫的地方發表評論，我認爲事情出錯了。基本上在一些地方預計一套，並給出一個地圖<>，反之亦然。我一直盯着這段代碼幾個小時，似乎無法弄清楚事情是不匹配的。

open System 
open System.Linq 


///'k represents the base key type, and 'a represents the element type. 
type trie<'k,'a when 'k : comparison> = TNode of ('a option * Map<'k,trie<'k,'a>>) 

///'ks represents a type that stores a sequence of the key elements, and 'k represents the type of the key elements. 
type iter_module<'ks,'k> = 
    { 
     eos : ('ks -> bool) //whether or not a key-sequence is at its end. 
     head : ('ks -> 'k) //gets the current key-value in a key sequence 
     tail : ('ks -> 'ks) // increments the key-sequence iterator. 
    } 

let siterm : iter_module<string * int, char> = 
    { 
     eos = fun (s,i) -> i >= String.length s 
     head = fun (s,i) -> s.[i] 
     tail = fun (s,i) -> (s, i+1) 
    } 

///Extracts the option value associated with a node. 
let node_value = function 
| TNode (ov,_) -> ov 

///Extracts the map representing connections from the current trie node to sub-trees. 
let node_map = function 
| TNode (_, m) -> m 

///Determines whether a trie is empty 
let is_empty tn = Map.isEmpty (node_map tn) 

///Empty trie. 
let empty_trie = TNode (None, Map.empty) 

/// <summary> 
/// Find a sub-trie. 
/// </summary> 
/// <param name="tn">The current trie node.</param> 
/// <param name="k">The key.</param> 
let find_subtrie tn k = 
    try 
     Map.find k (node_map tn) 
    with 
     not_found -> empty_trie 

/// <summary> 
/// Update the trie. 
/// </summary> 
/// <param name="m">The iteration module.</param> 
/// <param name="tn">The trie node.</param> 
/// <param name="ks">a sequence of the key elements</param> 
/// <param name="v">Option containing the element</param> 
let add m tn ks v = 
    let rec upd tn' ks' = 
     if(m.eos ks') then 
      TNode(Some v, (node_map tn')) 
     else 
      let k = (m.head ks') in 
      let ov = node_value tn' in 
      let tn'' = upd(find_subtrie tn' k)(m.tail ks') in 
       TNode(ov, Map.add k tn'' (node_map tn')) 
    in 
     upd tn ks 

/// <summary> 
/// Lookup the option value associated with a string 
/// </summary> 
/// <param name="m">The iteration module.</param> 
/// <param name="tn">The trie node.</param> 
/// <param name="ks">a sequence of the key elements</param> 
let lookup m tn ks = 
    let rec lv tn' ks' = 
     if(m.eos ks') then 
      node_value tn' 
     else 
      let k = (m.head ks') in 
       lv(find_subtrie tn' k)(m.tail ks') 

    in 
     lv tn ks 

/// <summary> 
/// Determine whether or not a specific work is valid in the trie by a simple use of the lookup function. 
/// </summary> 
/// <param name="m">The iteration module.</param> 
/// <param name="tn">The trie node.</param> 
/// <param name="ks">a sequence of the key elements</param> 
let mem m tn ks = 
    match(lookup m tn ks) with 
    | Some _ -> true 
    | None -> false 

/// <summary> 
/// Determines the suffix of a string 
/// </summary> 
/// <param name="s">The string to find the suffix of.</param> 
/// <param name="i">The starting point of the suffix.</param> 
let suffix(s:String,i) = s.Substring(i,(String.length s - i)) 

/// <summary> 
/// Computes the set of words defined by a trie node if we follow any valid character from that node, and then try to follow a specific char sequences. 
/// </summary> 
/// <param name="pfx">The prefix.</param> 
/// <param name="trie">The trie node.</param> 
/// <param name="wi">Word index.</param> 
/// <param name="words">The words.</param> 
let strings_with_suffix pfx trie wi words = 
let accumulate_paths c trie' ws = 
    if (mem siterm trie' wi) then 
    Set.add (pfx + (string c) + (suffix wi)) ws 
    else 
    ws 
in 
//THIS IS WHERE THINGS APPEAR TO BE GOING WRONG 
Map.fold accumulate_paths (node_map trie) words 

/// <summary> 
/// Spelling correction suggestions. 
/// </summary> 
/// <param name="trie">The trie.</param> 
/// <param name="word">The mispelled word.</param> 
let suggestions trie word = 
    let rec paths_around_char pfx trie wi words = 
    if (siterm.eos wi) then 
    strings_with_suffix pfx trie ("", 0) words 
    else if (is_empty trie) then 
    words 
    else 
    let c  = siterm.head wi in 
    let wi' = siterm.tail wi in 
    let trie' = find_subtrie trie c in 
    let ins_ws = strings_with_suffix pfx trie wi words in 
    let rep_ws = strings_with_suffix pfx trie wi' ins_ws in 
    let del_ws = if (mem siterm trie wi') then 
        Set.add (pfx + (suffix wi')) rep_ws 
       else 
        rep_ws 
    in 
    paths_around_char (pfx + (string c)) trie' wi' del_ws 
    in 
    paths_around_char "" trie (word, 0) Set.empty 

由於提前，

鮑勃

Answer 1

看來，問題出在了Map.fold不同的簽名（舊版本的F＃標準庫中有不同的參數順序）在strings_with_suffix

sign折ATURE：（狀態 - >「鍵 - > '價值 - >' 狀態） - >狀態 - >地圖<」鍵， '值> - >' 國家

當前調用點：

let strings_with_suffix pfx trie wi words = 
    let accumulate_paths c trie' ws (* 2 *)= 
     if (mem siterm trie' wi) then 
      Set.add (pfx + (string c) + (suffix wi)) ws 
     else 
      ws 
in 
//THIS IS WHERE THINGS APPEAR TO BE GOING WRONG 
Map.fold accumulate_paths (node_map trie) (* 1 *) words 

1. 調用者傳遞「作爲最後一個參數，而不是第一
2. accumulate_paths國家接受」國家作爲最後一個參數，而不是第一

正確的版本看起來像：

let strings_with_suffix pfx trie wi words = 
    let accumulate_paths ws c trie' = 
     if (mem siterm trie' wi) then 
      Set.add (pfx + (string c) + (suffix wi)) ws 
     else 
      ws 
    in 
    Map.fold accumulate_paths words (node_map trie)