13

リストとして表されるパスで動作するモジュールがあります。ほとんどの関数は一般的な再帰リスト処理を実行しますが、パスを変更することがある関数が必要になりました。だから、私はこのreplace関数を書きました：

module List =
  let replace f sub xs = 
    let rec finish acc = function
      | [] -> acc
      | x::xs -> finish (x::acc) xs
    let rec search acc = function
      | [] -> None
      | x::xs -> 
        if f x then Some(finish ((sub x)::xs) acc)
        else search (x::acc) xs
    search [] xs

これは次のように機能します：

let xs = List.init 10 id
let res = List.replace ((=) 5) (fun _ -> -1) xs
//Some [0; 1; 2; 3; 4; -1; 6; 7; 8; 9]

通常、組み込みモジュールを拡張する必要があると感じたとき、私は最終的に、奇妙なことや非効率的なことをしていることに気付きます。リスト要素を置き換えることはそれらの1つですか？これを行うためのより簡単な（同等に効率的な）方法はありますか？

4

3 に答える 3

7

If O(N) complexity is acceptable for your application, your code is perfect. For better complexity you would want to work around the need to do linear search, for example by imposing order on the elements and using binary search trees.

A related problem not involving search is replacing a list element with a known index:

val replaceAt : int -> 'a -> 'a list -> 'a list

For this problem, better persistent data structures exist than the standard list. Search for purely-functional random-access lists in the literature.

Curiously, no ML-family language (OCaml, F#, SML) defines replace or replaceAt in the standard list library. This is probably meant to encourage users to redesign their code to avoid the O(N) complexity of these operations.

于 2012-07-14T21:29:40.240 に答える
5

あなたはそれを使用して書くことができますList.fold：

let replace f sub xs = 
  let processItem (found,list) x =
    if found then (true,x::list) 
    elif f x then (true,(sub x)::list) 
    else (false,x::list)
  let (found, list) = xs |> List.fold processItem (false,[])
  if found then Some(List.rev list)
  else None

これは少し単純で、同様のパフォーマンスを備えています（リストの要素に対する単一のループ）。

于 2012-07-12T15:55:30.183 に答える
2 
let replace pf el xs =
  let c = ref 0
  let xs = List.map (fun x -> if pf x then incr c;el else x) xs
  if !c = 0 then None else Some xs

(*
> replace ((=)5) -1 [0..9];;
val it : int list option = Some [0; 1; 2; 3; 4; -1; 6; 7; 8; 9]
> replace ((=)10) -1 [0..9];;
val it : int list option = None
*)

アップデート

let replace pf sf xs =
  let find = ref false
  let rec aux = function
    | [] -> []
    | x::xs -> if pf x then find := true;(sf x) :: xs else x :: (aux xs)
  let xs = aux xs
  if !find then Some xs else None
(*
> let xs = [0..9];;
val xs : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
> let subf = fun _ -> -1;;
val subf : 'a -> int

> replace ((=) 5) subf xs;;
val it : int list option = Some [0; 1; 2; 3; 4; -1; 6; 7; 8; 9]
> replace ((<) 5) subf xs;;
val it : int list option = Some [0; 1; 2; 3; 4; 5; -1; 7; 8; 9]
> replace ((=) 50) subf xs;;
val it : int list option = None
*)
于 2012-07-12T23:47:33.670 に答える