[Haskell-cafe] how to make this work recursive ?

[Richard A. O'Keefe]

On 28/02/2015, at 9:40 pm, Roelof Wobben <r.wobben at home.nl> wrote:
> I found out that for 1 item I can do this : node = Node leaf "msg 1" leaf
> And for 2 items I can do this : node = Node leaf "msg1"  (Node leaf "msg2" leaf)

Your subject line says "how to make THIS work recursive(ly)" but the
body of your message does not explain what "this" is.

It looks as thought you have

data BinaryTree x
   = Leaf
   | Node (BinaryTree x) x (BinaryTree x)

except that you have written a variable name "leaf" instead of
a constant name "Leaf" (ok, there are no constant names, it's a constructor
name, but a constructor with no arguments is a constant).

> 
> But now I wonder how I can make this work with recursion.

Well, you have to START by saying clearly what "THIS" is.

It looks as though you want

empty :: BinaryTree x

insert :: Ord x => x -> BinaryTree x -> BinaryTree x

There's only one thing you can put for empty.  To make a Node
you would have to a value of type t, and you don't.  So

empty = Leaf

What about insert?
You have two arguments: an x (and all you know about x values is that
they can be compared) and a BinaryTree x.  It's going to have to be
a case analysis on the two possibilities for the BinaryTree:

insert v  Leaf              = Node Leaf v Leaf
insert v (Node lss elt gtr) = ??

Where are we doing to put v?  There are three places:
  lss (the set of things less than elt)
  elt (the value elt)
  gtr (the set of things greater than elt).
How can we tell where to put v?

Answer: by comparing v with elt:

  case compare v elt of
    LT -> "insert v in lss"
    GT -> "insert v in gtr"
    EQ -> "it's already in elt"

Convert the comments to Haskell, and we have

insert v Leaf = Node Leaf v Leaf
insert v (Node lss elt gtr) =
  case compare v elt of
    LT -> Node (insert v lss) elt gtr
    GT -> Node lss elt (insert v gtr)
    EQ -> Node lss elt gtr

We don't actually *MAKE* this function work recursively,
it just *happens* that to insert an element into a big
tree, we sometimes want to insert it into a subtree.

A first or second year data structure book would do this
in C:

typedef ???? elem;

typedef struct Node *tree;
typedef struct Node {
    tree lss;
    elem elt;
    tree gtr;
} Node;

tree insert(elem v, tree t) {
    if (t == 0) { /* leaf case */
        tree n = malloc(sizeof *n);
        if (n == 0) abort();
        n->lss = n->gtr = 0, n->elt = elt;
        return n;
    } else {
        if (v < t->elt) {
            t->lss = insert(v, t->lss);
        } else
        if (t->elt < v) {
            t->gtr = insert(v, t->gtr);
        }
        return t;
    }
}


> It seems that I keep the first 2 items and change the 3th one from leaf to another node

You DO NOT CHANGE ANYTHING.  Given a tree and a (possibly) new element,
you construct a NEW tree which shares most of its structure with the
old one.  In C, you have to destroy the old tree to make the new one.
In Haskell, you not only don't have to, you can't.

But the basic pattern:

   to insert v into t
      if t is empty
         return a new tree just containing v
      if t is not empty
         if v is less than the top element of t
            insert v into the left subtree of t
         if v is greater than the top element of t
            insert v into the right subtree of t
         if v is equal to the top element of t
            there is nothing to do

does not depend on which programming language you are using.

If you are alert, you will notice a strong similarity between
the structure of the DATA (a two-way choice where one choice
is simple and the other has three parts) and the structure of
the CODE (a two-way choice where one choice is simple and
the other has three parts).  This is not an accident.


>