Re: [Haskell] ANN: Uniplate 1.0
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Neil Mitchell wrote:
Hi,
I am pleased to announce Uniplate (formerly known as Play), a library for boilerplate removal requiring only Haskell 98 (for normal use) and optionally multi-parameter type classes (for more advanced features). This library has been tested with Yhc, Hugs and GHC.
The Uniplate library can do some of the same things as Scrap Your Boilerplate (SYB), and has functions that can be used in a similar manner to everywhere and everything.
LINKS
Project home page: http://www-users.cs.york.ac.uk/~ndm/uniplate/ Hackage release: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uniplate-1.0 Haddock docs: http://www.cs.york.ac.uk/fp/haddock/uniplate/ Short Manual: http://www.cs.york.ac.uk/fp/darcs/uniplate/uniplate.htm Draft Paper: http://www-users.cs.york.ac.uk/~ndm/downloads/draft-uniplate-15_jun_2007.pdf
The manual contains a basic overview of some bits of the library, the paper goes into more detail, but is intended to still be a readable introduction to the library.
The draft paper feels more readable and up-to-date than the manual. However I have one comment about it. In the section on DERIVE for Uniplate instances, the type appearing directly in one of its own constructors is demonstrated being recognized, as is the type appearing in a list in one of its own constructors. But no mention is made of just what powers the deriving has. I presume lists are a special case (how else would it be possible), but a naive reading gives no particular reason to suspect that the type in a Data.Map or Data.Set or any other collection, in one of its own constructors, would not be allowed. Also is there any restriction on the placement of lists in the constructor? I can't see how data Foo = CFoo Foo [Foo] Foo [Foo] Foo could be translated. Does putting the list somewhere other than last work? Isaac -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGdyHsHgcxvIWYTTURAiWuAKCUKf7aGf1rO58gcgxYkqbO7oKNCwCfTRpo 0UsQHx9riP+cZ/S/gloAy3g= =cAxY -----END PGP SIGNATURE-----
Hi
The draft paper feels more readable and up-to-date than the manual.
That's very true! Originally there was a manual, now there is a paper - perhaps I should take the manual down if people think that the paper is sufficiently readable?
However I have one comment about it. In the section on DERIVE for Uniplate instances, the type appearing directly in one of its own constructors is demonstrated being recognized, as is the type appearing in a list in one of its own constructors. But no mention is made of just what powers the deriving has.
The scheme outlined in the paper is very powerful - it will work for all data structures which don't contain a forall in the declaration. It can only derive instances for entirely concrete data types, i.e. you can't write an instance Maybe x, but you can write one instance Maybe Bool. (PlateData/PlateTypeable do not have this restriction).
I presume lists are a special case (how else would it be possible),
For the implementation, Data.Derive has a special case for lists, tuples and Maybe. Its a shame that only a restricted number of types are supported - things like Data.Map/Data.Set can be supported perfectly, apart from restrictions in Template Haskell. At derivation time, if Data.Derive comes across Data.Set it cannot get at Data.Set's internal structure, so it can't figure out how the instance should look. This means that the number of data types within the constructor is fixed, but can be easily extended. I'm currently deciding what to do about this. One option is to look at using SYB's reflection capabilities which do allow this, and saving the result as an instance. Another option is to add special cases for many more data types (Set/Map are both candidates). Perhaps template haskell can even be persuaded to do some of what I want - I'm still learning its power.
Also is there any restriction on the placement of lists in the constructor? I can't see how data Foo = CFoo Foo [Foo] Foo [Foo] Foo could be translated. Does putting the list somewhere other than last work?
The list can come anywhere. Consider the simplest example: data Foo = CFoo [Foo] [Foo] The instance would have the same effect as: instance Uniplate Foo where uniplate (CFoo x y) = (x ++ y, \z -> let (x2,y2) = splitAt (length x) z in CFoo x2 y2) (the actual instance would be a continuation passing variant of this, and be more efficient, but still have the same meaning) The key observation is that the length of the x field before and after is the same, so the multiple lists can be split back into their original sizes. Thanks Neil
Hi Thinking about this slightly further...
For the implementation, Data.Derive has a special case for lists, tuples and Maybe. Its a shame that only a restricted number of types are supported - things like Data.Map/Data.Set can be supported perfectly, apart from restrictions in Template Haskell.
There are two cases. 1) The data structure contains values, in specific places. Lists, tuples, Either etc. are all like this. The rules in the paper cover all these situations. 2) The data structure contains values, but their place is a feature of the data structure - i.e. Map/Set. In this case the right thing to do is probably to do fromList/toList pairs on them. I'll modify the derive tool to take this into account. I've never seen any comments on the effect of using SYB with data structures containing invariants such as Map's. I guess SYB can break these invariants quite easily, so should be used with care in some places. Thanks Neil
On Tue, Jun 19, 2007 at 03:11:44AM +0100, Neil Mitchell wrote:
Hi
Thinking about this slightly further...
For the implementation, Data.Derive has a special case for lists, tuples and Maybe. Its a shame that only a restricted number of types are supported - things like Data.Map/Data.Set can be supported perfectly, apart from restrictions in Template Haskell.
There are two cases.
1) The data structure contains values, in specific places. Lists, tuples, Either etc. are all like this. The rules in the paper cover all these situations.
2) The data structure contains values, but their place is a feature of the data structure - i.e. Map/Set. In this case the right thing to do is probably to do fromList/toList pairs on them.
I'll modify the derive tool to take this into account. I've never seen any comments on the effect of using SYB with data structures containing invariants such as Map's. I guess SYB can break these invariants quite easily, so should be used with care in some places.
No, it can't be used on Map etc in any reasonable way. You can't break the invariants because you can't do much of anything: -- This instance preserves data abstraction at the cost of inefficiency. -- We omit reflection services for the sake of data abstraction. instance (Data k, Data a, Ord k) => Data (Map k a) where gfoldl f z map = z fromList `f` (toList map) toConstr _ = error "toConstr" gunfold _ _ = error "gunfold" dataTypeOf _ = mkNorepType "Data.Map.Map" dataCast2 f = gcast2 f Stefan
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Neil Mitchell wrote:
Hi
Thinking about this slightly further...
For the implementation, Data.Derive has a special case for lists, tuples and Maybe. Its a shame that only a restricted number of types are supported - things like Data.Map/Data.Set can be supported perfectly, apart from restrictions in Template Haskell.
There are two cases.
1) The data structure contains values, in specific places. Lists, tuples, Either etc. are all like this. The rules in the paper cover all these situations.
2) The data structure contains values, but their place is a feature of the data structure - i.e. Map/Set. In this case the right thing to do is probably to do fromList/toList pairs on them.
Use Data.Traversable somehow - lots of things are instances of that. I'm just reading a paper about it... "A similar benefit can be found in the reassembly of a full data structure from separate shape and contents. This is a stateful operation, where the state consists of the contents to be inserted; but it is also a partial operation, because the number of elements provided may not agree with the number of positions in the shape." (p.10 http://web.comlab.ox.ac.uk/oucl/work/bruno.oliveira/iteratorJFP.pdf ) That reminded me of the 'uniplate' function... I haven't thought too closely about this, but it feels right. Also I wonder, since we can do deriving Functor, and Traversable instances are equally straightforward according to the paper, should we have deriving(Traversable)? Of course this would depend on the order of the constructor arguments just like deriving Ord, etc, do. Isaac -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGeUKDHgcxvIWYTTURApT5AKCB1QG4cgMoORIAf65LsyV1DFJc7wCgi2BJ wpKuYhtPZRriZ1qPzpy1Xe8= =a8ir -----END PGP SIGNATURE-----
participants (3)
-
Isaac Dupree -
Neil Mitchell -
Stefan O'Rear