Definition. The hylomorphism profunctor

Fix an endofunctor 𝐹:π’žοΈ€β†’π’žοΈ€. Hylomorphisms form a profunctor from coalgebras to algebras,

π–§π—’π—…π—ˆ:π–’π—ˆπ–Ίπ—…π—€(𝐹)op×𝖠𝗅𝗀(𝐹)β†’π’πžπ­,

where π–§π—’π—…π—ˆ((𝑋,𝛾),(𝐡,𝛼)) is the set of β„Ž:𝑋→𝐡 with β„Ž=π›Ύβ‹†πΉβ„Žβ‹†π›Ό.

The action is by composition. If 𝑔:(π‘Œ,𝛿)β†’(𝑋,𝛾) is a coalgebra morphism (𝑔⋆𝛾=𝛿⋆𝐹𝑔) and π‘˜:(𝐡,𝛼)β†’(𝐡′,𝛼′) is an algebra morphism (π›Όβ‹†π‘˜=πΉπ‘˜β‹†π›Όβ€²), then π‘”β‹†β„Žβ‹†π‘˜ is again a hylomorphism:

𝛿⋆𝐹(π‘”β‹†β„Žβ‹†π‘˜)⋆𝛼′=π›Ώβ‹†πΉπ‘”β‹†πΉβ„Žβ‹†π›Όβ‹†π‘˜=π‘”β‹†π›Ύβ‹†πΉβ„Žβ‹†π›Όβ‹†π‘˜=π‘”β‹†β„Žβ‹†π‘˜.

In these terms, a coalgebra 𝛾 is recursive when π–§π—’π—…π—ˆ(𝛾,βˆ’) is the terminal functor, and an algebra 𝛼 is corecursive when π–§π—’π—…π—ˆ(βˆ’,𝛼) is. For the inverse of an initial algebra the profunctor is representable, π–§π—’π—…π—ˆ(π—‚π—‡βˆ’1,βˆ’)≅𝖠𝗅𝗀(𝐹)(𝗂𝗇,βˆ’), and dually π–§π—’π—…π—ˆ(βˆ’,π—ˆπ—Žπ—βˆ’1)β‰…π–’π—ˆπ–Ίπ—…π—€(𝐹)(βˆ’,π—ˆπ—Žπ—) for a terminal coalgebra.

When every value of π–§π—’π—…π—ˆ is a singleton, every divide-and-conquer specification over 𝐹 has exactly one solution. This is what local contractivity guarantees.

hylomorphism-profunctor definition entries/category/hylomorphism-profunctor.hel