How does `HFix` work in Haskell's multirec package?

Question

I understand the regular fixed-point type combinator and I think I understand the higher-order fixed-n type combinators, but HFix eludes me. Could you give an example of a set of data-types and their (manually derived) fixed points that you can apply HFix to.

Answer 1

The natural reference is the paper Generic programming with fixed points for mutually recursive datatypes where the multirec package is explained.

HFix is a fixpoint type combinator for mutually recursive data types. It is well explained in Section 3.2 in the paper, but the idea is to generalise this pattern:

 Fix :: (∗ -> ∗) -> ∗
 Fix2 :: (∗ -> ∗ -> ∗) -> (∗ -> ∗ -> ∗) -> ∗

to

 Fixn :: ((∗ ->)^n * ->)^n ∗
 ≈
 Fixn :: (*^n -> *)^n -> *

To restrict how many types it does a fixed point over, they use type constructors instead of *^n. They give an example of an AST data type, mutually recursive over three types in the paper. I offer you perhaps the simplest example instead. Let us HFix this data type:

data Even = Zero | ESucc Odd deriving (Show,Eq)
data Odd  = OSucc Even       deriving (Show,Eq)

Let us introduce the family specific GADT for this datatype as is done in section 4.1

data EO :: * -> * where
  E :: EO Even
  O :: EO Odd

EO Even will mean that we are carrying around an even number. We need El instances for this to work, which says which specific constructor we are refering to when writing EO Even and EO Odd respectively.

instance El EO Even where proof = E
instance El EO Odd  where proof = O

These are used as constraints for the HFunctor instance for I.

Let us now define the pattern functor for the even and odd data type. We use the combinators from the library. The :>: type constructor tags a value with its type index:

type PFEO = U      :>: Even   -- ≈ Zero  :: ()      -> EO Even
        :+: I Odd  :>: Even   -- ≈ ESucc :: EO Odd  -> EO Even
        :+: I Even :>: Odd    -- ≈ OSucc :: EO Even -> EO Odd

Now we can use HFix to tie the knot around this pattern functor:

type Even' = HFix PFEO Even
type Odd'  = HFix PFEO Odd

These are now isomorphic to EO Even and EO Odd, and we can use the hfrom and hto functions if we make it an instance of Fam:

type instance PF EO = PFEO

instance Fam EO where
  from E Zero      = L    (Tag U)
  from E (ESucc o) = R (L (Tag (I (I0 o))))
  from O (OSucc e) = R (R (Tag (I (I0 e))))
  to   E (L    (Tag U))           = Zero
  to   E (R (L (Tag (I (I0 o))))) = ESucc o
  to   O (R (R (Tag (I (I0 e))))) = OSucc e

A simple little test:

test :: Even'
test = hfrom E (ESucc (OSucc Zero))

test' :: Even
test' = hto E test

*HFix> test'
ESucc (OSucc Zero)

Another silly test with an Algebra turning Even and Odds to their Int value:

newtype Const a b = Const { unConst :: a }

valueAlg :: Algebra EO (Const Int)
valueAlg _ = tag (\U             -> Const 0)
           & tag (\(I (Const x)) -> Const (succ x))
           & tag (\(I (Const x)) -> Const (succ x))

value :: Even -> Int
value = unConst . fold valueAlg E