Hi Andrew,
| Hey all.. I was wondering if somebody might offer me some assistance in
| trying to debug some code I wrote to check whether a tree is a binary
| search tree.. For some reason it always comes back as false! :( Thanks
| much!
One of the great things about functional programming is the
opportunities that it brings to explore old problems from new
angles. The code that you wrote is an attempt to describe a
test for binary search trees as a recursive algorithm, which
is the kind of implementation that you'd expect to see in an
imperative language. As your experience has shown, this kind
of code can be hard to read, and hard to get right. I'd
encourage you to try a different approach. Consider the simple
question: When is a tree a binary search tree? Answer: When its
leaves are arranged in increasing order. Translating that idea
directly to Haskell gives:
isBST :: Ord a => Tree a -> Bool
isBST = increasing . leaves
where:
leaves :: Tree a -> [a]
increasing :: Ord a => [a] -> Bool
The idea here is that leaves and increasing are general purpose
functions that you can use to enumerate the leaves of a tree
from left to right, and to determine whether the values in a
list are increasing, respectively. I'll leave the definitions
to you, but it shouldn't be too difficult: a simple two line
recursive definition suffices for leaves, while a mildly cunning
one-liner will get you to increasing (hint: think zipWith (<=)).
The whole definition is shorter and (IMHO) simpler than the code
you wrote, while at the same time providing useful functions that
might find applications elsewhere in a larger program.
I hope that you'll find my comments here interesting. Perhaps I
should explain that I responded to your message because it reminded
me of some similar examples that got me excited when I was first
learning a functional programming language. I'd been an imperative
programmer for some time before then, but as I looked at those
examples, I began to see new ways of solving all kinds programming
problems. And, in fact, many of those ideas are still useful to me
today, whatever language I happen to be using.
Enjoy!
Mark
