Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Hi again, I was silent for some time but in this time I created QuickCheck tests for Data.Tree.Zipper which achieve 100% coverage with HPC. I also created a ticket for it: Ticket #2324 http://hackage.haskell.org/trac/ghc/ticket/2324 The attached file is the current implementation and it contains the version updated from Iavor Diatchki. It has the advantage that it also works with forests, not just with trees. Initially I thought that complete testsuite for such a simple module might be overkill but actually I found a bug :-) in the splitChildren function which is now fixed. The dead line for further considerations is one week. Regards, Krasimir On Sun, May 25, 2008 at 1:09 AM, Iavor Diatchki [EMAIL PROTECTED] wrote: Hello, I think that the modified API (no state monad, and using Maybe) is quite nice! I implemented a version of the the suggested API using a slightly different data structure, which makes the code a bit simpler, I think. I put the code in the Haskell wiki: http://www.haskell.org/sitewiki/images/2/2d/RoseZipper.hs I also added a couple of extra functions that seemed useful, and renamed a few of the functions to be more consistent. As for how to distribute the code, it seems that Zipper should live in the same place as Data.Tree. I think that Data.Tree is part of the containers package, so it would make sense to add the Zipper there as well. -Iavor On Sat, May 24, 2008 at 1:24 AM, Neil Mitchell [EMAIL PROTECTED] wrote: Hi, It doesn't use State monad anymore and it returns Maybe. This seems to be the common preference, is it? Feel free to vote against. Should we change Data.Map also? There is another proposal for changes in findMin/findMax so it is better to make this two breaking changes together rather than in a later release. The standard libraries proposal thingy is to go via the libraries list, create tickets etc. What reason is there to make this part of the base libraries, rather than a separate package on hackage? I can't see much reason to make Data.Tree part of the base libraries, other than the fact it already is, and it could easily get moved out at a future date. We've seen there is some advantage in leaving the implementation outside the base library, as its already changed several times in the past few days. Thnanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Hello, I think that the modified API (no state monad, and using Maybe) is quite nice! I implemented a version of the the suggested API using a slightly different data structure, which makes the code a bit simpler, I think. I put the code in the Haskell wiki: http://www.haskell.org/sitewiki/images/2/2d/RoseZipper.hs I also added a couple of extra functions that seemed useful, and renamed a few of the functions to be more consistent. As for how to distribute the code, it seems that Zipper should live in the same place as Data.Tree. I think that Data.Tree is part of the containers package, so it would make sense to add the Zipper there as well. -Iavor On Sat, May 24, 2008 at 1:24 AM, Neil Mitchell [EMAIL PROTECTED] wrote: Hi, It doesn't use State monad anymore and it returns Maybe. This seems to be the common preference, is it? Feel free to vote against. Should we change Data.Map also? There is another proposal for changes in findMin/findMax so it is better to make this two breaking changes together rather than in a later release. The standard libraries proposal thingy is to go via the libraries list, create tickets etc. What reason is there to make this part of the base libraries, rather than a separate package on hackage? I can't see much reason to make Data.Tree part of the base libraries, other than the fact it already is, and it could easily get moved out at a future date. We've seen there is some advantage in leaving the implementation outside the base library, as its already changed several times in the past few days. Thnanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Aha. I see the point. The current design was influenced from some other implementation that I spot somewhere in the net. I will change it but this reminds me of another problem. Most movement functions raise error if they can't do the movement. This is convenient if you somehow know that the direction in which you go always exists. Alternatively I can use monad with failure. In other words, there are two possibilities: 1. Use error .. and types like: TreeLoc a - TreeLoc a 2. Use monad and type like: Monad m = TreeLoc a - m (TreeLoc a) In the second case some one have to do something like this to check whether the operation is successful: case left loc of Noting - error something gone wrong Just loc - ... In the first case there is no way to check for success but someone can use precondition: if isFirst loc then do_something (left loc) else i_cannot_go_left In my opinion 1 looks nicer but 2 also have advantages. What do you think? Regards, Krasimir On Fri, May 23, 2008 at 12:33 AM, Conal Elliott [EMAIL PROTECTED] wrote: * Every definition of tp I meant of type, forgetting that my emacs abbrevs don't expand in gmail. On Thu, May 22, 2008 at 2:13 PM, Conal Elliott [EMAIL PROTECTED] wrote: Hi Krasimir, I had a long exchange with chessguy about this interface, suggesting a significant change in style, simplifying the type. (Incidentally, the change removed the State and hence mtl dependence.) The conversation is on http://tunes.org/~nef/logs/haskell/08.05.17, starting with 12:08:11 chessguy w00t! and really picking up with conal chessguy: something smells funny Here's a summary of the conversation, though I encourage you to read the whole thing: * Every definition of tp 'State (TreeLoc a) a', does a getLabel at the end (except getLabel). * Often users of those movement functions discard the result. * Simpler and more orthogonal would be remove the getLabel and return 'State (TreeLoc a) ()' instead. * Now remove that return value altogether, simplifying the type of zipper movements to just 'TreeLoc a - TreeLoc a'. Then they compose nicely with (.), having id as identity. * Simplify the type of getLabel to just 'TreeLoc a - a'. Now no more State. Cheers, - Conal On Thu, May 22, 2008 at 12:52 PM, Krasimir Angelov [EMAIL PROTECTED] wrote: Hello Guys, We have Data.Tree in the standard libraries for a long time but for some reason we still don't have standard implementation for Zipper. I wrote recently one implementation for Yi but there are many other versions hanging around. At least I know for some. I propose to add one in the standard libraries i.e. the containers package. The version that I use currently is here: http://code.haskell.org/yi/Data/Tree/Zipper.hs If you would like to do code review I will be happy to hear comments. After the API is settled down I will write test cases also. One thing that is worying me is that the current version uses State monad which is in the mtl package while the natural place for Data.Tree.Zipper is in containers. This will create an extra dependency. Is this acceptable? Regards, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Krasimir Angelov wrote: The monads design is used in Data.Map i.e. lookup :: (Monad m, Ord k) = k - Map k a - m a which is widely considered a poor design decision and a wart on Data.Map. :-) Seriously, if you don't return a useful error message, then Maybe is as good as it gets, why not use it? (And there really is only one kind of error possible here, in each case) 'fail' only adds information in the case it has a useful error message (in which case I'd encourage MonadError m =) Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
I think that MonadZero m = ... is better than just Maybe. If you can have more general solution for free, why fight it? On 23 May 2008, at 14:55, Jules Bean wrote: Krasimir Angelov wrote: The monads design is used in Data.Map i.e. lookup :: (Monad m, Ord k) = k - Map k a - m a which is widely considered a poor design decision and a wart on Data.Map. :-) Seriously, if you don't return a useful error message, then Maybe is as good as it gets, why not use it? (And there really is only one kind of error possible here, in each case) 'fail' only adds information in the case it has a useful error message (in which case I'd encourage MonadError m =) Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
On Fri, May 23, 2008 at 10:55 AM, Jules Bean [EMAIL PROTECTED] wrote: Krasimir Angelov wrote: The monads design is used in Data.Map i.e. lookup :: (Monad m, Ord k) = k - Map k a - m a which is widely considered a poor design decision and a wart on Data.Map. It is? Can you point to somewhere explaining that? I rather liked that idiom. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
On 2008 May 23, at 13:34, Luke Palmer wrote: On Fri, May 23, 2008 at 10:55 AM, Jules Bean [EMAIL PROTECTED] wrote: Krasimir Angelov wrote: The monads design is used in Data.Map i.e. lookup :: (Monad m, Ord k) = k - Map k a - m a which is widely considered a poor design decision and a wart on Data.Map. It is? Can you point to somewhere explaining that? I rather liked that idiom. I'd argue that the poor design decision was killing MonadZero, and the type of Data.Map.lookup is a hackaround. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Using 'monad' here makes it easier to make a mistake with the code, as it permits new kinds of unexpected failure. This is Haskell, we should use Maybe. And users that want it can lift Maybe a - m a -- Don (-1) for new uses of fail in place of Nothing. kr.angelov: The monads design is used in Data.Map i.e. lookup :: (Monad m, Ord k) = k - Map k a - m a and I think that this will be more consistent. On 5/23/08, Ross Paterson [EMAIL PROTECTED] wrote: On Fri, May 23, 2008 at 09:03:29AM +0200, Krasimir Angelov wrote: Alternatively I can use monad with failure. In other words, there are two possibilities: 1. Use error .. and types like: TreeLoc a - TreeLoc a 2. Use monad and type like: Monad m = TreeLoc a - m (TreeLoc a) I'd suggest that TreeLoc a - Maybe (TreeLoc a) is better than the second version. The problem with using Monad(fail) is that it hides possible runtime errors among testable conditions. With 1. you can at least search the code for occurrences of the dangerous function. With the Monad version you need to consider the type of each use to know whether it is dangerous. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Data.Tree.Zipper in the standard libraries
Hello Guys, We have Data.Tree in the standard libraries for a long time but for some reason we still don't have standard implementation for Zipper. I wrote recently one implementation for Yi but there are many other versions hanging around. At least I know for some. I propose to add one in the standard libraries i.e. the containers package. The version that I use currently is here: http://code.haskell.org/yi/Data/Tree/Zipper.hs If you would like to do code review I will be happy to hear comments. After the API is settled down I will write test cases also. One thing that is worying me is that the current version uses State monad which is in the mtl package while the natural place for Data.Tree.Zipper is in containers. This will create an extra dependency. Is this acceptable? Regards, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
Hi Krasimir, I had a long exchange with chessguy about this interface, suggesting a significant change in style, simplifying the type. (Incidentally, the change removed the State and hence mtl dependence.) The conversation is on http://tunes.org/~nef/logs/haskell/08.05.17, starting with 12:08:11 chessguy w00t! and really picking up with conal chessguy: something smells funny Here's a summary of the conversation, though I encourage you to read the whole thing: * Every definition of tp 'State (TreeLoc a) a', does a getLabel at the end (except getLabel). * Often users of those movement functions discard the result. * Simpler and more orthogonal would be remove the getLabel and return 'State (TreeLoc a) ()' instead. * Now remove that return value altogether, simplifying the type of zipper movements to just 'TreeLoc a - TreeLoc a'. Then they compose nicely with (.), having id as identity. * Simplify the type of getLabel to just 'TreeLoc a - a'. Now no more State. Cheers, - Conal On Thu, May 22, 2008 at 12:52 PM, Krasimir Angelov [EMAIL PROTECTED] wrote: Hello Guys, We have Data.Tree in the standard libraries for a long time but for some reason we still don't have standard implementation for Zipper. I wrote recently one implementation for Yi but there are many other versions hanging around. At least I know for some. I propose to add one in the standard libraries i.e. the containers package. The version that I use currently is here: http://code.haskell.org/yi/Data/Tree/Zipper.hs If you would like to do code review I will be happy to hear comments. After the API is settled down I will write test cases also. One thing that is worying me is that the current version uses State monad which is in the mtl package while the natural place for Data.Tree.Zipper is in containers. This will create an extra dependency. Is this acceptable? Regards, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Tree.Zipper in the standard libraries
* Every definition of tp I meant of type, forgetting that my emacs abbrevs don't expand in gmail. On Thu, May 22, 2008 at 2:13 PM, Conal Elliott [EMAIL PROTECTED] wrote: Hi Krasimir, I had a long exchange with chessguy about this interface, suggesting a significant change in style, simplifying the type. (Incidentally, the change removed the State and hence mtl dependence.) The conversation is on http://tunes.org/~nef/logs/haskell/08.05.17http://tunes.org/%7Enef/logs/haskell/08.05.17, starting with 12:08:11 chessguy w00t! and really picking up with conal chessguy: something smells funny Here's a summary of the conversation, though I encourage you to read the whole thing: * Every definition of tp 'State (TreeLoc a) a', does a getLabel at the end (except getLabel). * Often users of those movement functions discard the result. * Simpler and more orthogonal would be remove the getLabel and return 'State (TreeLoc a) ()' instead. * Now remove that return value altogether, simplifying the type of zipper movements to just 'TreeLoc a - TreeLoc a'. Then they compose nicely with (.), having id as identity. * Simplify the type of getLabel to just 'TreeLoc a - a'. Now no more State. Cheers, - Conal On Thu, May 22, 2008 at 12:52 PM, Krasimir Angelov [EMAIL PROTECTED] wrote: Hello Guys, We have Data.Tree in the standard libraries for a long time but for some reason we still don't have standard implementation for Zipper. I wrote recently one implementation for Yi but there are many other versions hanging around. At least I know for some. I propose to add one in the standard libraries i.e. the containers package. The version that I use currently is here: http://code.haskell.org/yi/Data/Tree/Zipper.hs If you would like to do code review I will be happy to hear comments. After the API is settled down I will write test cases also. One thing that is worying me is that the current version uses State monad which is in the mtl package while the natural place for Data.Tree.Zipper is in containers. This will create an extra dependency. Is this acceptable? Regards, Krasimir ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
