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

Я читаю статью википедии о катаморфизмах, и на данный момент я смог воспроизвести примеры 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 #?

Ответы

Ответ 1

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

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

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