テール再帰的Ocamlプログラム

Question

私は関数met_devant_et_accをテール再帰的なものにしたいと思いますが、どのように書き直すことができるのか分かりません。 met_devant_et_acc l hはリストlのすべてのリストと要素hを持つこれらの同じリストをすべて含むリストを1番目の要素として返すものとします。

exは：met_devant h [ [ ]; ['x';'e']]戻り[ ['h'] ; ['h';'x';'e'] ]

がここのコードです：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

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

機能ajouteは、リストの先頭l

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

Answer 1

この関数に要素を追加するh 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]; []]