问题描述
我正在编写一个Haskell函数，该函数将一个列表作为输入.也就是说，没有理由它不能成为队列或出队，也不能使我能够访问其头部"和尾部"(并检查其是否为空).因此[a]输入类型似乎太具体了.但是AFAIK没有标准库类型类可以完全捕获此接口.当然，我可以将函数包装在Data.Foldable.toList中，并使其变为可折叠的多态，但这似乎不太正确(习惯用法).
I am writing a Haskell function which takes a list as input. That is, there's no reason it couldn't be a queue or dequeue, or anything that allows me to access its "head" and its "tail" (and check if it's empty). So the [a] input type seems too specific. But AFAIK there's no standard library typeclass that captures exactly this interface. Sure, I could wrap my function in a Data.Foldable.toList and make it polymorphic wrt Foldable, but that doesn't quite seem right (idiomatic).
为什么没有标准的列表类型类? (为什么Haskell中的容器"类型类层次结构没有我想象的那么发达?)还是我错过了一些必不可少的东西?
Why is there no standard list type class? (And why is the "container" type class hierarchy in Haskell less developed than I think it should be?) Or am I missing something essential?
推荐答案
给定的代数数据类型可以表示为其同构，即称为 教会编码 .这意味着列表与其foldr同构:
A given algebraic datatype can be represented as its catamorphism, a transformation known as Church encoding. That means lists are isomorphic to their 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的特征.您可以根据foldr定义foldMap，反之亦然.
But foldr also characterises Foldable. You can define foldMap in terms of foldr, and vice versa.
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类型的结构至少与列表相同.
(It shouldn't be surprising that foldMap :: Monoid m => (a -> m) -> [a] -> m characterises lists, because lists are a free monoid.) In other words, Foldable basically gives you toList as a class. Instances of Foldable have a "path" through them which can be walked to give you a list; Foldable types have at least as much structure as lists.
关于您的疑虑:
null :: Foldable t => t a -> Bool 是您的isEmpty，您可以使用 的适当选择:
null :: Foldable t => t a -> Bool is your isEmpty, and you can define (a safe version of) head straightforwardly with an appropriate choice of Monoid:
head :: Foldable t :: t a -> Maybe a
head = getFirst . foldMap (First . Just)
我认为
tail有点棘手.对于任意类型，tail甚至意味着什么都不是很明显.您当然可以编写tail :: Foldable t => t a -> Maybe [a](通过toList进行排序，然后再取消一致)，但是我认为定义了tail :: T a -> Maybe (T a)的任何类型T都必然在结构上类似于列表(例如 Seq ).此外，根据我的经验，绝大多数情况下，您认为需要访问列表的tail毕竟是折叠的.
tail is kinda tricky in my opinion. It's not obvious what tail would even mean for an arbitrary type. You can certainly write tail :: Foldable t => t a -> Maybe [a] (by toListing and then unconsing), but I think any type T for which tail :: T a -> Maybe (T a) is defined would necessarily be structurally similar to lists (eg Seq). Besides, in my experience, the vast majority of cases where you'd think you need access to a list's tail turn out to be folds after all.
也就是说，对不稳定类型的抽象有时是有用的.例如， megaparsec 定义了 Stream 类(单态)令牌流用作解析器的输入.
That said, abstracting over unconsable types is occasionally useful. megaparsec, for example, defines a Stream class for (monomorphic) streams of tokens to be used as input for a parser.
这篇关于为什么Haskell [](列表)不是类型类?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！