我正在尝试编写使用幺半群和可折叠来添加和乘以列表中所有元素的函数。我已经设置了一些我认为有效的代码:
data Rose a = a :> [Rose a]
deriving (Eq, Show)
instance Functor Rose where
fmap f rose@(a:>b) = (f a :> map (fmap f) b)
class Monoid a where
mempty :: a
(<>) :: a -> a -> a
instance Monoid [a] where
mempty = []
(<>) = (++)
newtype Sum a = Sum { unSum :: a } deriving (Eq, Show)
newtype Product a = Product { unProduct :: a } deriving (Eq, Show)
instance Num a => Monoid (Sum a) where
mempty = Sum 0
Sum n1 <> Sum n2 = Sum (n1 + n2)
instance Num a => Monoid (Product a) where
mempty = Product 1
Product n1 <> Product n2 = Product (n1 * n2)
class Functor f => Foldable f where
fold :: Monoid m => f m -> m
foldMap :: Monoid m => (a -> m) -> f a -> m
foldMap f a = fold (fmap f a)
instance Foldable [] where
fold = foldr (<>) mempty
instance Foldable Rose where
fold (a:>[]) = a <> mempty
fold (a:>b) = a <> (fold (map fold b))
然后在定义了不同的 Foldable 实例以及 Sum 和 Product 类型之后,我想定义两个函数,分别将数据结构中的元素相加,但这会产生我不知道如何解释的错误,我必须承认我认为这更多的是猜测工作而不是实际逻辑,因此欢迎对您的答案进行彻底解释。
fsum, fproduct :: (Foldable f, Num a) => f a -> a
fsum b = foldMap Sum b
fproduct b = foldMap Product b
错误:
Assignment3.hs:68:14: error:
* Occurs check: cannot construct the infinite type: a ~ Sum a
* In the expression: foldMap Sum b
In an equation for `fsum': fsum b = foldMap Sum b
* Relevant bindings include
b :: f a (bound at Assignment3.hs:68:6)
fsum :: f a -> a (bound at Assignment3.hs:68:1)
|
68 | fsum b = foldMap Sum b
| ^^^^^^^^^^^^^
Assignment3.hs:69:14: error:
* Occurs check: cannot construct the infinite type: a ~ Product a
* In the expression: foldMap Product b
In an equation for `fproduct': fproduct b = foldMap Product b
* Relevant bindings include
b :: f a (bound at Assignment3.hs:69:10)
fproduct :: f a -> a (bound at Assignment3.hs:69:1)
|
69 | fproduct b = foldMap Product b
| ^^^^^^^^^^^^^^^^^
最佳答案
如果您在 foldMap
中使用 Sum
(或 Product
),您将首先映射中的项目将 Foldable
转换为 Sum
(或 Product
)。因此,fsum
的结果 - 就像您定义的那样 - 是 Sum a
,而不是 a
:
fsum :: (Foldable f, Num a) => f a -> <b>Sum a</b>
fsum b = foldMap Sum b
为了检索封装在 Sum
构造函数中的值,您可以使用 unSum::Sum a -> a
getter 获取它:
fsum :: (Foldable f, Num a) => f a -> <b>a</b>
fsum b = <b>unSum (</b>foldMap Sum b<b>)</b>
或者在eta减少之后:
fsum :: (Foldable f, Num a) => f a -> a
fsum = unSum . foldMap Sum
对于产品
也应该发生同样的情况。
关于haskell - 可折叠和幺半群类型,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52779202/