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]

通常，当我觉得需要扩充一个内置模块时，我最终会发现我在做一些古怪或低效的事情。替换列表元素是其中之一吗？有没有更简单（同样有效）的方法来做到这一点？

4

3 回答 3

7

如果O(N)您的应用程序可以接受复杂性，那么您的代码就是完美的。为了获得更好的复杂性，您需要解决进行线性搜索的需要，例如通过对元素施加顺序并使用二叉​​搜索树。

一个不涉及搜索的相关问题是用已知索引替换列表元素：

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

对于这个问题，存在比标准列表更好的持久数据结构。在文献中搜索纯功能随机访问列表。

奇怪的是，没有 ML 系列语言（OCaml、F#、SML）定义replace或replaceAt在标准列表库中。这可能是为了鼓励用户重新设计他们的代码以避免O(N)这些操作的复杂性。

于 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 回答