haskell - 自定义函数的类型检查

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，但我认为它不会改变任何东西。

Answer 1

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

问题是您实际上从未将输入列表中的任何元素添加到输出列表中。您需要一个基本案例；类似的东西foo [x] = [x]。就目前而言，您实际上从未说过将输入列表中的任何元素添加到输出列表中。此函数的结果将始终为，无论输入如何[]，它都可以具有类型。[b]

但是，如果您尝试在此处实现类似 Quicksort 的功能，那么您的实现中有两个逻辑问题：

1. x，枢轴，不会被添加到输出列表中。
2. x列表中任何不等于x自身的值都将被添加两次，一次来自us，一次来自ys。