[Haskell-cafe] OT: Isorecursive types and type abstraction

[Edsko de Vries]

On Thu, Jan 24, 2008 at 10:06:04AM -0600, Antoine Latter wrote:
> Can "Fix" be made to work with higher-kinded types?  If so, would the
> following work:
> 
> Perfect = /\ A . Fix (L :: * -> *) . (A + L (A,A))

Hi,

Thanks for your quick reply. Unfortunately, your solution does not work. For

  Fix X. t

to be well-defined, we must have that if 'X' has kind 'k', then 't' must
also have kind 'k' (compare the type of 'fix' in Haskell: (a -> a) -> a).

> Keep in mind I have no idea what the "Perfect" data structure is
> supposed to look like.

The Haskell equivalent would be

data Perfect a = Leaf a | Branch (Perfect (a, a))

and models perfect binary trees (I admit, slightly headwrecking datatype! :)

Edsko