Все нижеследующее основано на моем (неправильном) понимании этой очень интересной статьи, опубликованной Мэтью Пикерингом в его комментарии: От моноидов к полукольцам: суть MonadPlus и альтернативы (Э. Ривас, М. Яскелиофф, Т. Шриверс). Все результаты принадлежат им; все ошибки мои.
От свободных моноидов к DList
Чтобы развить интуицию, сначала рассмотрим свободный моноид []
над категорией типов Haskell Hask
. Одна проблема с []
заключается в том, что если у вас есть
(xs `mappend` ys) `mappend` zs = (xs ++ ys) ++ zs
затем оценка этого требует обхода и повторного обхода xs
для каждого левого вложенного приложения mappend
.
Решение заключается в использовании CPS в виде списков различий:
newtype DList a = DL { unDL :: [a] -> [a] }
В документе рассматривается общая форма этого (называемая представлением Кэли), где мы не привязаны к свободному моноиду:
newtype Cayley m = Cayley{ unCayley :: Endo m }
с конверсиями
toCayley :: (Monoid m) => m -> Cayley m
toCayley m = Cayley $ Endo $ \m' -> m `mappend` m'
fromCayley :: (Monoid m) => Cayley m -> m
fromCayley (Cayley k) = appEndo k mempty
Два направления обобщения
Мы можем обобщить приведенную выше конструкцию двумя способами: во-первых, рассматривая моноиды не над Hask
, а над эндофункторами Hask
; т.е. монады; и, во-вторых, путем обогащения алгебраической структуры почти-полукольцами.
Free
монады в Codensity
Для любого (эндо)функтора Haskell f
мы можем создать свободную монаду Free f
, и у него будет аналогичная проблема производительности с левовложенными привязками с аналогичным решением использования представления Кэли Codensity
.
Почти-полукольца вместо моноидов
Здесь статья прекращает рассмотрение концепций, хорошо известных работающим программистам на Haskell, и начинает двигаться к своей цели. Почти-полукольцо похоже на кольцо, за исключением того, что оно проще, поскольку и сложение, и умножение просто обязаны быть моноидами. Связь между двумя операциями — это то, что вы ожидаете:
zero |*| a = zero
(a |+| b) |*| c = (a |*| c) |+| (b |*| c)
где (zero, |+|)
и (one, |*|)
— два моноида над некоторой общей базой:
class NearSemiring a where
zero :: a
(|+|) :: a -> a -> a
one :: a
(|*|) :: a -> a -> a
Свободное почти полукольцо (над Hask
) оказывается следующего типа Forest
:
newtype Forest a = Forest [Tree a]
data Tree a = Leaf | Node a (Forest a)
instance NearSemiring (Forest a) where
zero = Forest []
one = Forest [Leaf]
(Forest xs) |+| (Forest ys) = Forest (xs ++ ys)
(Forest xs) |*| (Forest ys) = Forest (concatMap g xs)
where
g Leaf = ys
g (Node a n) = [Node a (n |*| (Forest ys))]
(хорошо, что у нас нет коммутативности или инверсий, , которые делают свободные представления далеко не тривиально...)
Затем в статье дважды применяется представление Кэли к двум моноидальным структурам.
Однако, если мы делаем это наивно, мы не получаем хорошего представления: мы хотим представить почти-полукольцо, и поэтому необходимо учитывать всю почти-полукольцо, а не только одну выбранную моноидную структуру. [...] [Мы] получаем полукольцо эндоморфизмов над эндоморфизмами DC(N)
:
newtype DC n = DC{ unDC :: Endo (Endo n) }
instance (Monoid n) => NearSemiring (DC n) where
f |*| g = DC $ unDC f `mappend` unDC g
one = DC mempty
f |+| g = DC $ Endo $ \h -> appEndo (unDC f) h `mappend` h
zero = DC $ Endo $ const mempty
(Здесь я немного изменил реализацию по сравнению с документом, чтобы подчеркнуть, что мы используем структуру Endo
дважды). Когда мы обобщим это, два слоя не будут одинаковыми. Далее в газете говорится:
Обратите внимание, что rep
не является гомоморфизмом почти полукольца из N
в DC(N)
, поскольку он не сохраняет единицу [...] Тем не менее, [...] семантика вычисления над почти полукольцом будет сохранена, если мы поднимем значения к представлению, выполните почти полукольцевое вычисление там, а затем вернитесь к исходному почти полукольцу.
MonadPlus
почти полукольцо
Затем в статье переформулируется класс типов MonadPlus
, чтобы он соответствовал правилам почти полукольца: (mzero, mplus)
является моноидальным:
m `mplus` mzero = m
mzero `mplus` m = m
m1 `mplus` (m2 `mplus` m3) = (m1 `mplus` m2) `mplus` m3
и он взаимодействует с монадой-моноидом, как и ожидалось:
join mzero = mzero
join (m1 `mplus` m2) = join m1 `mplus` join m2
Или, используя привязки:
mzero >>= _ = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)
Однако это не правила существующий класс типов MonadPlus
из base
, который указан как:
mzero >>= _ = mzero
_ >> mzero = mzero
В документе MonadPlus
экземпляры, которые удовлетворяют почти полукольцевым законам, называются «монадами недетерминизма», и Maybe
приводится в качестве примера, который является MonadPlus
, но не монадой недетерминизма, поскольку установка m1 = Just Nothing
и m2 = Just
(Just False)
является контрпримером к join (m1 `mplus` m2) = join m1
`mplus` join m2
.
Свободное представление и представление Кэли монад недетерминизма
Собрав все вместе, с одной стороны мы имеем Forest
-подобную свободную монаду недетерминизма:
newtype FreeP f x = FreeP { unFreeP :: [FFreeP f x] }
data FFreeP f x = PureP x | ConP (f (FreeP f x))
instance (Functor f) => Functor (FreeP f) where
fmap f x = x >>= return . f
instance (Functor f) => Monad (FreeP f) where
return x = FreeP $ return $ PureP x
(FreeP xs) >>= f = FreeP (xs >>= g)
where
g (PureP x) = unFreeP (f x)
g (ConP x) = return $ ConP (fmap (>>= f) x)
instance (Functor f) => MonadPlus (FreeP f) where
mzero = FreeP mzero
FreeP xs `mplus` FreeP ys = FreeP (xs `mplus` ys)
а с другой стороны, двойное представление Кэли двух моноидальных слоев:
newtype (:^=>) f g x = Ran{ unRan :: forall y. (x -> f y) -> g y }
newtype (:*=>) f g x = Exp{ unExp :: forall y. (x -> y) -> (f y -> g y) }
instance Functor (g :^=> h) where
fmap f m = Ran $ \k -> unRan m (k . f)
instance Functor (f :*=> g) where
fmap f m = Exp $ \k -> unExp m (k . f)
newtype DCM f x = DCM {unDCM :: ((f :*=> f) :^=> (f :*=> f)) x}
instance Monad (DCM f) where
return x = DCM $ Ran ($x)
DCM (Ran m) >>= f = DCM $ Ran $ \g -> m $ \a -> unRan (unDCM (f a)) g
instance MonadPlus (DCM f) where
mzero = DCM $ Ran $ \k -> Exp (const id)
mplus m n = DCM $ Ran $ \sk -> Exp $ \f fk -> unExp (a sk) f (unExp (b sk) f fk)
where
DCM (Ran a) = m
DCM (Ran b) = n
caylize :: (Monad m) => m a -> DCM m a
caylize x = DCM $ Ran $ \g -> Exp $ \h m -> x >>= \a -> unExp (g a) h m
-- I wish I called it DMC earlier...
runDCM :: (MonadPlus m) => DCM m a -> m a
runDCM m = unExp (f $ \x -> Exp $ \h m -> return (h x) `mplus` m) id mzero
where
DCM (Ran f) = m
В документе приводится следующий пример вычисления, выполняемого в недетерминированной монаде, которая будет вести себя плохо для FreeP
:
anyOf :: (MonadPlus m) => [a] -> m a
anyOf [] = mzero
anyOf (x:xs) = anyOf xs `mplus` return x
Действительно, в то время как
length $ unFreeP (anyOf [1..100000] :: FreeP Identity Int)
требует времени, версия, преобразованная Кейли
length $ unFreeP (runDCM $ anyOf [1..100000] :: FreeP Identity Int)
мгновенно возвращается.
person
Cactus
schedule
01.09.2015