Foldr / Foldl бесплатно, когда Tree реализует Foldable foldMap?

Я новичок в Haskell и учусь по "Learn You a Haskell".

Я кое-что не понимаю в Tree реализации Foldable.

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r

Цитата из LYAH: «Итак, если мы просто реализуем foldMap для какого-то типа, мы получим foldr и foldl для этого типа бесплатно!».

Кто-нибудь может это объяснить? Я не понимаю, как и почему я теперь бесплатно получаю foldr и foldl ...


fold haskell foldable
person Roely de Vries    schedule 27.04.2014    source источник
comment
Кстати, механизм предоставления этих бесплатных реализаций аналогичен бесплатной реализации /=, которую вы получаете, если реализуете ==, как обсуждалось здесь   -  person hugomg    schedule 27.04.2014

Ответы (2)


arrow_upward
6
arrow_downward

foldr всегда можно определить как:

foldr f z t = appEndo (foldMap (Endo . f) t) z

где appEndo и Endo - это просто распаковщики / оболочки нового типа. Фактически, этот код был взят прямо из класса типов Foldable. Итак, определяя foldMap, вы автоматически получаете foldr.

person nomen    schedule 27.04.2014
comment
Точно так же foldl можно определить в терминах foldr и, следовательно, также foldMap, так что эта функция также предоставляется бесплатно. - person John L; 27.04.2014

arrow_upward
30
arrow_downward

Начнем с типа foldMap:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

foldMap работает, отображая функцию a -> m на структуру данных, а затем прогоняя ее, разбивая элементы в единое накопленное значение с помощью mappend.

Далее, мы отмечаем, что для некоторого типа b функции b -> b образуют моноид с (.) в качестве бинарной операции (т. Е. mappend) и id в качестве элемента идентичности (т. Е. mempty. Если вы еще не встретили его, id - это определяется как id x = x). Если бы мы специализировались foldMap на этом моноиде, мы получили бы следующий тип:

foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)

(Я назвал функцию foldEndo, потому что конечная функция - это функция от одного типа к одному и тому же типу.)

Теперь, если мы посмотрим на подпись списка foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

мы видим, что foldEndo совпадает с ним, за исключением обобщения на любой Foldable и некоторого изменения порядка аргументов.

Прежде чем мы перейдем к реализации, есть техническая сложность в том, что b -> b нельзя напрямую сделать экземпляром Monoid. Чтобы решить эту проблему, мы используем вместо этого Endo оболочку newtype из Data.Monoid:

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

Написано в терминах Endo, foldEndo просто специализировано foldMap:

foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b

Итак, мы перейдем непосредственно к foldr и определим его в терминах foldMap.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

Это определение по умолчанию, вы можете найти в Data.Foldable. Вероятно, самая сложная часть - Endo . f; если у вас возникли проблемы с этим, думайте о f не как о бинарном операторе, а как о функции одного аргумента с типом a -> (b -> b); затем мы оборачиваем получившуюся конечную функцию в Endo.

Что касается foldl, вывод по сути такой же, за исключением того, что мы используем другой моноид эндофункций с flip (.) в качестве бинарной операции (т.е. мы составляем функции в противоположном направлении).

person duplode    schedule 27.04.2014