Re: Binary search tree
Hi everybody, I studied haskell this semester at the university and I was required to implement a binary search tree in haskell. I would appreciate if anyone could send me an example code of this data structure. Just read a standard textbook. Some useful course notes by Jeroen Fokker are available online at http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Enough to solve your problem. Rijk-Jan van Haaften ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Binary Search Tree debugging
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
Re: Binary Search Tree debugging
Mon, 17 Apr 2000 14:47:49 -0400 (EDT), Sitzman [EMAIL PROTECTED] pisze:
| otherwise = False
2
/ should be a BST too.
1
checkL = ((treeVal (leftSub thetree)) (treeVal (thetree)))
checkR = ((treeVal (rightSub thetree)) (treeVal (thetree)))
It's not enough:
3
/ \
2 5
/ \
1 4
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://qrczak.ids.net.pl/
\__/ GCS/M d- s+:-- a23 C+++$ UL++$ P+++ L++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Binary Search Tree debugging
Assuming this isn't a homework exercise... 1) If current node is empty then this portion of tree is a BST 2) if the left subtree and right subtree's are both not empty then ... The logical negation of your second clause (which is what is picked up by the 'otherwise' clause of your code) is that if _either_ subtree is empty, then this portion of the tree is _not_ a BST. (In other words, it negates the effect of the first clause.) So all non-Nil trees will yield False, since everything immediately above a Nil node is not a BST. You probably want to change the condition thus: isBST thetree | isNil thetree = True | (isBST (leftSub thetree)) (isBST (rightSub thetree) = checkL checkR | otherwise = False Regards, Malcolm
Re: binary search
On Fri 17 Apr, Dave Tweed wrote: On Thu, 16 Apr 1998, S. Alexander Jacobson wrote: All that being said, we can say that there are certain properties that all haskell functions must fulfill. For example a recursive function should never call itself with the arguments that it recieved. e.g. myFunction 2 3 should not make a recursive call to myFunction 2 3 You can't even say that, since things like cycle :: [a] - [a] cycle xs = xs ++ cycle xs are very useful in a lazy functional language since only the portion of the list that is actually used in the computation will be constructed. (eg take 20 (cycle " ") to get a string of 20 spaces.) So you could say `a recursive function should not call itself on the right-hand side with exactly the same arguments on the left hand side as the argument of an operator/function is strict', But surely in this instance (and just about every other similar example I can think of) it would be better to write something like.. cycle xs = let circle = xs ++ circle in circle ..thereby creating a cyclic data structure instead of a truely infinite one. Can anybody give me an example where you couldn't use this trick? If not, I think I must agree with S. Alexander Jacobson Regards -- Adrian Hey
Re: binary search
On Thu, 16 Apr 1998, S. Alexander Jacobson wrote: All that being said, we can say that there are certain properties that all haskell functions must fulfill. For example a recursive function should never call itself with the arguments that it recieved. e.g. myFunction 2 3 should not make a recursive call to myFunction 2 3 You can't even say that, since things like cycle :: [a] - [a] cycle xs = xs ++ cycle xs are very useful in a lazy functional language since only the portion of the list that is actually used in the computation will be constructed. (eg take 20 (cycle " ") to get a string of 20 spaces.) So you could say `a recursive function should not call itself on the right-hand side with exactly the same arguments on the left hand side as the argument of an operator/function is strict', eg, not f x y = 1 + f x y because + is strict in its right argument ( its left but that's not relevant) but whether or not a function is strict in one argument may depend on the others and is undecidable in general. (I admit I can't think of a convincing example of the top of my head.) It would be really useful if a debugger/interpreter could detect when this type of error happens and generates an error message documenting the location of such an infinite loop call. What would be very useful would be just a tally of how many times a function f is called with the same arguments when a program being debugged looping is aborted, on the grounds that things like cycle should be dwarfed by the real cause of the infinite loop. cheers, dave - email: [EMAIL PROTECTED] One of the endearing things about www.cs.bris.ac.uk/~tweed/pi.htm mathematicians is the extent to which work tel: (0117) 9545104they will go to avoid doing any real work
Re: binary search
Not to reject assertions (they would be welcome), but I think that you need something slightly different in a functional programming language. Assertions in procedural languages typically define system state before and after a particular function gets executed. State assertions are less appropriate to functional programming languages (except in the context of the content of monads but that is a separate issue). As I understand it, Haskell programmers should use the type system to prevent functions from getting called w/ operands outside their domain. For example, a very careful programmer would specify that division is only allowed on a type that has already filtered out 0 e.g. newType NonZero :: MakeNonZero Num toNonZero:: Num - NonZero toNonZero x | x==0 = error "Shouldn't be zero" | otherwise = MakeNonZero x Using the type system is often entirely impractical, because the things you want to check may not be statically checkable, at least not within the computational language the type system provides. Inside GHC we make extensive use of assertions. In the example you give we might say divide :: Int - Int - Int divide a b = ASSERT( b /= 0 ) a/b The ASSERT expands to if not (b /= 0) then error "Assertion failed on line 27 of Foo.hs" else a/b In Haskell 2 I think assertions will be standard. (So far we have used the C preprocessor to add them, but they should jolly well be in the language.) It's *very* important to be able to turn all assertion-checking off, easily. Then programmers will write expensive assertion checks ASSERT( length xs 100 ) ASSERT( isBalanced tree ) which they would never write if they thought these checks formed a permanent part of their code. In our experience assertions are quite a potent debugging tool. Note that they can check post-conditions as well as pre-conditions: f x y = ASSERT( pre x y post x y r ) r where r = ...body of f... Simon
Re: binary search
Various people write: Cc: [EMAIL PROTECTED], [EMAIL PROTECTED] Can I ask people to be careful to which haskell-list address(es) they followup to? My understanding is that list messages ought to be sent _only_ to [EMAIL PROTECTED], and that any other addresses are symptoms (and in some cases causes) of list-mailer flakiness. (Not to mention likely to make my mail-filter go berserk, to inject a selfish note.) Slainte, Alex.
Re: binary search
2. how would I have found/fixed such an error in a more complex function w/o assertions and w/o print statements? Good questions There was a proposal to put assertions into Std Haskell, which we have implemented in GHC. (I'm not sure we've yet put that version out though.) So assertions are definitely coming. You are right that they are important. Finding infinite loops in functional programs is quite hard. Colin Runciman and Jan Sparud have been working on "redex trails". We plan to help at least identify where the loop is by putting out cost-centre-stack information... but that's still in the works. Simon
Re: binary search
On Thu, 16 Apr 1998, Simon L Peyton Jones wrote: 2. how would I have found/fixed such an error in a more complex function w/o assertions and w/o print statements? Good questions There was a proposal to put assertions into Std Haskell, which we have implemented in GHC. (I'm not sure we've yet put that version out though.) So assertions are definitely coming. You are right that they are important. Not to reject assertions (they would be welcome), but I think that you need something slightly different in a functional programming language. Assertions in procedural languages typically define system state before and after a particular function gets executed. State assertions are less appropriate to functional programming languages (except in the context of the content of monads but that is a separate issue). As I understand it, Haskell programmers should use the type system to prevent functions from getting called w/ operands outside their domain. For example, a very careful programmer would specify that division is only allowed on a type that has already filtered out 0 e.g. newType NonZero :: MakeNonZero Num toNonZero:: Num - NonZero toNonZero x | x==0 = error "Shouldn't be zero" | otherwise = MakeNonZero x Another application of assertions is documenting and formalizing the spec for functions. In this context assertions may provide a way of documenting code with a proof-of-correctness but this is of limited utility. In many contexts the risk that the spec is incorrect substantially outweighs the risk that the code is incorrect (and even more so in a functional programming language). All that being said, we can say that there are certain properties that all haskell functions must fulfill. For example a recursive function should never call itself with the arguments that it recieved. e.g. myFunction 2 3 should not make a recursive call to myFunction 2 3 It would be really useful if a debugger/interpreter could detect when this type of error happens and generates an error message documenting the location of such an infinite loop call. A more sophisticated version would detect more complex repeat patterns and output those. A lesser version would be some way to assert that a recursive function call really does reduce based on the definition of reduce for the particular function, but that imposes more work on the programmer. (Eiffel does this) Finding infinite loops in functional programs is quite hard. Colin Runciman and Jan Sparud have been working on "redex trails". We plan to help at least identify where the loop is by putting out cost-centre-stack information... but that's still in the works. Of course it would be much nicer if the compiler rejected all functions for which it could not prove that there was no way for the function to enter an infinite loop, but I don't know enough theory to know whether that is possible. I take your paragraph to mean that it is not impossible but it is hard. So to bring this back to my original question, I am trying to figure out how to think about debuging Haskell code. At least for me, the application of assertions to Haskell programming is non-intuitive. If you could explain how you expect people to use assertions in day-to-day functional programming/scripting to write better code, that would be really helpful. -Alex- ___ S. Alexander Jacobson i2x Media 1-212-697-0184 voice1-212-697-1427 fax
