检查Haskell中的空列表:是(长度列表== 0)还是(列表== [])更有效？

Question

假设我想在Haskell中检查一个列表是否为空,有两个选项:

1. length list == 0
2. list == []

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

Answer 1

length list == 0需要遍历整个列表以获得其长度,这意味着它是O(n).对元素类型list == []产生Eq约束.null list以恒定时间运行并且没有类型类约束.

然而,有一个巧妙的做法,就是做一些length list == 0优点,它可以很好地概括,length list1 == length list2而无需通过更长的列表:你可以使用genericLength自然数字的足够懒惰的表示,以便比较只会强制遍历较短的列表.

一个例子是使用的Natural类型:

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

nats :: [Int]
nats = iterate succ 0

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

Answer 2

正如其他人指出的那样，检查列表是否为空（仅此而已）的最佳方法是使用

null :: Foldable f => f a -> Bool

可以在类型上使用

null :: [a] -> Bool

如果要检查列表是否为空是因为要查看其元素否则，通常应该使用模式匹配：

f [] = something
f (x : xs) = something using x and/or xs

如果您想比较两个列表的长度（没有更多），最好的方法通常是

compareLength :: [a] -> [b] -> Ordering
compareLength [] [] = EQ
compareLength [] (_ : _) = LT
compareLength (_ : _) [] = GT
compareLength (_ : xs) (_ : ys) =
  compareLength xs ys

检查列表长度与某个数字的比较的最佳方法是

compareToLength :: Foldable f
                => f a -> Int -> Ordering
compareToLength = foldr go (compare 0) where
  go _ r n | n <= 0 = GT
           | otherwise = r $! n - 1

Answer 3

您可以使用来检查您的列表是否在固定时间内为空null list，这将返回一个布尔值。

Prelude> null []
True
Prelude> null [1]
False
Prelude> null ""
True
Prelude> null "Test"
False