时间戳

首页 > 解决方案 > 如何通知 GHC 特定模式匹配是不可能的（例如：列表永远不会为空）？

haskell - 如何通知 GHC 特定模式匹配是不可能的（例如：列表永远不会为空）？

问题描述

我定义了selectionSort函数，如下所示，对空列表进行排序只会产生一个空列表，对非空列表进行排序是最小元素和列表其余部分的排序版本的缺点。

selectionSort :: Ord a => [a] -> [a]
selectionSort xs
  | null xs = []
  | otherwise = minElem : (selectionSort ys)
    where
      (minElem, ys) = minf xs
        where
          minf [x] = (x, [])
          minf (x:xs) = let (m ,ms) = minf xs in
            if x <= m then (x, xs)
            else (m, x:ms)

minf接受一个非空列表并返回一个包含最小值和列表其余部分的元组。

当我用 -W 标志编译这个函数时，我得到这个警告

warning: [-Wincomplete-patterns]
Pattern match(es) are non-exhaustive
In an equation for `minf': Patterns not matched: []
    |
 24 |             minf [x] = (x, [])
    |             ^^^^^^^^^^^^^^^^^^...

直截了当，该函数minf永远不会应用于空列表，因为这些情况被捕获在null xs = []. 有没有办法通知 GHC 如果不使用其他类型（NonEmpty列表类型）或Maybes ，特定情况是不可能的

标签： haskell

解决方案

通常的想法是“设计”类型，使“不可能的模式”的数量非常少（最好为零）。

作为穷人解决方案，您可以从以下位置重写函数的签名：

foo :: [a] -> b  -- [a] is a non-empty list

至：

foo :: a -> [a] -> b  -- head and tail as input

因此，在这种情况下，我们可以将您的函数重写为：

selectionSort :: Ord a => [a] -> [a]
selectionSort [] = []
selectionSort (x:xs) = minElem : selectionSort ys
    where (minElem, ys) = minf x xs
          minf z [] = (z, [])
          minf z za@(z2:zs) = let (m, ms) = minf z2 zs in
              if z <= m then (z, za)
              else (m, z:ms)

所以我们这里使用第一个参数作为列表的头部，第二个作为尾部。由于列表至少包含一个元素，这意味着尾部可以为空，因此我们可以进行模式匹配。结果，我们仍然可以使用该-Wincomplete-patterns标志来检查是否所有模式都被覆盖，因此我们仍然可以得到编译器的一些保证。

如果您仍然无法正确设计类型，您可以添加模式并引发（验证）错误：

minf [] = error "Impossible: minf only works with a non-empty list"

推荐阅读