什么是措施？

Question

我正在阅读 this 我在哪里找到这个：

Measures -- In order to allow Haskell functions to appear in refinement types, we need to lift them to the refinement type level.

并且还有其他文件断言需要措施才能在合同中使用此类功能。但我试过这个：

{-@ len :: List a -> Nat @-}
len :: List a -> Int
len Nil           = 0
len (x `Cons` xs) = 1 + len xs

{-@ mymap :: (a -> b) -> xs : List a -> { ys : List b | len xs == len ys } @-}
mymap :: (a -> b) -> List a -> List b
mymap _ Nil           = Nil
mymap f (x `Cons` xs) = f x `Cons` mymap f xs

这有效，但 len 不是度量。那么究竟什么是衡量标准以及我何时需要它？

没有 measure 就无法工作的另一个例子：

{-@ measure ln @-}
ln :: [a] -> Int
ln [] = 0
ln (x:y) = 1 + ln y

{-@ conc :: xs : [a] -> ys : [a] -> {zs : [a] | ln zs == ln xs + ln ys} @-}
conc :: [a] -> [a] -> [a]
conc [] ys = ys
conc (x:xs) ys = x : (conc xs ys)

像我在许多文档中发现的那样使用 {-@ measure length @-} 会导致错误 Cannot extract measure from haskell function（即来自 length）。

Answer 1

度量只是一个函数，可以在验证时由 LiquidHaskell 运行用于改进和终止检查。你可能已经知道了。

你的第一个例子 "works" 的原因（我认为它不完整 as-is，但我可以告诉你要做什么）是 len 已经被定义为一个度量 in the LiquidHaskell prelude (technically it's a "class measure", which means it's polymorphic, and thus can be used both with [] lists and your custom List). Assuming you've added annotations for Nil and Cons as in 从你之前的问题来看，mymap的细化中使用的len不是你的len，而是前奏len，它已经是一个小节了。

在你的第二个例子中，measure 是必需的，因为 ln 是度量命名空间中的一个新符号，除非你创建它否则不存在。

什么是措施？

What is a measure?

haskell

liquid-haskell