Type Level Fix Point while Ensuring Termination

Question

It is possible to represent to some how make unFix total? Possibly by restricting what f is?

record Fix (f : Type -> Type) where
    constructor MkFix
    unFix : f (Fix f)

> :total unFix
Fix.unFix is possibly not total due to:
    MkFix, which is not strictly positive

Answer 1

The problem here is that Idris has no way of knowing that the base functor you are using for your datatype is strictly positive. If it were to accept your definition, you could then use it with a concrete, negative functor and prove Void from it.

There are two ways to represent strictly positive functors: by defining a universe or by using containers. I have put everything in two self-contained gists (but there are no comments there).

A Universe of Strictly Positive Functors

You can start with a basic representation: we can decompose a functor into either a sigma type (Sig), a (strictly-positive) position for a recursive substructure (Rec) or nothing at all (End). This gives us this description and its decoding as a Type -> Type function:

-- A universe of positive functor
data Desc : Type where
  Sig : (a : Type) -> (a -> Desc) -> Desc
  Rec : Desc -> Desc
  End : Desc


-- The decoding function
desc : Desc -> Type -> Type
desc (Sig a d) x = (v : a ** desc (d v) x)
desc (Rec d)   x = (x, desc d x)
desc End       x = ()

Once you have this universe of functors which are guaranteed to be strictly positive, you can take their least fixpoint:

-- The least fixpoint of such a positive functor
data Mu : Desc -> Type where
  In : desc d (Mu d) -> Mu d

You can now define your favourite datatype.

Example: Nat

We start with a sum type of tags for each one of the constructors.

data NatC = ZERO | SUCC

We then define the strictly positive base functor by storing the constructor tag in a sigma and computing the rest of the description based on the tag value. The ZERO tag is associated to End (there is nothing else to store in a zero constructor) whilst the SUCC one demands a Rec End, that is to say one recursive substructure corresponding to the Nat's predecessor.

natD : Desc
natD = Sig NatC $ \ c => case c of
  ZERO => End
  SUCC => Rec End

Our inductive type is then obtained by taking the fixpoint of the description:

nat : Type
nat = Mu natD

We can naturally recover the constructors we expect:

zero : nat
zero = In (ZERO ** ())

succ : nat -> nat
succ n = In (SUCC ** (n, ()))

References

This specific universe is taken from 'Ornamental Algebras, Algebraic Ornaments' by McBride but you can find more details in 'The Gentle Art of Levitation' by Chapman, Dagand, McBride, and Morris.

Strictly Positive Functors as the Extension of Containers

The second representation is based on another decomposition: each inductive type is seen as a general shape (i.e. its constructors and the data they store) plus a number of recursive positions (which can depend on the specific value of the shape).

record Container where
  constructor MkContainer
  shape : Type
  position : shape -> Type

Once more we can give it an interpretation as a Type -> Type function:

container : Container -> Type -> Type
container (MkContainer s p) x = (v : s ** p v -> x)

And take the fixpoint of the strictly positive functor thus defined:

data W : Container -> Type where
  In : container c (W c) -> W c

You can once more recover your favourite datatypes by defining Containers of interest.

Example: Nat

Natural numbers have two constructors, each storing nothing at all. So the shape will be a Bool. If we are in the zero case then there are no recursive positions (Void) and in the succ one there is exactly one (()).

natC : Container
natC = MkContainer Bool (\ b => if b then Void else ())

Our type is obtained by taking the fixpoint of the container:

nat : Type
nat = W natC

And we can recover the usual constructors:

zero : nat
zero = In (True ** \ v => absurd v)

succ : nat -> nat
succ n = In (False ** \ _ => n)

References

This is based on 'Containers: Constructing Strictly Positive Types' by Abbott, Altenkirch, and Ghani.