Катаморфизм в F#

Question

Я читаю статью в Википедии о катаморфизмах, и на данный момент я смог воспроизвести примеры на Haskell на F#, за исключением этой части:

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

Возможно ли это сделать в F#?

Answer 1

Если вы думаете о выражении действительно общих сгибов для произвольных типов контейнеров, а также схем рекурсии непосредственно в системе типов F# (или CLR в этом отношении) - вам не повезло. Слишком много необходимого оборудования отсутствует в языке - наиболее важные типы.

Однако HKT можно кодировать в F#, используя технику, называемую дефункционализацией. Существует библиотека F#, основанная на концепциях из этой статьи - Высшее. Фактически, он уже реализует fix, cata/ana/hylomorphisms и алгебры в качестве доказательства концепции. Я не знаю, насколько хорошо это работает, как с точки зрения производительности, так и простоты использования.

Кроме того, вы можете вручную создавать складки, специально предназначенные для ваших контейнеров, что устраняет необходимость в HKT. Классическая серия постов в блоге о реализации катаморфизмов здесь. Это стоит прочитать - помимо сгибов, он также углубляется в программирование в стиле продолжения.