Haskell Language
складываемый
Поиск…
Вступление
Foldable
- это класс типов t :: * -> *
которые допускают операцию складывания . Сложность агрегирует элементы структуры в четко определенном порядке, используя функцию объединения.
замечания
Если t
является Foldable
это означает, что для любого значения ta
мы знаем, как получить доступ ко всем элементам a
от «внутри» ta
в фиксированном линейном порядке. Это значение foldMap :: Monoid m => (a -> m) -> (ta -> m)
: мы «посещаем» каждый элемент с помощью сводной функции и разбиваем все сводки вместе. Порядок Monoid
уважения (но инвариантны к разным группировкам).
Подсчет элементов Складной структуры
length
учитывает вхождения элементов a
в складную структуру ta
.
ghci> length [7, 2, 9] -- t ~ []
3
ghci> length (Right 'a') -- t ~ Either e
1 -- 'Either e a' may contain zero or one 'a'
ghci> length (Left "foo") -- t ~ Either String
0
ghci> length (3, True) -- t ~ (,) Int
1 -- '(c, a)' always contains exactly one 'a'
length
определяется как эквивалентная:
class Foldable t where
-- ...
length :: t a -> Int
length = foldl' (\c _ -> c+1) 0
Обратите внимание, что этот тип возврата Int
ограничивает операции, которые могут выполняться на значениях, полученных вызовами функции length
. fromIntegral
- полезная функция, которая позволяет нам справиться с этой проблемой.
Складывание структуры в обратном порядке
Любая сгиб может выполняться в противоположном направлении с помощью Dual
моноида , который переворачивает существующий моноид, чтобы агрегация шла назад.
newtype Dual a = Dual { getDual :: a }
instance Monoid m => Monoid (Dual m) where
mempty = Dual mempty
(Dual x) `mappend` (Dual y) = Dual (y `mappend` x)
Когда основной моноид вызова foldMap
перевернут с помощью Dual
, сгиб бежит назад; следующий тип Reverse
определяется в Data.Functor.Reverse
:
newtype Reverse t a = Reverse { getReverse :: t a }
instance Foldable t => Foldable (Reverse t) where
foldMap f = getDual . foldMap (Dual . f) . getReverse
Мы можем использовать эту технику , чтобы написать сжатый reverse
для списков:
reverse :: [a] -> [a]
reverse = toList . Reverse
Экземпляр Foldable для двоичного дерева
Чтобы создать экземпляр Foldable
вам необходимо предоставить определение, по крайней мере, foldMap
или foldr
.
data Tree a = Leaf
| Node (Tree a) a (Tree a)
instance Foldable Tree where
foldMap f Leaf = mempty
foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r
foldr f acc Leaf = acc
foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l
Эта реализация выполняет обход дерева в порядке.
ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)
-- +--'b'--+
-- | |
-- +-'a'-+ +-'c'-+
-- | | | |
-- * * * *
ghci> toList myTree
"abc"
Расширение DeriveFoldable
позволяет GHC генерировать Foldable
экземпляры на основе структуры типа. Мы можем изменить порядок машинного обхода путем настройки макета конструктора Node
.
data Inorder a = ILeaf
| INode (Inorder a) a (Inorder a) -- as before
deriving Foldable
data Preorder a = PrLeaf
| PrNode a (Preorder a) (Preorder a)
deriving Foldable
data Postorder a = PoLeaf
| PoNode (Postorder a) (Postorder a) a
deriving Foldable
-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)
preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)
postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x
ghci> toList (inorder myTree)
"abc"
ghci> toList (preorder myTree)
"bac"
ghci> toList (postorder myTree)
"acb"
Сглаживание Складной структуры в список
toList
сглаживается в Foldable
структуру ta
в список a
сек.
ghci> toList [7, 2, 9] -- t ~ []
[7, 2, 9]
ghci> toList (Right 'a') -- t ~ Either e
"a"
ghci> toList (Left "foo") -- t ~ Either String
[]
ghci> toList (3, True) -- t ~ (,) Int
[True]
toList
определяется как эквивалент:
class Foldable t where
-- ...
toList :: t a -> [a]
toList = foldr (:) []
Выполнение побочного эффекта для каждого элемента Складной структуры
traverse_
выполняет Applicative
действие для каждого элемента в Foldable
структуре. Он игнорирует результат действия, сохраняя только побочные эффекты. (Для версии, которая не отбрасывает результаты, используйте Traversable
.)
-- using the Writer applicative functor (and the Sum monoid)
ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3]
((),Sum {getSum = 6})
-- using the IO applicative functor
ghci> traverse_ putStrLn (Right "traversing")
traversing
ghci> traverse_ putStrLn (Left False)
-- nothing printed
for_
является traverse_
с аргументами перевернута. Он похож на цикл foreach
на императивном языке.
ghci> let greetings = ["Hello", "Bonjour", "Hola"]
ghci> :{
ghci| for_ greetings $ \greeting -> do
ghci| print (greeting ++ " Stack Overflow!")
ghci| :}
"Hello Stack Overflow!"
"Bonjour Stack Overflow!"
"Hola Stack Overflow!"
sequenceA_
сворачивает Foldable
полную Applicative
действия в одно действие, игнорируя результат.
ghci> let actions = [putStrLn "one", putStLn "two"]
ghci> sequenceA_ actions
one
two
traverse_
определяется как эквивалент:
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr (\x action -> f x *> action) (pure ())
sequenceA_
определяется как:
sequenceA_ :: (Foldable t, Applicative f) -> t (f a) -> f ()
sequenceA_ = traverse_ id
Более того, когда Foldable
также является Functor
, traverse_
и sequenceA_
имеют следующее соотношение:
traverse_ f = sequenceA_ . fmap f
Сглаживание сложенной структуры в моноид
foldMap
отображает каждый элемент Складной структуры в Monoid
, а затем объединяет их в одно значение.
foldMap
и foldr
могут быть определены в терминах друг друга, а это означает, что для экземпляров Foldable
требуется только определение для одного из них.
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
Пример использования моноидного Product
:
product :: (Num n, Foldable t) => t n -> n
product = getProduct . foldMap Product
Определение складных
class Foldable t where
{-# MINIMAL foldMap | foldr #-}
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
-- and a number of optional methods
Интуитивно (хотя и не технически), Foldable
структуры представляют собой контейнеры элементов a
которые обеспечивают доступ к их элементам в четко определенном порядке. Операция foldMap
сопоставляет каждый элемент контейнера с Monoid
и сворачивает их с использованием структуры Monoid
.
Проверка того, что Складная структура пуста
null
возвращает True
если в складной структуре ta
нет элементов a
и False
если есть один или несколько. Структуры, для которых null
имеет значение True
имеют length
0.
ghci> null []
True
ghci> null [14, 29]
False
ghci> null Nothing
True
ghci> null (Right 'a')
False
ghci> null ('x', 3)
False
null
определяется как эквивалентное:
class Foldable t where
-- ...
null :: t a -> Bool
null = foldr (\_ _ -> False) True