Haskell Language
折りたたみ可能

前書き

備考

Foldable構造の要素を数える

lengthは、折りたたみ可能構造体ta内の要素aの発生をカウントする。

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モノイドの助けを借りて反対方向に走らせることができます。 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で定義されてい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リストにS。 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 (:) []

Foldable構造の各要素に対して副作用を実行する

traverse_は、 Foldable構造内のすべての要素に対してApplicativeアクションを実行しApplicative 。アクションの結果は無視され、副作用のみが保持されます。 （結果を破棄しないバージョンの場合は、 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_は、 Applicativeなアクションが完全に折りたたまれた状態で単一のアクションにFoldable 、結果は無視します。

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

Foldableの定義

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は折り畳み構造体taに要素aがない場合はTrue返し、1つ以上ある場合は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は以下と等価であると定義されnull 。

class Foldable t where
    -- ...
    null :: t a -> Bool
    null = foldr (\_ _ -> False) True