我有这个函数:
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,但我认为这并不会改变任何东西。
我有这个函数:
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,但我认为这并不会改变任何东西。
Ord a => [a] -> [b]
类型在内部是一致的!
问题在于你从未将任何输入列表中的元素添加到输出列表中。你需要一个基本情况;像foo [x] = [x]
这样的东西。目前为止,你从未说过任何来自输入列表的元素会被添加到输出列表中;这个函数的结果将始终是[]
,它可以具有[b]
类型,而不考虑输入。
如果你在这里尝试实现像快速排序之类的东西,那么你的实现中存在两个逻辑问题:
x
,即枢轴,并没有被添加到输出列表中。x
本身之外,列表中与x
相等的任何值都将被添加两次,一次来自us
,一次来自ys
。