[clean-list] Understanding Generics

[Arjen van Weelden]

Alexsandro Soares wrote:
> Arjen,
> 
>    I'm trying to make a Clean version of the genetic
> programming system originally written in Haskell using
> PolyP. The online reference is:
> 
> http://www.cs.chalmers.se/~patrikj/poly/others/geneticalgorithmsinhaskellwithpolytypicprogramming.ps.gz
Interesting paper.

> There, the author uses a paramorphism to implement the
> function "sub" (called "scan", in the original
> system), in this way:
> 
> ------------------------------------------------
> 
> --para :: Regular d => (d a -> FunctorOf d a b -> b)
> -> d a -> b
> para i x = i x (fmap id (para i) (out x)) 
> 
> polytypic fchildren :: (f a [b] -> [b]) 
> = case f of 
>     Const t -> \x -> [] 
>     Empty   -> \x -> [] 
>     Par     -> \x -> [] 
>     Rec     -> \x -> x 
>     f * g   -> \(x,y) -> fchildren x ++ fchildren y 
>     f + g   -> either fchildren fchildren 
> 
> --scan :: d a -> [d a] 
> scan = para (\x -> \y -> x : fchildren y) 
> 
> ----------------------------------------------
Ah yes, a much more precise specification. It looks like one could 
translate the polytypic function to a Clean generic function. `fmap' can 
be replaces by `gMap{|*->*|}', I don't know what `out' does but it's 
probably in the paper. Unfortunately, the generic type variable f is not 
of kind * (it has 2 type arguments, that makes it *->*->*), which is not 
supported by the Clean generics implementation. IIRC, PolyP and 
Clean/Generic Haskell are different in the way they handle recursive 
types, which makes some things not expressible in both languages.

>   I think the result of sub [[1, 2], [3], [4, 5, 6]]
> is
>   
>    [ [[1, 2], [3], [4, 5, 6]], 
>      [[3], [4, 5, 6]], 
>      [[4, 5, 6]], 
>      [[]] 
>    ]
>   
>   But I'm not sure.
I think so too. The implementation that I sent you fails on this.
I'll have a go at translating the PolyP example to Clean, after 
refreshing my memory of PolyP.

regards,
	Arjen