Haskell 空列表的潜在解决方法问题

Question

我定义了一个接收数据类型和列表的函数。

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 0 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

我遍历这个函数，传递 index 的 tail 有 3 种可能 returns：如果列表的长度小于或等于 1 它 returns x（存储在节点中的值）如果不是它检查索引的头部并调用 getAux索引的尾部。

我尝试通过在调用 getAux 时向索引末尾添加一个额外元素来解决此问题。 我没有比较索引的长度是否等于 0，而是将其与 1 进行比较。

当我调用函数时：

getAux (Nodo x iz de) (num2bin(index) ++ [True])

新的 getAux 是：

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 1 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

在这两种情况下，我都收到一条错误消息，指示我无法执行空列表的头部

Answer 1

你用 tail index 调用它，因此最终你到达空列表，因此这解释了为什么后者，如果 length index == 1 失败，它将尝试访问 head index 和因此错误。

但是使用 length 不是一个好主意，因为它在 O(n) 中运行，长度为 n列表，通常在列表上执行模式匹配比使用 head 和 tail 更好，因为这样可以保证列表具有 head 和 tail.

因此您可以将其实现为：

getAux :: SparseArray a -> [Bool] -> Value a
getAux (Node x _ _) [] = x
getAux (Node _ left right) (x:xs)
  | x = getAux right xs
  | otherwise = getAux left xs

通过为编译器启用 -Wincomplete-patterns ^{[Haskell-docs]}，它会警告您函数未涵盖的模式。例如，如果您的 SparseArray 有一个额外的数据构造函数，那么这些情况还没有涵盖（还）。

Haskell 空列表的潜在解决方法问题

Haskell problem with potential workaround for empty lists

haskell

list