Я новичок в 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 бесплатно прямо сейчас...
foldr всегда можно определить как:
foldr f z t = appEndo (foldMap (Endo . f) t) z
где appEndo и Endo являются просто новыми упаковщиками/обертками. Фактически, этот код вытащили прямо из Складного типа. Итак, определив foldMap, вы автоматически получите foldr.
Начнем с типа 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, потому что endofunction является функцией от одного типа к одному и тому же типу.)
Теперь, если мы посмотрим на подпись списка foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
мы можем видеть, что foldEndo соответствует ему, за исключением обобщения на любой Foldable и для некоторого переупорядочения аргументов.
Прежде чем мы перейдем к реализации, есть техническое осложнение в том, что b -> b не может быть непосредственно сделана экземпляр Monoid. Чтобы решить эту проблему, мы используем Endo newtype wrapper от 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, то вывод по существу один и тот же, за исключением того, что мы используем другой моноид из endofunctions, причем flip (.) как двоичная операция (т.е. мы составляем функции в противоположном направлении).