Fixpoints

Definitions to support various fixpoints, both on the value level and the type level.

This software is made available under the terms of the MIT License.

FuPy.fixpoints.fix(f: Func) → A[source]

Return fixpoint of f.

Uses laziness to avoid infinite recursion. The call fix(f) will result in f(Lazy(lambda: fix(f))). Thus, the argument of f is made lazy. TODO: Why “make fix lazy”? Terminology needs reconsideration.

class FuPy.fixpoints.Functor(*args, **kwargs)[source]

Type class for functors.

Deprecated (for use with (co)inductive types).

FuPy.fixpoints.fmap(f: Func) → Func[F[X], F[Y]][source]

Apply functor F to function f in X -> Y to get function in F[X] -> F[Y].

Deprecated (for use with (co)inductive types).

FuPy.fixpoints.Fmap[F, X, Y]

class FuPy.fixpoints.Fix(_unFix: Final[F[Fix[F]] | Lazy[F[Fix[F]]]])[source]

Fix[F] is fixpoint data type for functor F.

For a lazy Fix, invoke as Fix(Lazy(lambda: v)). An alternative would be to define locally:

class LazyFix[F, X](Fix[F[X]]):
    def unFix(self) -> F[Fix[F]]:
        return v

... LazyFix(None) ...

FuPy.fixpoints.in_(a: F[Fix[F]]) → Fix[source]

Initial constructor F-algebra of Fix[F].

Deprecated type bound Functor.

FuPy.fixpoints.out(a: Fix | Lazy[Fix]) → F[Fix[F]][source]

Final deconstructor F-coalgebra of Fix[F].

Inverse of in. Deprecated type bound Functor.

FuPy.fixpoints.FAlgebra[F, X]

FuPy.fixpoints.cata(fmap: Fmap) → Func[F_Algebra, Func[Fix, Y]][source]

Construct catamorphism given functor and F-algebra (curried).

cata(fmap: (X -> Y) -> F[X] -> F[Y])(alg: F[Y] -> Y)(x: Fix[F]) -> Y:: return (alg @ fmap(cata(fmap)(alg)) @ out)(x)

Note the typing: cata(fmap)(alg): Y <- Fix[F] out: F[Fix[F]] <- Fix[F] fmap(cata(fmap)(alg)): F[Y] <- F[Fix[F]] alg: Y <- F[Y]

FuPy.fixpoints.cata_(alg: F_Algebra) → Func[Fix, X][source]

For F-algebra alg, construct catamorphism in Fix[F] -> X.

Deprecated. ?

FuPy.fixpoints.F_CoAlgebra[F, X]

FuPy.fixpoints.ana(fmap: Fmap) → Func[F_CoAlgebra, Func[X, Fix]][source]

Construct anamorphism given functor and F-coalgebra (curried).

ana(fmap: (X -> Y) -> F[X] -> F[Y])(coalg: Y -> F[Y])(x: X) -> Fix[F]:: return (in @ fmap(ana(fmap)(coalg)) @ coalg)(x)

Note the typing: ana(fmap)(coalg): Fix[F] <- X coalg: F[X] <- X fmap(ana(fmap)(coalg)): F[Fix[F]] <- F[X] in: Fix[F] <- F[Fix[F]]

FuPy.fixpoints.ana_(coalg: F_CoAlgebra) → Func[X, Fix][source]

For F-coalgebra coalg, construct anamorphism in X -> Fix[F].

Deprecated. ?

FuPy.fixpoints.hylo(fmap: Fmap) → Func[Both[F_Algebra, F_CoAlgebra], Func][source]: Construct hylomorphism given functor and F-(co)algebras (curried).