Fwd: [Haskell-cafe] Data.Tree.Zipper in the standard libraries

[Ian Lynagh]

On Wed, Jun 04, 2008 at 10:14:59AM -0700, Iavor Diatchki wrote:
> 
> extra functionality?  Especially, if---like in the case of
> Zipper---the implementation can be more or less computed from an
> existing definition in the package (I am referring to the fact that
> the zipper is the derivative of Tree, for details you can look at
> Conor's paper).

I've just skimmed http://citeseer.ist.psu.edu/472190.html
    The Derivative of a Regular Type is its Type of One-Hole Contexts
        (Extended Abstract) (2001)
    Conor McBride

Given the way people had been appealing to it, I has assumed that
datastructure derivatives were some general thing, but it looks like
they are actually just a way of describing a particular concrete
implementation of zippers. I'm not even sure how well the theoretical
connection applies to the variable branching degree of Data.Tree.

Also, it's actually the derivative of Forest, not Tree, right? Which is
why toTree can lose information, here the b and c trees:
    Data.Tree.Zipper> toTree (Loc (Node 'a' []) [Node 'b' []] [Node 'c' []] [])
    Node {rootLabel = 'a', subForest = []}
This feels a little scary to me.

Also, I think that technically it doesn't follow the paper, in that it
stores the parents in the reverse order.

That aside, the fact the datastructure is a derivative doesn't tell us
that it is efficient (in fact, it is more efficient because it /isn't/ a
straightforward derivative, but reverses the parent order as above),
that we have implemented the "right" methods to operate on it, that we
have chosen the "best" names for those methods, etc.

> - what makes code "proven"
>   Again, not sure how to define this.  The code for Zipper has QC
> tests that cover it 100%, according to HPC.

The question is more "is it the best interface" than "is the code
correct".

> Or are we going to
> require that it is already used by many people as a separate package,
> and then we are going to ask everyone to change their code, so that
> they can start using it from the new location?

The only change that should be needed is changing the Cabal dependencies
(and even that isn't strictly necessary, as you can make an empty zipper
package that depends on containers (>= n).

> But more to the point though, does anyone have any suggestions about
> what may be wrong with the Zipper concretely, rather then the library
> process in general?  Neil, the sniplet that you posted from the IRC
> channel does not give us an idea of what we might want to change.

Agreed: It sounds like people who have thought about this in the past
have found some design choices; it might be useful if they could explain
what they are.

> >> I would tend to agree with Neil that significant additions to the core
> >> libraries should be proven first as separate packages and integrated
> >> later.
> >
> > +1

I agree too - no matter how much you mark it experimental, people will
still complain loudly if you try to change the interface of a module in
the "standard" libraries.


Thanks
Ian