- Generics - Haskell.org

New paper
by Johan Jeuring 15 Jul '08

15 Jul '08

We have just finished a paper in which we use type families and GADTs to do generic programming with fixed points for mutually recursive datatypes: Generic programming with fixed points for mutually recursive datatypes Alexey Rodriguez, Stefan Holdermans, Andres Löh, Johan Jeuring Abstract: Many datatype-generic functions need access to the recursive positions in the structure of the datatype, and therefore adopt a fixed point view on datatypes. Examples include variants of fold that traverse the data following the recursive structure, or the zipper data structure that enables navigation along the recursive positions. However, Hindley-Milner-inspired type systems with algebraic datatypes make it difficult to express fixed points for anything but regular datatypes. Many real-life examples such as abstract syntax trees are in fact systems of mutually recursive datatypes and therefore excluded. Using Haskell's GADTs and type families, we describe a technique that allows a fixed-point view for systems of mutually recursive datatypes. We demonstrate that our approach is widely applicable by giving several examples of generic functions for this view, most prominently the Zipper. See http://people.cs.uu.nl/andres/Rec/ -- Johan

1 0

Re: Traversible Functor Data, or: X marks the spot (Re: Haddock version during build)
by Claus Reinke 30 Jun '08

30 Jun '08

>> Does anyone out there *want* functions and IO in Data? > > I have a feeling you sometimes need those instances to make the > typechecker happy, even though you aren't actually doing anything > generic on those parts of the types. > > syb-with-class has also defined IO and (->) instances, but no comment as > to why. I found this remark in "Scrap More Boilerplate: .." (section 5.3, non-representable data types): Lastly, it is convenient to give Data instances even for types that are not strictly data types, such as function types or monadic IO types. Otherwise deriving ( Data ) would fail for a data type that had even one constructor with a functional argument type, so the user would instead have to write the Data instance by hand. Instead, we make all such types into vacuous instances of Data. Traversal will safely cease for values of such types. However, values of these types can not be read and shown. So the convenience hypothesis seems correct. The problem with this is that it assumes that the vacuous instances do not involve any types that the generic traversals are operating on. Also, while I could add such a vacuous instance Data (a->b), and then use deriving Data over the remaining types, I cannot remove an existing instance Data (a->b), nor can I easily override its effects. I suggest to separate the vacuous from the proper instances, and to expose only the former via Data.Generics. That way, the convenience is only an import away, but doesn't get in the way of non-standard applications. Claus

2 1

instance Data (in-)conveniences (Re: Traversible Functor Data, or: X marks the spot)
by Claus Reinke 29 Jun '08

29 Jun '08

>> I suggest to separate the vacuous from the proper instances, >> and to expose only the former via Data.Generics. That way, >> the convenience is only an import away, but doesn't get in >> the way of non-standard applications. > > The problem with this is that it leads to conflicting instances if you > import both. I was thinking of splitting Data.Generics.Instances, moving some of its Data instances to Data.Generics.DummyInstances, and not importing/exporting the latter from Data.Generics. Importing both Data.Generics and Data.Generics.DummyInstances would give the current situation, no conflicting instances. And those who need application-specific instances instead of the dummies can avoid importing the dummy instances. In particular, 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) claim to have polymorphic/generic components, but use the defaults gfoldl _ z = z gmapT f x = unID (gfoldl k ID x) where k (ID c) x = ID (c (f x)) meaning that gmapT (=id) will never get access to those component types. Contrast this with the conventional instances for [], Maybe, Either, (,..) in the same module, and especially the abstraction- preserving instance for Array a b. And compare the not very consistent results (sometimes the transformation is applied, sometimes not): > everywhere (mkT ((+1)::Int->Int)) (0,1)::(,) Int Int (1,2) > everywhere (mkT ((+1)::Int->Int)) (0%1)::Ratio Int 0%1 > everywhere (mkT ((+1)::Int->Int)) (return 0::[] Int) [1] > everywhere (mkT ((+1)::Int->Int)) (return 0::IO Int) 0 > everywhere (mkT ((+1)::Int->Int)) (return 0::() -> Int) () 0 > everywhere (mkT ((+1)::Int->Int)) (array (0,0) [(0,0)] :: Array Int Int) array (0,0) [(0,1)] There isn't any straightforward "proper" Data instance for those types, either. But if, say, I'd knew that, for a specific application context, I'd want to apply my transformation (b->b) to the range, and only to the range, of all functions (a->b), via post-composition, how would I even do that, given the existing instance Data (a->b)? I can bypass monomorphic functions using extT, but what about polymorphic functions? > (\(f,g)->(f (),g 0)) $ everywhere (mkT (((+1).)::(()->Int)->(()->Int))) (\()->(0::Int),\_->(0::Int)) (1,0) Is there a way to do this without removing the existing Data instance (which would allow me to define my own)? Claus

1 0

RE: Traversible Functor Data, or: X marks the spot (Re: Haddock version during build)
by Simon Peyton-Jones 24 Jun '08

24 Jun '08

| I was surprised to see Data instances for (a->b) and IO a, | since for such non-algebraic types, there isn't anything to | gfoldl or gmap over. And those instances do indeed seem | to offer very little functionality (not to mention the runtime | errors..). I'm surprised too. I thought Data meant, well, data. Does anyone out there *want* functions and IO in Data? | ps. What is the right list for this topic? Possibly generics(a)haskell.org Simon

1 0

patch applied (generics): Attempted to write an instance for Perfect and failed.
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 11:20:45 PDT 2008 Alexey Rodriguez <mrchebas(a)gmail.com> * Attempted to write an instance for Perfect and failed. M ./comparison/syb3/FoldTree.lhs -1 +1 M ./comparison/syb3/PerfectReps.hs +84

1 0

patch applied (generics): GRose test for syb3 with hand-written Data instance.
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 09:38:23 PDT 2008 Alexey Rodriguez <mrchebas(a)gmail.com> * GRose test for syb3 with hand-written Data instance. M ./comparison/syb3/GEq.lhs -2 +2 M ./comparison/syb3/GRoseReps.hs -3 +18

1 0

patch applied (generics): Yet more info for bug
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 09:37:21 PDT 2008 Alexey Rodriguez <mrchebas(a)gmail.com> * Yet more info for bug M ./comparison/syb3/BugBinTree.lhs -1 +1 M ./comparison/syb3/Derive.hs -3 +5

1 0

patch applied (generics): Start of new time / efficiency measurement
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 06:08:00 PDT 2008 patrikj(a)chalmers.se * Start of new time / efficiency measurement M ./comparison/Common.lhs -21 +7 M ./comparison/Makefile +5 M ./comparison/TestEfficiency.lhs -22 +10 M ./comparison/TestSelectIntWTree.lhs -3 +8 M ./comparison/TreeDatatype.hs +23 M ./comparison/log.txt +37 A ./comparison/time.hs

1 0

patch applied (generics): WTree uses the new Derive, Company uses the old, otherwise it breaks. Perfect works with neither.
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 06:40:21 PDT 2008 Alexey Rodriguez <mrchebas(a)gmail.com> * WTree uses the new Derive, Company uses the old, otherwise it breaks. Perfect works with neither. M ./comparison/syb3/CompanyReps.hs +3 M ./comparison/syb3/Derive.hs -1 +4 M ./comparison/syb3/FoldTree.lhs -1 M ./comparison/syb3/PerfectReps.hs +2 M ./comparison/syb3/TreeReps.hs -1 +1

1 0

patch applied (generics): Some notes to the BugBinTree file.
by Alexey Rodriguez Yakushev 01 Apr '08

01 Apr '08

Tue Apr 1 06:13:15 PDT 2008 Alexey Rodriguez <mrchebas(a)gmail.com> * Some notes to the BugBinTree file. M ./comparison/syb3/BugBinTree.lhs -1 +4

1 0