为什么Foldable和Functor分开了？

Question

该wiki页面说这两类处理集装箱业务,与折叠是一类已经容器foldr在他们定义和函子是fmap.

但是,可折叠类型和Functors类型之间的根本区别是什么？

维基暗示了这种区别:

类[可折叠]类不需要Functor超类,以允许容器如Set或StorableVector

但是我仍然不确定如果我正确地解释了为什么Set无法映射到另一个集合.

Answer 1

Foldable并Functor为具有可折叠(或缩小)和映射的结构的类型提供两个单独的抽象.

可折叠值包含可以枚举并组合在一起的值¹.人们可以将Foldable视为可以转化为列表的东西(toList :: Foldable f => f a -> [a]).或者,可以将Foldables视为其值可以单独组合的结构:( (Foldable t, Monoid m) => (a -> m) -> t a -> m当然,这需要能够枚举它们).

另一方面,函数是允许人们"提升"函数(a -> b)以应用于a结构(fmap :: (a -> b) -> (f a -> f b))所持有的s的结构.fmap必须保留被映射的结构:树之前和之后必须具有相同的形状,列表必须具有相同顺序的元素数量,Nothing不能变成某些东西,依此类推.另一方面,Foldables不需要保留这种结构; 重点是丢弃结构并生成新结构.

Wiki指的是无法提供类型类约束的事实fmap.fmap :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b不与类定义的类型统一,fmap :: (a -> b) -> f a -> f b没有约束.这使得一个实例Set无法编写.

但是,这只是一个语言实现问题,而不是关于集合的更深入的数学陈述.Foldable没有Functor超类的真正原因只是有可折叠的实例而不是Functor实例.

1. "保持"有点松散,意图在"Functors are containers"意义上解释,其中Proxy s a保持零a,Identity a保持一个a,Maybe a保持零或一个a,b -> a保持|b|一个,等等.

Answer 2

假设我有xs :: Set Int,我想putStrLn在它上面映射函数.这将是一个问题,因为IO ()没有Ord实例,因此无法弄清楚如何将这些操作插入到结果集中.fmap叶子的类型没有限制类型参数的约束Functor.

IO也提供了一个例子,Functor但没有任何有意义的方法foldMap.

值得一提的是Foldable,Functor在Traversable课堂上聚集在一起,这比任何一个都要强大得多.

Answer 3

Set并且StorableVector 是仿函数,你确实可以在它们上面映射函数.

但不是任何一种功能.例如,你不能映射(+)一个StorableArray数字:这将给出一系列函数,而这些函数是不可存储的.

因此,这些函子不是所有Hask上的(endo)仿函数,而是仅包含特定类的类型的子类别.这在Haskell98中无法表达,事实上,随着约束种类的出现,它最近才成为可能.看这个例子:

instance Functor Set Ranking Ranking where
  fmap = constrainedFmap Set.map

实际上,如果你使用一些聪明的GADT技巧,套装也会在Hask中形成一个monad .但这对所有容器都不可能,因此标准库不需要.FoldableFunctor f => Foldable f

Answer 4

该Functor类型类不会让你fmap过的东西,对他们的类型元素的限制.Set要求Ord和StorableVector要求Storable.

可以使用GHC的ConstraintKinds扩展来表达"受约束的函子" ,例如:

{-# LANGUAGE ConstraintKinds,
             FunctionalDependencies,
             MultiParamTypeClasses #-}

import GHC.Exts (Constraint)
import Data.Set (Set)
import qualified Data.Set as Set

class ConstrainedFunctor c f | f -> c where
  cfmap :: (c a, c b) => (a -> b) -> f a -> f b

instance ConstrainedFunctor Ord Set where
  cfmap = Set.map

但是这个机器在Functor第一次出现时并不存在.

此外,Functor应该是"保持形状",但例如在a上的映射Set可能会改变其大小.