Haskell/Solutions/Foldable
1.
-- We start from:
foldMap g = mconcat . fmap g
foldMap g = foldr mappend mempty . fmap g -- mconcat definition
-- Which can be simplified to:
foldMap f = foldr (mappend . f) mempty
-- Or, more pointfully:
foldMap f xs = foldr (\x z -> f x <> z) mempty xs
-- Alternatively (via the definition of foldr):
foldMap _ [] = mempty
foldMap g (x:xs) = g x <> foldMap g xs
1.
答案的总结。微妙的问题在下面的笔记中解释。
| 折叠 | mempty
|
mappend
|
初步 函数 |
newtype 来自Data.Monoid |
笔记 |
|---|---|---|---|---|---|
product |
1 |
(*) |
乘积 |
||
concat |
[] |
(++) |
|||
concatMap f |
[] |
(++) |
f |
||
all p |
True |
(&&) |
p |
All |
|
elem x |
False |
(||) |
(== x) |
Any |
|
length |
0 |
(+) |
const 1 |
Sum |
|
traverse_ f |
pure () |
(*>) |
void . f |
参见 [i] | |
mapM_ f |
return () |
(>>) |
void . f |
参见 [i] | |
safeMaximum |
Nothing |
max' Nothing m = m max' m Nothing = m max' (Just x) (Just y) = Just (max x y) |
参见 [ii] | ||
find p |
Nothing |
最左边的 Just |
\x -> if p x then Just x else Nothing |
First |
参见 [iii] |
composeL f |
id |
flip (.) |
flip f |
Dual . Endo |
参见 [iv] |
笔记
[i]: 这里的 monoid 的类型为 Applicative f => f ()。函数 void（在 Data.Functor 中定义为 fmap (const ())）用于将操作的内部值转换为 ()，从而丢弃内部值。这种转换在基于 foldr 的实现中是不需要的（就像实际的实现一样）；然而，对于不是使用 Endo 的通用 foldMap，我们需要要么使用 void 丢弃结果（如上所示），要么创建一个忘记结果类型的包装器。后一种技巧（实际上是一种相当高级的技巧）使用了一个叫做 存在量化 的功能，可能看起来像这样
{-# LANGUAGE ExistentialQuantification #-} -- First line of the source file.
-- forall a. causes the type to be forgotten.
data NoResults f = forall a. NoResults (f a)
runNoResults :: Applicative f => NoResults f -> f ()
runNoResults (NoResults u) = const () <$> u
instance Applicative f => Monoid (NoResults f) where
mempty = NoResults (pure ())
NoResults u `mappend` NoResults v = NoResults (u *> v)
虽然这是一个时尚的解决方案，但它会产生很多问题 - 我们不能使用 newtype 或者记录，并且仍然需要一个 fmap (const ()) 来提取最终的操作。所以把这种方法仅仅当作一个好奇心来看待吧。
在更合理的情况下，mapM_ 只是在类型签名上与 traverse_ 不同，因为 return = pure 以及 (>>) = (*>)。这也意味着上述观察也适用于它。
[ii]: max :: Ord a => a -> a -> a 计算出两个参数中的较大值，而 max' :: Ord a => Maybe a -> Maybe a -> Maybe a 类似，但涉及 Maybe。这里使用 Maybe 只是一个技巧，为类型 a 添加一个额外的 Nothing 值，以便 max' 可以成为合法的 mappend。Nothing 作为 mempty，是 max' 的单位元，因此充当一个小于或等于 a 中所有值的值（例如，对于整数来说，就像负无穷大一样）。这个 monoid 可以用包装器 Max 实现如下（事实上，类似的东西被用于 Data.Foldable 中 maximum 的默认实现中）。
newtype Max a = Max { unMax :: Maybe a }
instance Ord a => Monoid (Max a) where
mempty = Max Nothing
Max Nothing `mappend` x = x
x `mappend` Max Nothing = x
Max (Just x) `mappend` Max (Just y) = Max $ Just $ max x y
-- safeMaximum can then be written
safeMaximum = unMax . foldMap (Max . Just)
注意，liftA2 max 不能用作 mappend，因为 liftA2 max Nothing x = Nothing，因此 Nothing 不是 liftA2 max 的单位元，如 monoid 法则要求的那样。
[iii]: “最左边的 Just” 意味着
Just x `mappendFirst` _ = Just x
_ `mappendFirst` Just y = Just y
_ `mappendFirst` _ = Nothing
镜像的替代方案是
_ `mappendLast` Just y = Just y
Just x `mappendLast` _ = Just x
_ `mappendLast` _ = Nothing
它们分别通过 Data.Monoid 中的 First 和 Last newtype 包装器实现。
[iv]: 这是 高阶函数 中 foldl 练习解决方案的简化版本。Dual 是一个 Data.Monoid 包装器，它会 flip 包装的 Monoid 的 mappend。
1a.
instance Foldable Tree where
foldMap f t = case t of
Leaf x -> f x
Branch tl tr -> foldMap f tl <> foldMap f tr
1b.
-- Using the catamorphism
-- treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeDepth :: Tree a -> Int
treeDepth = treeFold (\dl dr -> 1 + max dl dr) (const 0)
不可能使用 Foldable 来实现 treeDepth。像列表一样折叠树会破坏分支结构的信息。这可以通过找到一对结构不同但被 toList 转换为相同列表的树来清楚地显示。
1a.
instance (Monoid a, Monoid b) => Monoid (a,b) where
mempty = (mempty, mempty)
(x1, y1) `mappend` (x2, y2) = (x1 `mappend` x2, y1 `mappend` y2)
1b.
-- For given a and b
-- f :: (Monoid a, Monoid b) => a -> b
-- If f is a monoid homomorphism, then
-- f mempty = mempty
-- f (x <> y) = f x <> f y
fst (mempty, mempty) = mempty -- Target
fst (mempty, mempty) -- LHS
mempty -- Q.E.D
fst ((x1, y1) <> (x2, y2)) = fst (x1, y1) <> fst (x2, y2)
fst (x1 <> x2, y1 <> y2) = x1 <> x2
x1 <> x2 = x1 <> x2 -- Q.E.D
1c.
foldMap f &&& foldMap g = foldMap (f &&& g) -- Target
-- f &&& g = \x -> (f x, g x)
(\x -> (foldMap f x, foldMap g x)) = foldMap (\x -> (f x, g x)) -- Target 2
-- Target 2 holds if the following hold:
fst . (\x -> (foldMap f x, foldMap g x)) = fst . foldMap (\x -> (f x, g x)) -- Target 3a
snd . (\x -> (foldMap f x, foldMap g x)) = snd . foldMap (\x -> (f x, g x)) -- Target 3b
-- From Target 3a, using the monoid homomorphism property:
fst . (\x -> (foldMap f x, foldMap g x)) = foldMap (fst . (\x -> (f x, g x)))
foldMap f = foldMap f -- OK
-- From Target 3b, using the monoid homomorphism property:
snd . (\x -> (foldMap f x, foldMap g x)) = foldMap (snd . (\x -> (f x, g x)))
foldMap g = foldMap g -- OK
-- Q.E.D (both Target 3a and Target 3b hold.)