type constructor genericity with regular
Hi, I want to define a function which is generic for all unary type constructors using the regular package. More precisely, I want to define a function like the following, which replaces every polymorphic component by the position of the component in the generic representation. shape :: (Regular f, Shape (PF f)) => f a -> f [Bool] Is it correct that it is not possible to implement a function like this using regular? Or do I miss something? I have implemented the function by using different representation types K, I and so forth that take an additional argument. Furthermore I have added an additional type to mark the polymorphic component. Thanks, Jan
Hi Jan,
On Wed, Sep 15, 2010 at 10:30, Jan Christiansen
Hi,
I want to define a function which is generic for all unary type constructors using the regular package. More precisely, I want to define a function like the following, which replaces every polymorphic component by the position of the component in the generic representation.
shape :: (Regular f, Shape (PF f)) => f a -> f [Bool]
I'm not sure I fully understand what you're trying to do. Could you provide typical use cases of your function, to several arguments of different types? Cheers, Pedro
Is it correct that it is not possible to implement a function like this using regular? Or do I miss something?
I have implemented the function by using different representation types K, I and so forth that take an additional argument. Furthermore I have added an additional type to mark the polymorphic component.
Thanks, Jan _______________________________________________ Generics mailing list Generics@haskell.org http://www.haskell.org/mailman/listinfo/generics
Hi, On 15.09.2010, at 11:40, José Pedro Magalhães wrote:
I'm not sure I fully understand what you're trying to do. Could you provide typical use cases of your function, to several arguments of different types?
Consider a polymorphic data type with one type variable like lists. I want to replace every value of the "polymorphic" type by a list of Booleans that corresponds to its position in the term (with respect to the :*: constructor). For example, shape [1,2] = [[False],[True,False]] because the generic representation (without the injections) of [1,2] is K 1 :*: (K 2 :*: U)) and in this term the path [False] corresponds to 1 while the path [True,False] corresponds to 2. As another example consider the following data type for binary trees. data Tree a = Node (Tree a) a (Tree a) | Leaf a then we have shape (Node (Leaf 'a') 'b' (Leaf 'c')) = Node (Leaf [False]) [True,False] (Leaf [True,True]) because the generic representation (without the injections) of the argument tree is K 'a' :*: (K 'b' :*: K 'c'). In fact, for the same reason I suspect that it is not possible to implement shape by means of regular I would expect that it is not possible to implement the standard fmap by means of regular. Is this correct? Cheers, Jan
Hi,
2010/9/15 Jan Christiansen
Hi,
On 15.09.2010, at 11:40, José Pedro Magalhães wrote:
I'm not sure I fully understand what you're trying to do. Could you
provide typical use cases of your function, to several arguments of different types?
Consider a polymorphic data type with one type variable like lists. I want to replace every value of the "polymorphic" type by a list of Booleans that corresponds to its position in the term (with respect to the :*: constructor). For example,
shape [1,2] = [[False],[True,False]]
because the generic representation (without the injections) of [1,2] is K 1 :*: (K 2 :*: U)) and in this term the path [False] corresponds to 1 while the path [True,False] corresponds to 2.
As another example consider the following data type for binary trees.
data Tree a = Node (Tree a) a (Tree a) | Leaf a
then we have
shape (Node (Leaf 'a') 'b' (Leaf 'c')) = Node (Leaf [False]) [True,False] (Leaf [True,True])
because the generic representation (without the injections) of the argument tree is K 'a' :*: (K 'b' :*: K 'c').
In fact, for the same reason I suspect that it is not possible to implement shape by means of regular I would expect that it is not possible to implement the standard fmap by means of regular. Is this correct?
Ah, I now see what you mean. Yes, you are right: regular does not abstract over type parameters, hence you can't do much to them. We have a similar library which does abstract over one parameter, though. It's called generic-deriving on Hackage, and used by the Utrecht Haskell Compiler [1, 2]. However, in your application of shape to Tree, I see that you want to replace not only the parameters but also the recursive occurrences. I think this function could still be expressed with generic-deriving, though. For curiosity: what do you want this shape function for? Cheers, Pedro [1] Hackage package: http://hackage.haskell.org/package/generic-deriving [2] Companion paper: http://dreixel.net/research/pdf/gdmh_draft.pdf
On 15.09.2010, at 13:41, José Pedro Magalhães wrote:
Ah, I now see what you mean. Yes, you are right: regular does not abstract over type parameters, hence you can't do much to them. We have a similar library which does abstract over one parameter, though. It's called generic-deriving on Hackage, and used by the Utrecht Haskell Compiler [1, 2].
This looks quite interesting, thanks.
However, in your application of shape to Tree, I see that you want to replace not only the parameters but also the recursive occurrences.
I don't see what you mean here.
For curiosity: what do you want this shape function for?
This is probably a quite odd "application". I have proved some properties about functions f :: [a] -> [a] by representing them by a combination of (!!) and a function shape. That is, we have f xs == map (!!xs) (shape xs) where shape has the type [a] -> [Int] and simply numbers the elements of the list. I want to generalize these statements to functions f :: F a -> G a where F and G are arbitrary functors by providing generalizations of shape and (!!) for arbitrary functors. Cheers, Jan
Hi Jan,
2010/9/15 Jan Christiansen
On 15.09.2010, at 13:41, José Pedro Magalhães wrote:
However, in your application of shape to Tree, I see that you want to
replace not only the parameters but also the recursive occurrences.
I don't see what you mean here.
I'm sorry, you are only replacing parameters indeed. Never mind. I hope you can make it with generic-deriving. Feel free to ask anything if you run into troubles---the current release is rather experimental. Cheers, Pedro
participants (2)
-
Jan Christiansen -
José Pedro Magalhães