[Haskell-cafe] how to make this work recursive ?
Roelof Wobben
r.wobben at home.nl
Mon Mar 2 08:22:13 UTC 2015
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
More information about the Haskell-Cafe
mailing list