isRecursiveTyCon

[Simon Peyton Jones]

Identifying recursive types is an old and unsatisfactory part of GHC.

The code in TcTyDecls was an early attempt and has not received much love since.  Partly because it's not so clear exactly what it is trying to do! What precisely does it mean for a TyCon to be "recursive" and what guarantees do you get?

It's clearly something to do with spotting loops, but with higher kinds it's possible to construct fixpoint combinators (the details escape me this morning).

In most of GHC I've adopted a conservative "online" approach; see Note [Expanding newtypes and products] in TyCon, and the accompanying `RecTcChecker` stuff.  But it builds on isRecursiveTyCon; without that it'd be far too conservative (e.g. Maybe (Maybe t)).

Type/data families make things more interesting; as do hs-boot files.


I believe that a bit of systematic thinking will help here; it'd be great if you could do that.

Simon

|  -----Original Message-----
|  From: ghc-devs [mailto:ghc-devs-bounces at haskell.org] On Behalf Of José
|  Manuel Calderón Trilla
|  Sent: 04 March 2016 02:46
|  To: ghc-devs at haskell.org
|  Subject: isRecursiveTyCon
|  
|  Hello,
|  
|  I'm extending GHC's demand analysis to sum types, but _not_ recursive
|  types. I was searching for a function that would tell me if a TyCon is
|  recursive, so that I could analyse Maybes but avoid Lists.
|  
|  I found isRecursiveTyCon, but it's not actually for this purpose,
|  there's actually a long note in typecheck/TcTyDecls.hs that explains
|  why it's not fit for determining which type constructors are recursive
|  in general. The key point from the note is
|  
|  "The "recursive" flag for algebraic data types is irrelevant (never
|  consulted) for types with more than one constructor."
|  
|  It seems that because the strictness analyser never worked over sum
|  types it never had to worry about recursive sum types and at some point
|  the flag that says a data type is recursive broke for sum types without
|  anyone knowing.
|  
|  For example the following mutually recursive data types have different
|  return values from isRecursiveTyCon
|  
|  data OddNat = One | SuccO EvenNat
|  
|  data EvenNat = Zero | SuccE OddNat
|  
|  
|  Does anyone know of the simplest way to test for this?
|  
|  Thanks for your time,
|  
|  Jose
|  _______________________________________________
|  ghc-devs mailing list
|  ghc-devs at haskell.org
|  https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.ha
|  skell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc-
|  devs&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7caf0464cbbf1a4e18
|  627c08d343d72286%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=700%2bnpJ
|  Iry1DQgeUrTTO29vHQ1mQ3TrwLj2uXVw9QPk%3d