| The type system rejects it:
|
| ERROR "hylomorphism.lhs" (line 22): Ambiguous type signature in
| type declaration
|
| *** ambiguous type : (CoAlgebra a b, Algebra a c) => b -> c
| *** assigned to : hylo
|
| I think I understand the reason, but my question is:
|
| How can I define that function?
You should only use overloading in situations where values are
uniquely determined by their types. Describing algebras using
type classes like this does not fit that pattern. For example,
there are many possible candidates for Algebra List Int, none
of which is more general than any of the others. The situation
becomes even worse for your hylo example because that doesn't
even specify which functor is used, and there are many choices.
In such cases, it is better to work with the objects explicitly
rather than leaving overloading to figure out which ones you want.
Try something like:
newtype Fix f = In (f (Fix f))
fix a = In a
xif (In a) = a
type Algebra f a = f a -> a
type CoAlgebra f a = a -> f a
cata phi = phi . map (cata phi) . xif
ana psi = fix . map (ana psi) . psi
hylo phi psi = cata phi . ana psi
(Types can be inferred ... without ambiguity)
All the best,
Mark
