Есть ли эффективный, ленивый способ объединить FoldMap и Traverse? - PullRequest
Новая
       28

Есть ли эффективный, ленивый способ объединить FoldMap и Traverse?

10 голосов
/ 08 мая 2019

Недавнее предложение по списку рассылки библиотек на Haskell заставило меня рассмотреть следующее: 

ft :: (Applicative f, Monoid m, Traversable t)
   -> (b -> m) -> (a -> f b) -> t a -> f m
ft f g xs = foldMap f <$> traverse g xs

Я заметил, что ограничение Traversable может быть ослаблено до Foldable: 

import Data.Monoid (Ap (..))  -- Requires a recent base version

ft :: (Applicative f, Monoid m, Foldable t)
   -> (b -> m) -> (a -> f b) -> t a -> f m
ft f g = getAp . foldMap (Ap . fmap f . g)

В первоначальном предложении предполагалось, что f будет id, что приведет к 

foldMapA
  :: (Applicative f, Monoid m, Foldable t)
   -> (a -> f m) -> t a -> f m
--foldMapA g = getAp . foldMap (Ap . fmap id . g)
foldMapA g = getAp . foldMap (Ap . g)

, что строго лучше, чем метод обхода-затем-сгиба.

Нов более общем случае ft существует потенциальная проблема: fmap может быть дорогостоящим в f функторе, и в этом случае объединенная версия потенциально может быть более дорогой, чем оригинальная!

Обычные инструментыдля борьбы с дорогими fmap стоят Yoneda и Coyoneda.Поскольку нам нужно поднимать много раз и только один раз, Coyoneda - это то, что может помочь нам: 

import Data.Functor.Coyoneda

ft' :: (Applicative f, Monoid m, Foldable t)
    => (b -> m) -> (a -> f b) -> t a -> f m
ft' f g = lowerCoyoneda . getAp
  . foldMap (Ap . fmap f . liftCoyoneda . g)

Так что теперь мы заменяем все эти дорогие fmap на один (похоронен в lowerCoyoneda).Задача решена?Не совсем.

Проблема с Coyoneda состоит в том, что его liftA2 является строгим .Так что если мы напишем что-то вроде 

import Data.Monoid (First (..))

ft' (First . Just) Identity $ 1 : undefined
-- or, importing Data.Functor.Reverse,
ft' (Last . Just) Identity (Reverse $ 1 : undefined)

, то это не получится, тогда как ft не будет иметь проблем с ними.Есть ли способ получить наш торт и съесть его тоже?То есть версия, которая использует только ограничение Foldable, только в fmap с O (1) раз больше, чем traverse в функторе f, и такая же ленивая, как ft?

Примечание: мы могли бы сделать liftA2 для Coyoneda несколько ленивее: 

liftA2 f m n = liftCoyoneda $
  case (m, n) of
    (Coyoneda g x, Coyoneda h y) -> liftA2 (\p q -> f (g p) (h q)) x y

Этого достаточно, чтобы дать ему ответ на ft' (First . Just) Identity $ 1 : 2 : undefined, ноне до ft' (First . Just) Identity $ 1 : undefined.Я не вижу очевидного способа сделать его более ленивым, потому что совпадения с образцами в экзистенциалах всегда должны быть строгими.

1 Ответ

2 голосов
/ 08 мая 2019

Я не верю, что это возможно.Избегание fmap s в элементах, кажется, требует некоторых знаний о структуре контейнера.Например, экземпляр Traversable для списков может быть записан 

traverse f (x : xs) = liftA2 (:) (f x) (traverse f xs)

Мы знаем, что первый аргумент (:) - это отдельный элемент, поэтому мы можем использовать liftA2 для объединения процесса отображениянад действием для этого элемента с процессом объединения результата этого действия с результатом, связанным с остальной частью списка.

В более общем контексте структура сгиба может быть точно получена с помощьютип магмы с поддельным Monoid экземпляром: 

data Magma a = Bin (Magma a) (Magma a) | Leaf a | Nil
  deriving (Functor, Foldable, Traversable)

instance Semigroup (Magma a) where
  (<>) = Bin
instance Monoid (Magma a) where
  mempty = Nil

toMagma :: Foldable t => t a -> Magma a
toMagma = foldMap Leaf

Мы можем написать 

ft'' :: (Applicative f, Monoid m, Foldable t)
   => (b -> m) -> (a -> f b) -> t a -> f m
ft'' f g = fmap (lowerMagma f) . traverse g . toMagma

lowerMagma :: Monoid m => (a -> m) -> Magma a -> m
lowerMagma f (Bin x y) = lowerMagma f x <> lowerMagma f y
lowerMagma f (Leaf x) = f x
lowerMagma _ Nil = mempty

Но есть проблема в Traversable экземпляре: 

traverse f (Leaf x) = Leaf <$> f x

Это именно та проблема, которую мы пытались избежать.И нет ленивого решения для этого.Если мы встретим Bin l r, мы не можем лениво определить, являются ли l или r листьями.Итак, мы застряли.Если бы мы допустили ограничение Traversable для ft'', мы могли бы захватить результат обхода с более богатым типом типа магмы (например, используемым в lens), который я подозреваю может позволить нам сделать что-то более умное, хотя я еще ничего не нашел.

...