igloo:
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.
Quite so, the list derivative xmonad uses, for example, taken straight from the Huet paper, data Stack a = Stack { focus :: !a -- focused thing in this set , up :: [a] -- clowns to the left , down :: [a] } -- jokers to the right deriving (Show, Read, Eq) has an integration function, integrate :: Stack a -> [a] integrate (Stack x l r) = reverse l ++ x : r and, e.g. moving around the structure, focusUp (Stack t (l:ls) rs) = Stack l ls (t:rs) focusUp (Stack t [] rs) = Stack x xs [] where (x:xs) = reverse (t:rs) The structure of the type is derived, the implementation of the API is able to make further decisions appropriate to the representation. -- Don