将列表元素替换为反模式？

Question

我有一个模块适用于表示为列表的路径.大多数函数都执行典型的递归列表处理,但现在我需要一个有时会改变路径的函数.所以,我写了这个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]

通常,当我觉得需要增加一个内置模块时,我最终会发现我正在做一些古怪或低效的事情.将list元素替换为其中之一？有没有更简单(同样有效)的方法来做到这一点？

Answer 1

您可以使用以下方式编写它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

它稍微简单一些并且具有相似的性能（对列表元素的一个循环）。

Answer 2

如果O(N)您的应用程序可以接受复杂性,那么您的代码就完美了 为了更好的复杂性,您可能希望解决线性搜索的需要,例如对元素施加顺序和使用二叉搜索树.

不涉及搜索的相关问题是用已知索引替换list元素:

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

对于此问题,存在比标准列表更好的持久性数据结构.在文献中搜索纯功能随机访问列表.

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