替换列表元素是反模式吗? [英] Is replacing a list element an anti-pattern?

问题描述

我有一个模块，可以在以列表表示的路径上工作.大多数功能都执行典型的递归列表处理，但是现在我需要一个有时会改变路径的函数.所以，我写了这个replace函数:

I have a module that works on paths represented as lists. Most of the functions do typical recursive list processing, but now I need one that sometimes mutates a path. So, I wrote this replace function:

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]

通常，当我觉得有必要扩展内置模块时，我最终发现自己在做一些古怪或低效的事情.替换列表元素是其中之一吗?有没有更简单(同样有效)的方法来做到这一点?

Usually, when I feel the need to augment a built-in module I ultimately discover I'm doing something quirky or inefficient. Is replacing a list element one of those things? Is there a simpler (equally efficient) way to do this?

推荐答案

如果您的应用程序可接受O(N)复杂性，则您的代码是完美的.为了获得更好的复杂性，您可能需要解决线性搜索的需求，例如通过在元素上施加顺序并使用二进制搜索树.

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.

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

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.

这篇关于替换列表元素是反模式吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！