# Recursion and strong static typing can help you build functions!

There is a synergy between recursion and strong static typing that I never

realized and here it is:

If you express problem solution recursively, every choice made on every

branch of the recursion at any time in the problem space has to match

the type signature of the promised outcome.

Take this function to delete a node from a tree for example:

delete :: Ord a => a -> Tree a -> Tree a

So one thing we know for dead certain, is that delete will be returning a

Tree. So, if we code delete with a number of cases for different scenarios

each of those cases **must** return a tree.

Given this, one way to try to find the solution for this is take a look at

all the possible trees that you know about and ask when they would apply as

a solution. It kind of gets you going towards thinking about the mechanics

of the problem. First let's rewrite the type signature as the function head:

delete val (Node v t1 t2)

and now let's ask the pivotal question once again: "what sorts of trees can

I think of?" Well, we are looking at two of them in the second argument

to delete() - t1 and t2. When is t1 the solution to this problem? Well,

that's the same as asking when would we only return the left subtree after hitt\ing a node. And when would we do that? Well, the answer to that is:

"if val == v and there is no left subtree, then we

simply need to return t1." Nice! Codewise, it looks like this:

` (val == v) && (isNil t2) = t1`

Now of course we have the "mirror" situation

of when do we only return t2? And the answer is very similar to the other one:

` (val == v) && (isNil t1) = t2`

Ok, so we've nailed down two cases just by taking a look at the head

of the rule. So, let's see both of those cases had to do with being at a

node where val == v. The only difference was that the left or right subtree

was not there.

So obviously, we want to start thinking about when val == v and both

subtrees are there. Well in that case, we need to remove the root node and

join the 2 subtrees, maintaining the required binary tree ordering. So

that clause looks like this, assuming we use the fallback properties of

guards:

` otherwise = join t1 t2`

So we have thorougly cased out all of the scenarios where we have reached

the node of interest. What happens in the current node has a value greater

than the one we want to delete? Well, the node we are looking for must

exist down the left subtree:

` val < v = Node v (delete val t1) t2`

and conversely, if the current node's value is less than the one we are

looking for then we need to try to delete down the right subtree:

` val > v = Node v t1 (delete val t2)`

So now that we have cased all deletion scenarios out, we have our

final delete function:

```
```delete val (Node v t1 t2)

| val < v = Node v (delete val t1) t2

| val > v = Node v t1 (delete val t2)

| isNil t2 = t1

| isNil t1 = t2

| otherwise = join t1 t2

**conclusion**

SJT says that one should start with an informal description of a problem, then come up with your types. I add to that: once you get your types, then create type signatures for your functions and then once you get your type signatures, build the head of your function with pattern matching and then use the required types to express various cases.

- metaperl's blog
- Login to post comments

oblivion meridia

meridia com

pharmacy meridia