Бесплатная групповая монада - программирование

В теории категорий aa monad представляет собой композицию из двух сопряженных функторов. Например, монада Maybe может быть свободным указательным функтором, составленным с забывчивым функтором. Аналогично, Монада Списка - это свободный моноидный функтор, составленный с забывчивым функтором.

Моноид - одна из простейших алгебраических структур, поэтому я задаюсь вопросом, может ли программирование извлечь выгоду из более сложных. Я не нашел бесплатную групповую монаду в стандартных пакетах Haskell, поэтому я определю ее здесь.

data FreeGroup a = Nil | PosCons a (FreeGroup a) | NegCons a (FreeGroup a)

Оператор == определяется так, что NegCons x (PosCons x y) == y. Соответственно, в length :: FreeGroup a -> Int каждый PosCons подсчитывается +1 и каждый NegCons -1 (это единственный морфизм группы для Int, что значения +1 на каждом PosCons).

Как и в списках (свободные моноиды), concat является просто умножением, а map является функториальным лифтом функций. Таким образом, экземпляр monad FreeGroup точно такой же, как у List.

Использует ли свободная групповая монада какое-либо программирование? Кроме того, часто существует интерпретация монады как значения в контексте: для List контекст будет выбором или неопределенностью. Существует ли такая интерпретация для свободной монады?

Как насчет свободных колец и векторных пространств (которые всегда свободны)?

Для любой алгебраической структуры S существование категорического свободного функтора FS :: Set -> S означает существование функции, которую Haskell вызывает fold:

foldS :: S s => (a -> s) -> FS a -> s

Он поднимает функцию на основе a на S -морфизм на свободном объекте FS a. Обычная функция foldr является специализацией foldMonoid (называемой foldMap в Haskell, по какой-то причине я не совсем понимаю), моноид - это набор функций b -> b с составом как умножение.

Для полноты, вот пример монады FreeGroup:

mult :: FreeGroup a -> FreeGroup a -> FreeGroup a
mult Nil x = x
mult x Nil = x
mult (PosCons x y) z = PosCons x (mult y z)
mult (NegCons x y) z = NegCons x (mult y z)

inverse :: FreeGroup a -> FreeGroup a
inverse Nil = Nil
inverse (PosCons x y) = mult (inverse y) (NegCons x Nil)
inverse (NegCons x y) = mult (inverse y) (PosCons x Nil)

groupConcat :: FreeGroup (FreeGroup a) -> FreeGroup a
groupConcat Nil = Nil
groupConcat (PosCons x l) = mult x (groupConcat l)
groupConcat (NegCons x l) = mult (inverse x) (groupConcat l)

instance Functor FreeGroup where
  fmap f Nil = Nil
  fmap f (PosCons x y) = PosCons (f x) (fmap f y)
  fmap f (NegCons x y) = NegCons (f x) (fmap f y)

instance Applicative FreeGroup where
  pure x = PosCons x Nil
  fs <*> xs = do { f <- fs; x <- xs; return $ f x; }

instance Monad FreeGroup where
  l >>= f = groupConcat $ fmap f l

type FreeGroupT a = [Either a a] fgTofgT :: FreeGroup a -> FreeGroupT a fgTofgT Nil = [] fgTofgT (a :+: as) = Right a : fgToList as fgTofgT (a :-: as) = Left a : fgToList as fgTTofg :: FreeGroupT a -> FreeGroup a fgTTofg [] = Nil fgTTofg (Right a : as) = a :+: fgTTofg as fgTTofg (Left a : as) = a :-: fgTTofg as --using (:-:) instead of NegCons --and (:+:) instead of PosCons

Ответ 1