1

I am doing OCaml 99, and can't quite understand some terms in this problem.

A string representation of binary trees. (medium)

enter image description here

Somebody represents binary trees as strings of the following type (see example): "a(b(d,e),c(,f(g,)))".

  1. Write an OCaml function which generates this string representation, if the tree is given as usual (as Empty or Node(x,l,r) term).
  2. Then write a function which does this inverse; i.e. given the string representation, construct the tree in the usual form.
  3. Finally, combine the two predicates in a single function tree_string which can be used in both directions.
  4. Write the same predicate tree_string using difference lists and a single predicate tree_dlist which does the conversion between a tree and a difference list in both directions.

For simplicity, suppose the information in the nodes is a single letter and there are no spaces in the string.

Here are my questions:

  1. What does predicate mean in this problem?
  2. For the 3rd point, it asks to make a function which can be used in both directions, i.e., can accept a tree and output a string or accept a string and output a tree. Should I use functor or something like that?
  3. I totally can't understand the 4th point. What is difference lists?
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

1 Answers1

1

These problems were originally intended to be solved in Prolog, which explains the terminology I think.

In Prolog a predicate can represent an equality (or maybe isomorphism is a better word?) between two sorts of values, such that if you have a value of one sort it can actually calculate the value of the other sort. I.e., it works as a two-way function. It's not at all clear how to code this in OCaml. Maybe you should peek at the answers?

A difference list is a Prolog data structure. Here's a SO page that seems to explain them (I googled very quickly): Understanding difference lists (Prolog)

Community
  • 1
  • 1
Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108
  • Do you think there is a difference list in OCaml? or does it make sense or is useful in OCaml? – Jackson Tale Feb 25 '14 at 16:37
  • could you please also have a look at http://stackoverflow.com/questions/22020879/how-to-write-the-bnf-for-this-tree-related-operation? – Jackson Tale Feb 25 '14 at 21:44
  • I think you can have difference lists with Prolog's semantics using laziness (`lazy` in OCaml), but it is so tricky as not to be worth it. – lukstafi Mar 02 '14 at 02:53