`

haskell - Functors, Applicative Functors and Monoids - Monoids application

阅读更多

we have introduced monoids before, and in this post, we will continue to examine the usage of monoids, we will continue this post with introduction on the some datascture implemented with monoids, such as tree....

 

in this post we will discuss something that is related to the Monoid with the fold data structure. 

 

One of the more interesting ways to put monoids to work  is to make them help us define folds over various data structures. 

 

Fold can work over alomst any data structure, Trees especially lend themeselves well to folding. 

 

In fact, there is a Foldable type class was introduced. 

 

to use that, you can do like this:  

import qualified Foldable as F  

 

function that may comes handy are included as follow. 

 

foldr, foldl, foldr1 and foldl1

 

let's compare the Prelude.Foldr and hte Foldable.foldr, 

ghci> :t foldr  
foldr :: (a -> b -> b) -> b -> [a] -> b  
ghci> :t F.foldr  
F.foldr :: (F.Foldable t) => (a -> b -> b) -> b -> t a -> b 

 

as  you can see that the foldr in the Prelude is used for the list type, while the foldr is used for almost any types. 

 

some of the test comparision of the two is like this: 

 

 

ghci> foldr (*) 1 [1,2,3]  
6  
ghci> F.foldr (*) 1 [1,2,3]  
6  

ghci> F.foldl (+) 2 (Just 9)  
11  
ghci> F.foldr (||) False (Just True)  
True  

 

 

Now let's make some type part of the Foldable, so that we can do foldx on the customized types.  remember the types that we have showed before like this:

 

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)  

 

 suppose that we are going to make a visiting procedure that visit the tree, here is the code. 

 

before going to the real code, we will first visit the code which we will use to help us..  It is the FlatMap method. 

 

 

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m  
this is a function which takes as its first parameter of the type that our foldable stucture contains, and returns a monoid,. and the second type is a  foldable structure that contains values of type a. It maps that function over the foldable structure, thus producing a foldable structure that contains monoid values. Then, by doing mappend between those monoid values, it joins them all into a single monoid value. 
so to make the Tree part of foldable, here is the code. 
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  
 
so what can we do wih that ?
suppose that we have a tree like this:  
testTree = Node 5  
            (Node 3  
                (Node 1 Empty Empty)  
                (Node 6 Empty Empty)  
            )  
            (Node 9  
                (Node 8 Empty Empty)  
                (Node 10 Empty Empty)  
            )  
 so the following will show what you can do with it..
-- to sum
ghci> F.foldl (+) 0 testTree  
42  
-- to foldr and apply product
ghci> F.foldl (*) 1 testTree  
64800   
-- if there is any element that has value of 3
ghci> getAny $ F.foldMap (\x -> Any $ x == 3) testTree  
True  
-- list is monoid, so you can visit the tree and get the element along the tree. 
ghci> F.foldMap (\x -> [x]) testTree  
[1,3,6,5,8,9,10]  
 

 

 

 

 

 

 

分享到:
评论

相关推荐

    Haskell趣学指南---文字版.pdf

    第十一章讨论了Functors、Applicative Functors、Monoids,它们是构建复杂函数式程序的基础。通过理解Monoids和其在数据结构折叠(Folding)中的应用,读者可以学习到如何将数据结构聚合成单一值。 第十二章开始,...

    B10-Haskell趣学指南.pdf

    本章重温了Functor的概念,并介绍了Applicative Functors和Monoids,这些都是Haskell中处理数据结构和组合函数的强大工具。通过使用Monoids,我们能高效地折叠(fold)数据结构。 ### 第十二章与第十三章:来看看几...

    Haskell趣学指南

    #### 十一、Functors, Applicative Functors与Monoids - **Functors**:介绍Functor类型类及其应用。 - **Applicative Functors**:讲解Applicative Functor类型类及其在函数式编程中的作用。 - **Monoids**:学习...

    LtuPatternFactory:最终的Lambda模式工厂:FP,Haskell,Typeclassopedia与软件设计模式

    5. **Monoids**:Monoids是一类具有结合性和单位元的数据结构,例如整数加法或字符串连接。它们在FP中广泛用于聚合和组合操作。 6. **Monad Transformers**:Monad Transformer允许我们将不同类型的Monad组合在一起...

Global site tag (gtag.js) - Google Analytics