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.