我有一个适用于以列表表示的路径的模块。大多数函数都会执行典型的递归列表处理,但现在我需要一个有时会改变路径的函数。所以,我写了这个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]
通常,当我觉得需要增强内置模块时,我最终会发现我正在做一些奇怪或低效的事情。替换列表元素是其中之一吗?有没有更简单(同样有效)的方法来做到这一点?
If O(N)
您的应用程序的复杂性是可以接受的,您的代码是完美的。为了获得更好的复杂性,您可能希望解决线性搜索的需要,例如通过对元素施加顺序并使用二叉搜索树。
不涉及搜索的一个相关问题是用已知索引替换列表元素:
val replaceAt : int -> 'a -> 'a list -> 'a list
对于这个问题,存在比标准列表更好的持久数据结构。在文献中搜索纯功能随机访问列表。
奇怪的是,没有 ML 系列语言(OCaml、F#、SML)定义replace
or replaceAt
在标准列表库中。这可能是为了鼓励用户重新设计他们的代码以避免O(N)
这些操作的复杂性。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)