Is replacing a list item with an anti-pattern?

Question

I have a module that works with paths presented as lists. Most functions do the typical processing of a recursive list, but now I need one that sometimes mutates the 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 fx then Some(finish ((sub x)::xs) acc) else search (x::acc) xs search [] xs 

which works as follows:

 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 expand the built-in module, I eventually find that I am doing something fancy or ineffective. Is replacing a list item with one of these things? Is there an easier (equally effective) way to do this?

Answer 1

If O(N) complexity is acceptable for your application, your code is perfect. For better complexity, you will need to solve the linear search problem, for example, by putting order on the elements and using binary search trees.

A related non-search issue replaces the list item with a known index:

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

There are more robust data structures for this problem than a standard list. Search for purely functional random access lists in the literature.

Interestingly, not a single language in the ML family (OCaml, F #, SML) defines replace or replaceAt in the standard list library. This probably means that users should redesign their code to avoid O(N) complexity of these operations.

Answer 2

You can write it using List.fold :

 let replace f sub xs = let processItem (found,list) x = if found then (true,x::list) elif fx 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 

This is a bit simpler and with similar performance (one cycle on list items).

Answer 3

 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 *) 

UPDATE

 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 *)