How to access ocaml datatype and modify value recursively?

Question

I'm learning Ocaml and quite lost how to deal with this.

Here is example.

let's say

type xml = Element of tag * xml list | CharData of string;;

and i want to access tag value and modify it.

The way i can think of is

match xml with 
    Element (tag, xlist) -> (* do something *) 
|   CharData str -> (* do something *)

I know this is not recursive syntax, but i want to know at least how to deal with this

Answer 1

Well first, what do you mean by "modify"? Is it okay to just return a new changed value, or do you actually have to mutate the original structure? Because in OCaml, the only things that are mutable are array elements, string elements, fields in records explicitly marked mutable (including the ref data structure), and fields in objects explicitly marked mutable.

Answer 2

If I understand your question, you can achieve what you want in two different ways.

You use a mutable data structure on your tag type, like the following example:

type tag = string ref;;
type xml = Element of tag * xml list | CharData of string;;

let xml_test = Element (ref "person",
   [CharData "text0";
    Element (ref "phoneNumber", [CharData "text2"]);
    CharData "text1";
    Element (ref "phoneNumber", [CharData "text3"])]);;

let modify_tag tag new_value=
    tag := new_value;;

let rec modify_and_print_xml xml =
    match xml with 
        Element (tag, xlist) -> modify_tag tag (!tag^"_modified");
                                print_string (!tag); print_newline ();

                                (*here you do the recursive call*)
                                List.iter (fun element -> modify_and_print_xml element) xlist

        |CharData str -> print_string str; print_newline ();;

modify_and_print_xml xml_test;;

Otherwise and since you are new to functional programming, the best way to think about it, is not to modify the tag value in place, but construct a new xml value that has the modified tag (this is what you should do to code purely functional and eliminate side effects).

Here is an example, say you want modify every tag named "phoneNumber" to "phone":

let rec get_modified_xml xml =
    match xml with
        Element (tag, xlist) -> if (!tag = "phoneNumber") then
                                    Element(ref "phone", List.map (fun element -> get_modified_xml element) xlist)
                                else
                                    Element (tag, List.map (fun element -> get_modified_xml element) xlist)
        | _ -> xml;;


get_modified_xml xml_test;;

output :

- : xml =
Element ({contents = "person"},
 [CharData "text0"; Element ({contents = "phone"}, [CharData "text2"]);
  CharData "text1"; Element ({contents = "phone"}, [CharData "text3"])])

Answer 3

I think you are using the word modify loosely here --and it's no fault against you. I doubt anyone in there right mind is going to use references in their recursive data structure; and being new, it's hard for me to justify that you mean it literally as such.

There is a difference because in functional languages we normally deal with immutable data structures. What I think you mean to ask, is how to return a new structure with a specified tag replaced by another. Pedantry aside, it is a very natural thing to do in functional languages, and it will be something you will only consider rarely.

Lets completely define the structure that you are working with. I additionally defined tag --I assume it's a string.

type tag = string
type xml = Element of tag * xml list | CharData of string;;

And the signature for the function (so we are clear on what we are trying to accomplish),

val replace_tag : string -> string -> xml -> xml

let rec replace_tag from_tag to_tag = function
    (* nothing to do here... *)
    | (CharData _ ) as x -> x
    (* an element with the proper tag; call function on its contents *)
    | Element (tag, xmlist) when tag = tag_from ->
        let xmlist = List.map (fun t -> replace_tag from_tag to_tag t) xmlist in
        let ntag,ncontent = f tag xmlist in
        Element (tag_to,xmlist)
    (* look into each element of xml contents *)
    | Element (tag, xmlist) ->
        let xmlist = List.map (fun t -> replace_tag from_tag to_tag t) xmlist in
        Element(tag,xmlist)

This is a decent, simple solution to what I think your problem is. There are a number of problems with this though; it doesn't do error checking if the value doesn't exist and it will copy the whole data structure each time --due to the List.map call. With some more details I think we can provide you with a better solution.