为什么Haskell [](列表)不是类型类？

Question

我正在编写一个Haskell函数,它以列表作为输入.也就是说,没有理由它不能成为队列或出队,或任何允许我访问其"头部"及其"尾部"(并检查它是否为空)的东西.所以[a]输入类型似乎太具体了.但是AFAIK没有标准的库类型类可以捕获这个接口.当然,我可以将我的函数包装在Data.Foldable.toList中并使其变为多态wrt可折叠,但这看起来不太正确(惯用).

为什么没有标准的列表类型类？(为什么Haskell中的"容器"类型层次结构比我认为应该更少？)或者我错过了必要的东西？

Answer 1

给定的代数数据类型可以表示为其变形,一种称为教会编码的变换.这意味着列表与它们同构foldr:

type List a = forall b. (a -> b -> b) -> b -> b

fromList :: [a] -> List a
fromList xs = \f z -> foldr f z xs

toList :: List a -> [a]
toList l = l (:) []

但foldr也有特色Foldable.您可以定义foldMap,foldr反之亦然.

foldMap f = foldr (mappend . f) mempty
foldr f z t = appEndo (foldMap (Endo . f) t) z

(foldMap :: Monoid m => (a -> m) -> [a] -> m列表的特征应该不足为奇,因为列表是一个免费的幺半群.)换句话说,Foldable基本上就是把你toList作为一个类.Foldable通过它们有一个"路径"的实例,可以走路给你一个列表; Foldable类型至少与列表一样多.

关于你的疑虑:

它不像Foldable函数head/ tail/ isEmpty,这是我会发现更直观的.

null :: Foldable t => t a -> Bool是你的isEmpty,你可以直接定义(一个安全的版本)head,并选择适当的Monoid:

head :: Foldable t :: t a -> Maybe a
head = getFirst . foldMap (First . Just)

tail在我看来有点棘手.tail对任意类型来说,甚至意味着什么并不明显.你当然可以写tail :: Foldable t => t a -> Maybe [a](由toList荷兰国际集团,然后unconsing),但我认为任何类型T为其tail :: T a -> Maybe (T a)定义必然是结构上类似于列表(例如Seq).此外,根据我的经验,绝大多数你认为你需要访问列表的情况tail毕竟是折叠.

也就是说,抽象不可靠的类型偶尔会有用.megaparsec例如,Stream为(单态)标记流定义一个类,用作解析器的输入.

Answer 2

问题

让你的问题更具体,让我们问:

为什么不是类型类

class HasHeadAndTail t where
    head :: t a -> Maybe a
    tail :: t a -> Maybe (t a)
    isEmpty :: t a -> Bool

在base图书馆？

一个答案

此类仅适用于有序的线性容器. Map,Set,HashMap,HashTable,和Tree所有不会的情况.我甚至反对制作Seq和DList实例,因为该结构实际​​上有两个可能的"头".

关于这个类的一个实例,我们还可以说什么呢？我认为唯一的财产是,如果isEmpty是假,则head和tail应是非Nothing.因此,isEmpty甚至不应该在类中,而是一个函数isEmpty :: HashHeadAndTail t => t a -> Bool ; isEmpty = isNothing . head.

所以我的答案是:

• 这个类在缺乏实例的情况下缺乏实用性.
• 这个类缺乏有用的属性,缺乏属性的类经常被劝阻.