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

[Roelof Wobben]

Richard A. O'Keefe schreef op 2-3-2015 om 0:31:
> 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.
>
>

Thanks for the explanation.

Roelof