尾遞歸Ocaml程序

Question

我想將函數met_devant_et_acc變成一個尾遞歸函數，但我不知道如何重寫它。 met_devant_et_acc l h應該返回一個列表，其中包含列表l的所有列表以及所有這些列表中的元素h作爲第一個元素。

例如：met_devant_et_acc [ [1;2] ; [3;4] ]是[ [9;1;2] ; [9;3;4] ; [1;2] ; [3;4] ]

let rec met_devant_et_acc l h = match l with 
    | [] -> [[]] 
    | a::t -> (met_devant h l) @ l;; 

功能met_devant放元素h在每個列表的頭列表l

例如：met_devant h [ [ ]; ['x';'e']]回報[ ['h'] ; ['h';'x';'e'] ]

這裏的代碼met_devant

let rec met_devant h l = match l with 
    | [] -> l 
    | a::b -> List.map (ajoute h) l;; 

功能ajoute添加元素h到列表l

let ajoute t l = match l with 
    | [] -> l 
    | a::b -> t::l;; 

Answer 1

此功能是寫在F＃的頭，但它可能會在ocaml的編譯，也許小的修改。該函數不附加原始列表。

以相反的順序收集結果的原因是，我認爲預先計算比追加更有效，然後在循環後進行反轉。

let prependToLists lists element = 

    let rec loop (shrinkList, growList) = 
     match shrinkList with 
     | [] -> ([], growList) 
     | headList :: tailLists -> 
      let newGrowList = (element::headList)::growList 
      loop (tailLists, newGrowList) 

    let emptyList, resultList: int list list * int list list = loop (lists, []) 
    List.rev resultList 

// let test = []      // [] 
// let test = [[]]     // [ [ 555 ] ] 
// let test = [ [123] ]    // [ [ 555; 123 ] ] 
let test = [ [7]; []; [3;5] ] // [[555;7]; [555]; [555;3;5]] 
let prependedLists = prependToLists test 555 

Answer 2

let met_devant_et_acc h l = 
    let rec aux acc = function 
    | [] -> acc 
    | a::t -> aux ((h::a)::acc) t 
    in 
    aux [] (List.rev l) @ l 

或者

let met_devant_et_acc h l = 
    List.fold_left (fun acc a -> (h::a)::acc) [] (List.rev l) @ l 

測試：

# met_devant_et_acc 9 [ [1;2] ; [3;4] ];; 
- : int list list = [[9; 1; 2]; [9; 3; 4]; [1; 2]; [3; 4]] 
# met_devant_et_acc 9 [];; 
- : int list list = [] 
# met_devant_et_acc 9 [[]];; 
- : int list list = [[9]; []]