自定义函数

Question

的类型检查我得到这个功能：

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

类型此函数的是一个奥德=>并[a] - >并[b]。

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

我正在使用拥抱，但我不认为它会改变任何东西。

Answer 1

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

问题是，您从来没有实际将任何元素从输入列表添加到输出列表。你需要一个基础案例;像foo [x] = [x]。就目前而言，你绝对不会说输入列表中的任何元素都会被添加到输出列表中;该函数的结果将始终为[]，无论输入如何，该函数的类型都可以是[b]。

如果你想在这里实现类似快速排序，不过，也有在您的实现两个逻辑问题：

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