2017-09-14 67 views
8

LYAH中,有一段代碼看起來像這樣。Foldable.foldl如何在數字a上工作=> a

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

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 

ghci> F.foldl (+) 0 testTree 
42 
ghci> F.foldl (*) 1 testTree 
64800 

據我所知,foldMapfoldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m類型,但Num a => a本身並不Monoid型的,所以我想知道如何Foldable.foldl實際上在這裏工作?由於foldMapFoldable.foldl在內部調用,因此Monoid的類型是什麼?

+0

嗨@WillemVanOnsem,謝謝你的幫助。這正是我所困惑的,你提到'mempty = 1',那麼這裏的'mempty'的類型是什麼?我不太明白這一點,因爲不像'Sum'和'Product','Int'不是類型'Monoid' AFAIK。你能解釋一下這個嗎?謝謝 –

+0

嗯,我明白了,我是Haskell的新手,我想那是我缺少的部分。非常感謝:) –

+1

請注意,這種技巧是非常先進的,肯定不是初學者的材料。編寫一個'foldl'實現可能更容易,它首先使用'foldMap(\ x - > [x])'將任何可摺疊的元素轉換爲普通列表,然後執行''a''' foldl'在名單上。效率較低,但可能更易於理解。它可以使一個很好的鍛鍊:) – chi

回答

9

如果您考慮foldr,它的類型爲(a -> b -> b) -> b -> t a -> b,這會更容易一點。 「代數」函數的類型爲a -> b -> b,您可以將其視爲a -> (b -> b) - 即:以a作爲輸入並返回b -> b作爲輸出的函數。

現在,b -> b自同態,這也是一個獨異,並Data.Monoid限定類型Endo a(或這裏,它應該可能是Endo b),這是,事實上,一個Monoid

foldr只需使用Endo內部調用foldMap

foldr :: (a -> b -> b) -> b -> t a -> b 
foldr f z t = appEndo (foldMap (Endo #. f) t) z 

foldl基本上只是翻轉的參數,以做同樣的伎倆各地:

foldl :: (b -> a -> b) -> b -> t a -> b 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

要清楚,我簡直複製這些來自Haskell源碼的兩個函數實現。如果您轉到documentation of Data.Foldable,可以通過各種鏈接查看源代碼。這就是我所做的。

+0

我看到,我實際上發現的源代碼的一部分,但無法理解'Endo'作爲我對Haskell的新角色,將讀更多關於這一點。非常感謝 :) –

相關問題