[Hs-Generics] type constructor genericity with regular

[José Pedro Magalhães]

Hi,

2010/9/15 Jan Christiansen <jac at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/generics/attachments/20100915/44f8c4c5/attachment.html