Является ли функция списка Data.List.Extra катаморфизмом списка?

Базовая библиотека Haskell содержит несколько функций, которые являются строчными версиями соответствующих типов данных, таких как bool, maybe и either. В исходном коде Data.Bool.Extra функция bool четко выражена как катаморфизм типа данных:

bool = curry cata

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

-- base library definition
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

-- definition with cata
newtype Fix f = Fix {unFix :: f (Fix f)}
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
maybe n f m = cata alg where
    alg Nothing = n
    alg (Just x) = f x

Однако функция Data.List.Extra list только что упоминается в комментариях как «нерекурсивное преобразование по списку, например «может быть»», но, поскольку она нерекурсивна в отличие от своего типа данных, очевидно, это не так. любая схема рекурсии списка или нет? Поэтому он не определен в базовой библиотеке? Есть ли у функции какие-либо другие хорошие теоретические свойства?


person rubystallion    schedule 17.03.2017    source источник
comment
Немногие считают пакет extra распространенным, поэтому вот ссылка: список.   -  person Carl    schedule 17.03.2017
comment
какой тип bool с определением, которое у вас есть выше?   -  person is7s    schedule 17.03.2017
comment
Тип bool в определении — a -> a -> Bool -> a, как определено здесь.   -  person rubystallion    schedule 18.03.2017
comment
@rubystallion, но это определение для bool не будет проверять тип с данным определением cata.   -  person is7s    schedule 18.03.2017


Ответы (1)


Катаморфизм для [] - это foldr.

Функция list из пакета extra является преобразованием в кодировку Скотта, подобно тому, как катаморфизм является преобразованием в кодировку Черча. Поскольку кодировки Скотта нерекурсивны, они не могут соответствовать какой-либо схеме рекурсии.

person Carl    schedule 17.03.2017