在Haskell中如何让校验逻辑的时间复杂度为O(1)而非O(n)？

优化方案 #

只需要调整你的模式匹配顺序，把负数校验放在所有分支的最前面即可：

get1 :: [a] -> Int -> a
-- 第一个分支直接判断n是否为负，完全不需要操作列表，O(1)完成校验
get1 _ n | n < 0 = error "Use positive numbers"
get1 [] _ = error "List is too small"
get1 (x:_) 0 = x
get1 (_:xs) n = get1 xs (n - 1)

原理说明 #

• Haskell的模式匹配按从上到下的顺序执行，只要前面的分支匹配成功就不会进入后续分支
• 你原有写法把空列表匹配放在了负数校验之前，存在两个问题：
  • 当传入空列表+负数参数时，会先触发「列表太小」的错误，不会走到负数校验逻辑
  • 如果你不小心把负数校验分支放在了递归分支后面，负数参数会跟着递归遍历完整个列表才会报错，时间复杂度退化为O(n)
• 优化后的第一个分支用通配符_匹配列表参数，不需要对列表做任何求值操作，只要参数n为负就立刻抛出错误，不管列表是空、有限长还是无限长，校验的时间复杂度都是O(1)

内容的提问来源于stack exchange，提问作者user17221096