2010/9/15 Jan Christiansen <jac@informatik.uni-kiel.de>

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