为什么Haskell [](列表)不是类型类? [英] Why is Haskell [] (list) not a type class?

问题描述

我正在编写一个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?

推荐答案

给定的代数数据类型可以表示为其同构，即称为

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.

关于您的疑虑:

这不像Foldable具有功能head/tail/isEmpty，这是我会更直观地看到的.

It's not like Foldable has functions head/tail/isEmpty, which is what I would find more intuitive.

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都必然在结构上类似于列表(例如

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 定义了

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 [](列表)不是类型类?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！