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?

Answer 1

You can write it using 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

It is slightly simpler and with similar performance (one single loop over the elements of the list).

Answer 2

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.

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