haskell - 检查 Haskell 中的空列表 : Is (length list == 0) or (list == []) more efficient?

Question

假设我想检查 Haskell 中的守卫中的列表是否为空，有两个选项:

1. 长度列表 == 0
2. 列表==[]

这两个逻辑测试哪一个更有效？我倾向于说空列表测试，因为它依赖于更基本的构造，而不是前奏函数 length 但我不确定。

Answer 1

length list == 0需要遍历整个列表才能得到它的长度，也就是说它的长度是O(n)。 list == [] 产生对元素类型的 Eq 约束。 空列表 在恒定时间内运行，并且没有类型类约束。

但是，有一个巧妙的技巧可以执行诸如 length list == 0 之类的操作，其优点是它可以很好地概括为 length list1 == length list2 而无需继续通过较长的列表:您可以使用 genericLength使用足够惰性的自然数表示，以便比较只会强制遍历较短的列表。

一个例子是使用 the Natural type :

import Data.Number.Natural
import Data.List (genericLength)

nats :: [Int]
nats = iterate succ 0

areThereTenNats :: Bool
areThereTenNats = genericLength nats >= (10 :: Natural)