自定义函数的类型检查

Question

我有这个函数：

foo [] = []
foo (x:xs) = foo us ++ foo ys
where us = filter (<=x) xs
      ys = filter (>=x) xs

该函数的类型是 Ord a => [a] -> [b]。

我不理解为什么输出类型是 [b] 而不是 [a]。我认为应该是 [a]，因为输出列表中的元素将是输入列表元素的一部分。

我正在使用 Hugs，但我认为这并不会改变任何东西。

- chechn

Answer 1

Ord a => [a] -> [b]类型在内部是一致的！

问题在于你从未将任何输入列表中的元素添加到输出列表中。你需要一个基本情况；像foo [x] = [x]这样的东西。目前为止，你从未说过任何来自输入列表的元素会被添加到输出列表中；这个函数的结果将始终是[]，它可以具有[b]类型，而不考虑输入。

如果你在这里尝试实现像快速排序之类的东西，那么你的实现中存在两个逻辑问题：

1. x，即枢轴，并没有被添加到输出列表中。
2. 除了x本身之外，列表中与x相等的任何值都将被添加两次，一次来自us，一次来自ys。

- Louis Wasserman

---

我会把这个问题添加到我的列表中。这个列表包含了如果编译器可以警告那些类型签名不够多态化可能会发现的错误分类。 - jberryman

谢谢！实际上这只是一个练习，我需要弄清楚类型。我没有使用那个特定的函数。 - chechn