Replace element in discriminated union

Question

Is it possible to do a 'search and replace' on a discriminated union, for example replacing Foo with Bar with an instance of e.g.

type Expression
| Foo of Expression list
| Bar of Expression list

?

The highly nested definition of expressions can be of any depth.

Tomas Petricek Tomas Petricek · Accepted Answer · 2016-01-17T18:05:56

There is no built-in feature in the language that would let you do this automatically. The basic method is to write a recursive function - if you want to switch Foo for Bar, this is quite easy:

let rec switch = function
  | Foo es -> Bar(List.map switch es)
  | Bar es -> Foo(List.map switch es)

You could try to abstract the part that walks over the tree from the bit that specifies what should be transformed how. This doesn't really help with this simple problem, but it can be useful for more complex transformations.

For example, the following takes a function and calls it on all nodes. If the function returns Some, the node is replaced:

let rec transform f e = 
  match f e with
  | Some n -> n
  | None ->
      match e with
      | Foo es -> Foo(List.map (transform f) es)
      | Bar es -> Bar(List.map (transform f) es)

Now you can, for example, easily replace Bar [] with Foo [] and keep all other expressions unchanged:

Foo [ Bar []; Bar[] ] |> transform (fun e ->
  match e with
  | Bar [] -> Some(Foo [])
  | _ -> None)

Replace element in discriminated union

1 Answers