Is replacing a list element an anti-pattern?

Question

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 ``` which works like this: ``` 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?

Accepted Answer

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.

Is replacing a list element an anti-pattern?

Solution

Problem