On 28/02/2015, at 9:40 pm, Roelof Wobben
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.