Как только у меня есть F-алгебра, могу ли я определить Foldable и Traversable в терминах этого?

Ответ 1

F-алгебра определяет рецепт для оценки одного уровня рекурсивной структуры данных после того, как вы оценили всех детей. Foldable определяет способ оценки (не обязательно рекурсивной) структуры данных, если вы знаете, как преобразовать значения, хранящиеся в ней, в элементы моноида.

Чтобы реализовать foldMap для рекурсивной структуры данных, вы можете начать с определения алгебры, носитель которой является моноидом. Вы бы определили, как преобразовать лист в моноидальное значение. Затем, предполагая, что все дочерние элементы node были оценены для моноидальных значений, вы должны определить способ их комбинирования в node. После того, как вы определили такую ​​алгебру, вы можете запустить катаморфизм, чтобы оценить foldMap для всего дерева.

Итак, ответ на ваш вопрос заключается в том, что для создания экземпляра Foldable для структуры данных с фиксированной точкой вам необходимо определить соответствующую алгебру, носитель которой является моноидом.

Изменить: Здесь выполняется реализация Складной:

data Expr e a = Branch [a] | Leaf e

newtype Ex e = Ex { unEx :: Fix (Expr e) }

evalM :: Monoid m => (e -> m) -> Algebra (Expr e) m
evalM _ (Branch xs) = mconcat xs
evalM f (Leaf   i ) = f i

instance Foldable (Ex) where
  foldMap f = cata (evalM f) . unEx

tree :: Ex Int
tree = Ex $ branch [branch [leaf 1, leaf 2], leaf 3]

x = foldMap Sum tree

Реализация Traversable как катаморфизма - это немного больше, потому что вы хотите, чтобы результат был не просто сводкой - он должен содержать полную восстановленную структуру данных. Поэтому носитель алгебры должен быть типом конечного результата traverse, который (f (Fix (Expr b))), где f - Applicative.

tAlg :: Applicative f => (e -> f b) -> Algebra (Expr e) (f (Fix (Expr b)))

Здесь эта алгебра:

tAlg g (Leaf e)    = leaf   <$> g e
tAlg _ (Branch xs) = branch <$> sequenceA xs

И вот как вы реализуете traverse:

instance Traversable Ex where
  traverse g = fmap Ex . cata (tAlg g) . unEx

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

fAlg :: (a -> b) -> Algebra (Expr a) (Fix (Expr b))
fAlg g (Leaf e) = leaf (g e)
fAlg _ (Branch es) = branch es

instance Functor Ex where
  fmap g = Ex . cata (fAlg g) . unEx

(Майкл Слоан помог мне написать этот код.)

Ответ 2

Очень приятно, что вы использовали Bifunctor. Используя Bifunctor базового функтора (Expr), определим Functor на фиксированной точке (Fix Expr). Этот подход обобщается на Bifoldable и Bitraversable (они также находятся в base).

Посмотрим, как это будет выглядеть с помощью recursion-schemes. Это выглядит несколько иначе, поскольку мы определяем нормальный рекурсивный тип, скажем Tree e, а также его базовый функтор: Base (Tree e) = TreeF e a с двумя функциями: project :: Tree e -> TreeF e (Tree e) и embed :: TreeF e (Tree e) -> Tree e. Механизм рекурсии выводится с использованием TemplateHaskell:

Заметим, что мы имеем Base (Fix f) = f (project = unFix, embed = Fix), поэтому мы можем использовать refix преобразовать Tree e в Fix (TreeF e) и обратно. Но нам не нужно использовать Fix, поскольку мы можем непосредственно cata Tree!

Сначала включает:

{-# LANGUAGE TemplateHaskell, KindSignatures, TypeFamilies, DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

import Data.Bifunctor
import Data.Bifoldable
import Data.Bitraversable

Затем данные:

data Tree e = Branch [Tree e] | Leaf e deriving Show

-- data TreeF e r = BranchF [r] | LeafF e
-- instance Traversable (TreeF e)
-- instance Foldable (TreeF e)
-- instance Functor (TreeF e)
makeBaseFunctor ''Tree

Теперь, когда у нас есть механизм, мы можем иметь катаморфизм

cata :: Recursive t => (Base t a -> a) -> t -> a
cata f = c where c = f . fmap c . project

или (что нам понадобится позже)

cataBi :: (Recursive t, Bifunctor p, Base t ~ p x) => (p x a -> a) -> t -> a
cataBi f = c where c = f . second c . project

Сначала a Functor экземпляр. Экземпляр Bifunctor для TreeF соответствует описанию OP, обратите внимание, как Functor выпадает само по себе.

instance Bifunctor TreeF where
    bimap f _ (LeafF e)    = LeafF (f e)
    bimap _ g (BranchF xs) = BranchF (fmap g xs)

instance Functor Tree where
    fmap f = cata (embed . bimap f id)

Неудивительно, что Foldable для фиксированной точки можно определить в терминах Bifoldable базы функтор:

instance Bifoldable TreeF where
    bifoldMap f _ (LeafF e)    = f e
    bifoldMap _ g (BranchF xs) = foldMap g xs

instance Foldable Tree where
    foldMap f = cata (bifoldMap f id)

И, наконец, Traversable:

instance Bitraversable TreeF where
    bitraverse f _ (LeafF e)    = LeafF <$> f e
    bitraverse _ g (BranchF xs) = BranchF <$> traverse g xs

instance Traversable Tree where
    traverse f = cata (fmap embed . bitraverse f id)

Как вы можете видеть, определения очень просты и следуют сходным шаблон.

Действительно, мы можем определить traverse -подобную функцию для каждой фиксированной точки, которая основывается функтор Bitraversable.

traverseRec
    :: ( Recursive t, Corecursive s, Applicative f
       , Base t ~ base a, Base s ~ base b, Bitraversable base)
    => (a -> f b) -> t -> f s
traverseRec f = cataBi (fmap embed . bitraverse f id)

Здесь мы используем cataBi, чтобы сделать подпись типа более красивой: no Functor (base b) as это "подразумевается" на Bitraversable base. Btw, что одна хорошая функция как ее тип сигнатуры в три раза длиннее реализации).

В заключение я должен упомянуть, что Fix в Haskell не совершенен: Мы используем последний аргумент для исправления базового функтора:

Fix :: (* -> *) -> * -- example: Tree e ~ Fix (TreeF e)

Таким образом, Bartosz должен определить Ex в своем ответе, чтобы совместить типы, однако было бы лучше зафиксировать первый аргумент:

Fix :: (* -> k) -> k -- example: Tree e = Fix TreeF' e

где data TreeF' a e = LeafF' e | BranchF' [a], т.е. TreeF с индексами переворачивается. Таким образом, мы могли бы иметь Functor (Fix b) в терминах Bifunctor f, Bifunctor (Fix b) в терминах (несуществующих в общих библиотеках) Trifunctor и т.д.

Вы можете прочитать о моих неудачных попытках об этом и комментариях Эдварда Кмета по вопросу в https://github.com/ekmett/recursion-schemes/pull/23