无法证明过滤器功能的唯一细化类型

Question

我正在关注 LH tutorial 并坚持练习以改进过滤器函数的类型，如果使用具有唯一元素的列表调用，输出也是一个唯一列表独特元素。

这是我正在使用的代码：

import Data.Set hiding (insert, partition, filter, split, elems)

{-@ measure elts @-}
elts        :: (Ord a) => [a] -> Set a
elts []     = empty
elts (x:xs) = singleton x `union` elts xs

{-@ measure unique @-}
unique        :: (Ord a) => [a] -> Bool
unique []     = True
unique (x:xs) = unique xs && not (member x (elts xs))

{-@ filter' :: (a -> Bool) -> xs:[a] -> { l:[a] | unique xs => unique l } @-}
filter' _ []   = []
filter' f (x:xs)
  | f x       = x : xs'
  | otherwise = xs'
  where
    xs'       = filter' f xs

然而，当让 LH 证明它时，LH 抛出以下错误：

filter.hs:16:17-23: Error: Liquid Type Mismatch

 16 |   | f x       = x : xs'
                      ^^^^^^^

   Inferred type
     VV : {v : [a] | tail v == xs'
                     && head v == x
                     && listElts v == Set_cup (Set_sng x) (listElts xs')
                     && len v == 1 + len xs'
                     && Main.elts v == Set_cup (Set_sng x) (Main.elts xs')
                     && (Main.unique v <=> Main.unique xs'
                                           && not (Set_mem x (Main.elts xs')))
                     && len v >= 0}

   not a subtype of Required type
     VV : {VV : [a] | Main.unique ?a => Main.unique VV}

   In Context
     xs : {v : [a] | len v >= 0}

     xs' : {v : [a] | (Main.unique xs => Main.unique v)
                      && len v >= 0}

     x : a

     ?a : {?a : [a] | len ?a >= 0}

我已经尝试过以不同的方式指定它，在优化中使用 if 并使用不同的优化类型，但是 none 它似乎有效...

你能给我指明正确的方向吗？我仍然很难理解错误消息。据我了解，推断类型包含以下信息：如果 xs' 是唯一的，则它是唯一的，因此在我看来，这应该是所需类型的子类型。

Answer 1

抱歉耽搁了，我刚看到！（我倾向于更密切地监视松弛通道。）错误消息基本上是说 LH 无法证明输出列表 x:xs' 确实是唯一的。具体来说，LH 无法知道 x 还不是 xs'.

的元素

现在，为什么 x 不是 xs' 的元素？因为

(1) x 不是 xs 的元素 AND (2) xs' 是 xs

值的子集

如果输入列表是唯一的，LH 知道第一个属性。

但它不知道第二个。所以如果你把它添加到输出 filter 会有所帮助。

[顺便说一句，这是一个很好的问题；我会用提示更新教程]

无法证明过滤器功能的唯一细化类型

Can't prove unique refinement type for filter function

liquid-haskell