Haskell Language
складываемый

Вступление

замечания

Подсчет элементов Складной структуры

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