Гистоморфизм а-ля Мендлер - PullRequest
Новая
       59

Гистоморфизм а-ля Мендлер

0 голосов
/ 03 ноября 2018

Используя гистоморфизм (histo) из рекурсивных схем Я могу получить список, содержащий только нечетные индексы из исходного списка: 

import Data.Functor.Foldable

odds :: [a] -> [a]
odds = histo $ \case
  Nil                           -> []
  Cons h (_ :< Nil)             -> [h]
  Cons h (_ :< Cons _ (t :< _)) -> h:t

Как можно получить то же самое, используя mhisto? 

nil      = Fix Nil
cons a b = Fix $ Cons a b
list = cons 1 $ cons 2 $ cons 3 $ nil

modds :: Fix (ListF a) -> [a]
modds = mhisto alg where
   alg _ _ Nil = []
   alg f g (Cons a b) = ?

1 Ответ

0 голосов
/ 03 ноября 2018

Вот оно: 

modds :: Fix (ListF a) -> [a]
modds = mhisto alg
    where
    alg _ _ Nil = []
    alg odd pre (Cons a b) = a : case pre b of
        Nil -> []
        Cons _ b' -> odd b' 

GHCi> list = cata embed [1..10] :: Fix (ListF Int)
GHCi> odds (cata embed list)
[1,3,5,7,9]
GHCi> modds list
[1,3,5,7,9]

odd сворачивает остальную часть списка, в то время как pre копает предшественника. Обратите внимание, что наличие функции y -> f y в алгебре Мендлера отражает введение Cofree в алгебру обыкновенного гистоморфизма (в котором можно вернуться назад, достигнув хвоста потока Cofree): 

cata  :: Functor f => (f c -> c) -> Fix f -> c
histo :: Functor f => (f (Cofree f c) -> c) -> Fix f -> c

mcata  :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c

Подробнее о mcata и mhisto см. Главы 5 и 6 Категориальное программирование с индуктивным и коиндуктивным типами , от Varmo Vene .

...