- Generics - Haskell.org

ANNOUNCE: multirec-0.1
by Andres Loeh 31 Oct '08

31 Oct '08

multirec: Generic programming with systems of recursive datatypes ================================================================= Many generic programs require information about the recursive positions of a datatype. Examples include the generic fold, generic rewriting or the Zipper data structure. Several generic programming systems allow to write such functions by viewing datatypes as fixed points of a pattern functor. Traditionally, this view has been limited to so-called regular datatypes such as lists and binary trees. In particular, systems of mutually recursive datatypes have been excluded. With the multirec library, we provide a mechanism to talk about fixed points of systems of datatypes that may be mutually recursive. On top of this representations, generic functions such as the fold or the Zipper can then be defined. We expect that the library will be especially interesting for compiler writers, because ASTs are typically systems of mutually recursive datatypes, and with multirec it becomes easy to write generic functions on ASTs. The library is based on ideas described in the paper: Alexey Rodriguez, Stefan Holdermans, Andres Löh, Johan Jeuring Generic programming with fixed points for mutually recursive datatypes Technical Report, Universiteit Utrecht http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-019.pdf Features -------- * Generalizes the fixed point view from single, regular datatypes to systems of recursive datatypes. * Includes detailed examples: generic fold and generic compos, the latter in the style of Björn Bringert, Arne Ranta A pattern for almost compositional functions ICFP 2006 The Zipper and generic rewriting for systems of datatypes will be released soon as separate libraries that build on multirec. * The generic compos functions do not require the user to modify their existing systems of datatypes. * In its current form, this library does not support nested datatypes. Requirements ------------ * GHC 6.8.3 or later * Cabal 1.2.1 or later Download -------- With cabal-install: cabal install multirec Get the package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/multirec Get the source: svn checkout https://svn.cs.uu.nl:12443/repos/dgp-haskell/multirec/trunk Bugs & Support -------------- Report issues, request features, or just discuss the library with the authors, maintainers, and other interested persons at: http://www.haskell.org/mailman/listinfo/generics -- Andres Loeh, Universiteit Utrecht mailto:andres@cs.uu.nl mailto:mail@andres-loeh.de http://www.andres-loeh.de

1 0

Re: syb changes (Re: base-3 vs base-4 (Was: Breakage with 6.10))
by José Pedro Magalhães 13 Oct '08

13 Oct '08

Hello Ian, I'm attaching patches that add a link to the new wiki from the haddock of syb (and change the maintainer to generics(a)haskell.org) Thanks, Pedro On Mon, Oct 13, 2008 at 11:39, José Pedro Magalhães <jpm(a)cs.uu.nl> wrote: > Hello, > > I created a new wiki page for SYB which also contains some more detailed > information on the changes for 6.10: > http://www.cs.uu.nl/wiki/bin/view/GenericProgramming/SYB > > > Thanks, > Pedro >

1 0

Re: Splitting SYB from the base package in GHC 6.10
by José Pedro Magalhães 10 Oct '08

10 Oct '08

Hello, On Sun, Oct 5, 2008 at 15:40, Claus Reinke <claus.reinke(a)talk21.com> wrote: > >The following "dubious" instances are now in the syb package (in the > >Data.Generics.Instances module): DataType TyCon TypeRep Handle ThreadId > >StablePtr (a -> b) (IO a) (ST s a) (STM a) (IORef a) (TVar a) (MVar a). > All > >the other instances are in the base package, Data.Data module. > > Contrary to that list, 'Data (a->b)' is still in Data.Data? > Oops, my mistake. Thanks for noticing! Attaching patches. Thanks, Pedro

1 1

Re: Splitting SYB from the base package in GHC 6.10
by José Pedro Magalhães 04 Oct '08

04 Oct '08

Hello Ian, On Mon, Sep 22, 2008 at 21:54, Ian Lynagh <igloo(a)earth.li> wrote: > > I'm a little lost as to exactly what changes you want. Can you send a > darcs patch against the base and syb repos please?: > http://darcs.haskell.org/ghc-6.10/packages/base/ > http://darcs.haskell.org/ghc-6.10/packages/syb/ > Currently everything is in the syb package. I'm attaching patches to 4 repositories that split SYB between the syb and base packages. (It's my first time doing this so I hope all is fine, but if not just let me know.) Basically, a new module Data.Data in base contains the previous Data.Generics.Basics and most of the instances from Data.Generics.Instances. Other changes are: On Mon, Sep 15, 2008 at 13:28, José Pedro Magalhães <jpm(a)cs.uu.nl> wrote: > > - Ratio has to be fixed to have a consistent instance: either it's seen > as an abstract datatype (therefore with undefined gunfold) or a gfoldl has > to be defined matching its gunfold; > > Ratio had its gfoldl defined to match its gunfold. Since GHC.Ratio exports the constructor (:%), I guess Ratio cannot be considered abstract. > - Complex should have its derived instance restored (or otherwise a > manual instance with a proper gfoldl); > > Complex had its derived instance restored. > - Other places that have to be changed: > - The Data instance of Data.Array should be moved from > Data.Generics.Instances into Array, to avoid syb dependency; > > This was not done, since I am unsure if it would break some sort of Hugs compatibility. If the instance for Array is in Data.Data (note that it is not an orphan anymore), then it's provided independently of where the Array comes from. If it would be in Data.Array, then Hugs would have to provide an instance in its Array library too. > - The imports of SYB in the following modules should be fixed to avoid > bringing into scope all the instances: > > ./containers/Data/IntMap.hs > ./containers/Data/IntSet.hs > ./containers/Data/Map.hs > ./containers/Data/Sequence.hs > ./containers/Data/Set.hs > ./containers/Data/Tree.hs > ./network/Network/URI.hs > ./packedstring/Data/PackedString.hs > > This was not done, given the discussion in [1] regarding instance visibility and orphans. The following "dubious" instances are now in the syb package (in the Data.Generics.Instances module): DataType TyCon TypeRep Handle ThreadId StablePtr (a -> b) (IO a) (ST s a) (STM a) (IORef a) (TVar a) (MVar a). All the other instances are in the base package, Data.Data module. Ian, do you think this could be incorporated in any possible upcoming beta versions/release candidates before the final release? I did some sanity checking but it would be good if a wider audience could test it. Thanks, Pedro [1] http://thread.gmane.org/gmane.comp.lang.haskell.libraries/9929/focus=27

1 0

Re: instance visibility
by José Pedro Magalhães 30 Sep '08

30 Sep '08

I'm trying to understand the implications of this discussion in the current splitting off of SYB from base. In the division that was more or less agreed [1], the Data class and its uncontested instances would be kept in base, whereas the rest would go into a new syb package. The instances were traditionally orphans in Data.Generics.Instances, but it was suggested that they should now be moved into Data.Generics.Basics. This would make SYB free of orphans, but no longer offers a user the possibility of avoid the import of Data.Generics.Instances to define its own instances. It also invalidates some of the changes proposed in [1], namely caring about the imports of Data.IntMap, Data.IntSet, etc. So my question is: should Data.Generics.Instances indeed be folded into Data.Generics.Basics (which contains the Data class and associated stuff)? (Worth noting is that the instances that are moved to the syb package will remain orphans, but the idea is that those might change or disappear in the future.) Thanks, Pedro [1] http://thread.gmane.org/gmane.comp.lang.haskell.libraries/9962/focus=9981

1 0

ANNOUNCE: Extensible and Modular Generics for the Masses (EMGM) 0.1
by Sean Leather 19 Sep '08

19 Sep '08

Extensible and Modular Generics for the Masses ============================================== Extensible and Modular Generics for the Masses (EMGM) is a library for generic programming in Haskell using type classes. This is the initial release of a maintained library for EMGM. Other versions have previously existed in various states from various sources. We plan to continue updating and maintaining this version. Visit the home page: http://www.cs.uu.nl/wiki/GenericProgramming/EMGM Features -------- The primary features of EMGM include: * Datatype-generic programming using sum-of-product views * Large collection of ready-to-use generic functions * Included support for standard datatypes: lists, Maybe, tuples * Easy to add support for new datatypes * Type classes make writing new functions straightforward in a structurally inductive style * Generic functions are extensible with ad-hoc cases for arbitrary datatypes * Good performance of generic functions The features of this distribution include: * The API is thoroughly documented with Haddock * Fully tested with QuickCheck and HUnit * Program coverage ensures that all useful code has been touched by tests * Tested on both Mac and Windows systems Requirements ------------ EMGM has the following requirements: * GHC 6.8.1 - It has been tested with versions 6.8.3 and 6.9.20080916. * Cabal library 1.2.1 - It has been tested with versions 1.2.3 and 1.4.0.1. Download & Source ----------------- Use caball-install: cabal install emgm Get the package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/emgm Get the source: svn checkout https://svn.cs.uu.nl:12443/repos/dgp-haskell/EMGM Examples -------- Check out the examples: https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/examples/ Bugs & Support -------------- Report issues or request features: http://code.google.com/p/emgm/ Discuss EMGM with the authors, maintainers, and other interested persons: http://www.haskell.org/mailman/listinfo/generics Credits ------- The research for EMGM originated with Ralf Hinze. It was extended with work by Bruno Oliveira and Andres Löh. More details of the library functionality were explored by Alexey Rodriguez. We are very grateful to all of these people for the foundation on which this library was built. The current authors and maintainers of EMGM are: * Sean Leather * José Pedro Magalhães * Alexey Rodriguez * Andres Löh

1 0

Re: Splitting SYB from the base package in GHC 6.10
by José Pedro Magalhães 15 Sep '08

15 Sep '08

Hello, On Wed, Sep 3, 2008 at 13:50, Simon Peyton-Jones <simonpj(a)microsoft.com>wrote: > My reading of Claus's message is that, modulo discussion of some details of > [partial], he'd go with that plan. > > Is that acceptable to others? If so, someone (Jose) needs to sort out the > details. 19 Sept is GHC's release candidate, so we need this done well > before then. Are the details sorted out? Summarizing: - Data.Generics.Basics stays in base; - All other SYB modules besides Data.Generics.Instances go into a new 'syb' package; - Data.Generics.Instances is split in two, one part remaining in base and the other moving to the syb package. Regarding the instances, two aspects have to be considered: 1. Avoiding the implicit re-export of Data instances from modules in base; 2. Deciding which instances go where. Regarding (1), the following changes need to be done: - Ratio has to be fixed to have a consistent instance: either it's seen as an abstract datatype (therefore with undefined gunfold) or a gfoldl has to be defined matching its gunfold; - Complex should have its derived instance restored (or otherwise a manual instance with a proper gfoldl); - Other places that have to be changed: - The Data instance of Data.Array should be moved from Data.Generics.Instances into Array, to avoid syb dependency; - The imports of SYB in the following modules should be fixed to avoid bringing into scope all the instances: ./containers/Data/IntMap.hs ./containers/Data/IntSet.hs ./containers/Data/Map.hs ./containers/Data/Sequence.hs ./containers/Data/Set.hs ./containers/Data/Tree.hs ./network/Network/URI.hs ./packedstring/Data/PackedString.hs - The following modules use of Ratio instances, which is not problematic if the instance for Ratio is fixed. Therefore no change is needed here: ./haskell-src/Language/Haskell/Syntax.hs ./template-haskell/Language/Haskell/TH/Quote.hs ./template-haskell/Language/Haskell/TH/Syntax.hs - These modules depend on an instance for ForeignPtr Word8. Instances for types with phantom types stay in base, since no suitable instance can be given (see (2) below). Therefore no change is needed here: ./bytestring/Data/ByteString/Internal.hs ./bytestring/Data/ByteString/Lazy/Internal.hs Regarding (2), the separation of the 44 Data instances in Data.Generics.Instances is the following: - These 26 [standard] instances are uncontroversial and can accompany the Data class: [a] (Maybe a) (Either a b) () (,) (,,) (,,,) (,,,,) (,,,,,) (,,,,,,) Bool Ordering Char Double Float Integer Int Int8 Int16 Int32 Int64 Word Word8 Word16 Word32 Word64 - These 2 instances could also be [standard] and stay in base, after fixing (see (1) above): Ratio Complex - These 2 instances have phantom types. No good suggestion for what to do with them has shown up, therefore they stay in base as they are: Ptr ForeignPtr - These 6 instances have abstract datatypes. Unless there is some reason to keep them in base, I suggest they go into the syb package: DataType TyCon TypeRep Handle ThreadId StablePtr - These 7 go in the syb package for future discussion: (a -> b) (IO a) (ST s a) (STM a) (IORef a) (TVar a) (MVar a) - The instance for Array is moved into Data.Array. Any remarks? Thanks, Pedro

1 0

Re: Splitting SYB from the base package in GHC 6.10
by José Pedro Magalhães 07 Sep '08

07 Sep '08

Hello, On Fri, Sep 5, 2008 at 14:34, Jules Bean <jules(a)jellybean.co.uk> wrote: > José Pedro Magalhães wrote: > >> Complex has a derived instance. In Data.Complex: >> >> data (RealFloat a) => Complex a >> = !a :+ !a # if __GLASGOW_HASKELL__ >> deriving (Eq, Show, Read, Data) >> # else >> deriving (Eq, Show, Read) >> # endif >> >> Was there a problem with this? >> >> > Yes, isn't it exactly the same problem as Ratio? > > The derived instance 'leaks' the implementation detail of a complex number > as a real and imaginary component. As part of a large structure I might want > to apply some operation to all the 'Doubles' therein, but certainly not to > the components of any Complex Doubles. You can imagine particular situations > where I want to apply only to the real component, or something more subtle. > > You can also imagine that an alternative implementation of Complexes in > polar coordinates (with a suitable solution to the principle value problem) > is supposed to be abstractly the same, but would gain a totally different > Data instance. I think the question here is if the datatype if abstract or not. Complex exports its (:+) constructor, so the implementation details are not hidden. Therefore it is correct to traverse its arguments. Ratio, however, does not export its (:%) constructor: Ratio is abstract, while Complex is not. I guess then Complex should have a Data instance as it is above. But regarding Ratio, do we want to change its gfoldl to match its current gunfoldl (as suggested before), or go the other way around, and change its gunfold, toConstr and dataTypeOf to match its gfoldl? If we change its gfoldl, the instance is fully defined, but does not respect the data abstraction. If we go the other way around, the instance becomes partial (gunfold and toConstr return errors), but respects the data abstraction. In any case, the behaviour would differ from the current. Any opinions on this? Thanks, Pedro

1 0

Splitting SYB from the base package in GHC 6.10
by José Pedro Magalhães 02 Sep '08

02 Sep '08

Hello all, I'm initiating this discussion per suggestion of SP Jones and following from [1]. The issue is: SYB is being moved out of base into its own package. However, the Data class is, in a way, tied to base since it depends on the deriving mechanism. Therefore, it was suggested that the entire Data.Generics.Basics module [2] should remain in base. This module defines the Data class and several associated functions and datatypes. I don't think anyone objected to this so far: please correct me if I'm wrong, or object now. Then it was also suggested that Data.Generics.Instances [3] could stay in base (perhaps inside Basics as well). This, however, would prevent dealing with the "dubious" Data instances [4], and this was one of the motivating factors to split SYB from base. This refers concretely to the instances: instance (Data a, Data b) => Data (a -> b) instance Typeable a => Data (IO a) instance Typeable a => Data (Ptr a) instance Typeable a => Data (StablePtr a) instance Typeable a => Data (IORef a) instance Typeable a => Data (ForeignPtr a) instance (Typeable s, Typeable a) => Data (ST s a) instance Typeable a => Data (TVar a) instance Typeable a => Data (MVar a) instance Typeable a => Data (STM a) instance (Data a, Integral a) => Data (Ratio a) These instances are defined in such a way that they do not traverse the datatype. In fact, there is no other possible implementation, and this implementation at least allows for datatypes which contain both "regular" and "dubious" elements to still have their "regular" elements traversed. However, this implies that a user cannot redefine such instances even in the case where s/he knows extra information about these types that would allow for a more useful instance definition, for instance. Claus, please correct me if I'm wrong, but if the 11 "dubious" instances (or perhaps less, given your message in [5]) go in the syb package and the remaining, "standard" ones stay in base, we: - Mantain backwards compatibility regarding SYB in 6.10, and - Can still deal with the issue by releasing a new version of the syb package later, independently of GHC. Since the deadline for 6.10 is approaching I'm assuming that we should try to minimize the changes there, while keeping future development in the syb package as open as possible. Finally, there are module naming issues, which are probably secondary to the issue above and can be dealt with separately and later. Thanks, Pedro [1] The base library and GHC 6.10: http://thread.gmane.org/gmane.comp.lang.haskell.libraries/9929 [2] http://www.haskell.org/ghc/dist/stable/docs/libraries/base/Data-Generics-Ba… [3] http://www.haskell.org/ghc/dist/stable/docs/libraries/base/Data-Generics-In… [4] http://www.haskell.org/pipermail/generics/2008-June/000347.html [5] http://article.gmane.org/gmane.comp.lang.haskell.libraries/9957

5 5

Re: Splitting SYB from the base package in GHC 6.10
by Claus Reinke 01 Sep '08

01 Sep '08

> These instances are defined in such a way that they do not traverse the > datatype. In fact, there is no other possible implementation, and this > implementation at least allows for datatypes which contain both "regular" and > "dubious" elements to still have their "regular" elements traversed. > However, this implies that a user cannot redefine such instances even in the > case where s/he knows extra information about these types that would allow for > a more useful instance definition, for instance. |These two statements appear to be contradictory. Perhaps an example of |a possible instance would help. "no other possible implementation" is an overstatement, though an easy one to make: those 'Data' instances are incomplete because better instances are hard to come by. One can perhaps do little improvements, like replace the effective 'gmapT = id' for 'IO a' and 'b -> a' with something like[1]: gmapT f fun = f . fun -- instead of gmapT f fun = fun gmapT f io = (return . f) =<< io -- instead of gmapT f io = io but that still doesn't make those instances complete. If it wasn't for the partial uses, like skipping 'IO a' and 'b -> a' as parts of derived 'Data' instances, one wouldn't want these instances at all, imho (at least not in their current form). Then there are abstract types, for which the current default when implementing reflection is to assume "no constructors", hence no basis for 'gunfold', hence more incomplete 'Data' instances and runtime errors. It might be possible to experiment with associating exactly one, abstract, constructor with each abstract type instead, but that isn't something I'd like to bake in without more experience. Another way to look at it: 'Data' tries to do too much in a single class, and the consequence are all those half-implemented 'Data' instances. The probable long-term solution is to split 'Data' into 2 or 3 classes, so that we know that a any type instantiating 'DataGfoldl' really supports 'gfoldl' b any type instantiating 'DataGunfold' really supports 'gunfold' c any type instantiating 'DataReflect' really supports 'Data' reflection Currently, too many types instantiate 'Data' without supporting b or c (-> runtime errors), and a few instances don't even support a. All of which suggests that 'Data' should probably leave 'base', as it needs to evolve further? |Claus argued that -> and the monads could be treated by analogy |with Show for these types. I had mentioned 'Text.Show.Functions' as an example of "improper" instances provided for optional import to support 'deriving Show'. But when I read your sentence, my first thought was: perhaps there's also a way to apply the showList trick? That would neatly avoid either changing the 'deriving' mechanism or having dummy instances. More reason for moving everything to 'syb', keeping it flexible for a while. |There is an additional problem with types like ThreadId, Array, ST, STM, |TVar and MVar: they're notionally defined in other packages, even though |they're actually defined in partially-hidden GHC.* modules in base and |re-exported. Would it be sufficient for 'syb' to depend on both 'base' and those notional source packages? It would be useful to keep the instances in 'syb' until the 'Data' story has settled down, after which the instances ought to move to their 'data' type source packages. Claus [1] http://www.haskell.org/pipermail/libraries/2008-July/010319.html

2 2