Haskell Language
접을 수있는

소개

비고

Foldable 구조의 요소 계산하기

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 모노 노이드 의 도움으로 반대 방향으로 진행될 수 있습니다 . 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 호출의 기본 모노 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 목록에 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 액션을 실행합니다. 액션의 결과를 무시하고 부작용 만 유지합니다. 결과를 무시하지 않는 버전의 경우 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

Foldable 구조를 Monoid로 전개

foldMap (A)에 상기 폴딩 구조의 각 요소를 매핑 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 요소 a 컨테이너입니다. foldMap 작동은 용기의 각 요소에 매핑 Monoid 상기 사용하여 축소 Monoid 구조.

Foldable 구조체가 비어 있는지 확인하기

null 은 foldable 구조체 ta 에 요소 a 가 없으면 True 반환하고, 하나 이상 있으면 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