Liquid Haskell: ошибка "Определение псевдонима циклического типа" из встроенной рекурсивной функции

Question

Я написал некоторый код для выполнения порядковой арифметики в Haskell и теперь пытаюсь использовать Liquid Haskell для проверки определенных свойств. Однако у меня возникают проблемы с "отражением" рекурсивных функций. Я выделил проблему в функции "меньше чем" ниже:

-- (Ord a n b) = a^n + b
{-@ data Ordinal [size] = Ord { a :: Ordinal, n :: Nat,  b :: Ordinal }
                        | Zero {} @-}
data Ordinal = Ord Ordinal Integer Ordinal
             | Zero
             deriving (Eq, Show)

{-@ measure size @-}
{-@ size :: Ordinal -> Nat @-}
size :: Ordinal -> Integer
size Zero = 1
size (Ord a n b) = (size a) + 1 + (size b)

{-@ inline ordLT @-}
ordLT :: Ordinal -> Ordinal -> Bool
ordLT _ Zero = False
ordLT Zero _ = True
ordLT (Ord a0 n0 b0) (Ord a1 n1 b1) =
    (ordLT a0 a1) || 
    (a0 == a1 && n0 < n1) || 
    (a0 == a1 && n0 == n1 && ordLT b0 b1)

one = (Ord Zero 1 Zero)     -- 1
w   = (Ord one 1 Zero)      -- omega
main = print w              -- Ord (Ord Zero 1 Zero) 1 Zero

проведение liquid ordinals.hs только с вышеупомянутым выдает следующую ошибку:

Error: Cyclic type alias definition for `Main.ordLT`
14 |     {-@ inline ordLT @-}
                     ^^^^^
The following alias definitions form a cycle:
* `Main.ordLT`

Итак, как правильно отразить рекурсивные функции? Я читал учебник по жидкому хаскеллу, но не могу понять, что его примеры делают по-другому.

Answer 1

Немного сложно быть уверенным в том, что ты хочешь делать без контекста, но inline действительно не работает с рекурсивными функциями: inline позволяет использовать функцию в типе , расширяя ее во время компиляции (перед созданием условия проверки, отправляемого решателю), поэтому необходимо иметь возможность заменять каждое вхождение ordLT a b по какой-то определенной логической формуле (что невозможно, так как это рекурсивно).

Если вам нужно иметь возможность использовать произвольные функции Haskell в логике, вы можете изучить использование Refinement Reflection. Ваш пример компилируется с {-@ reflect ordLT @-} а также {-@ LIQUID "--exact-data-cons" @-}, Однако символы функций, созданные с помощью уточненного отражения, не полностью интерпретируются в логике. Все подробности обсуждаются в этой статье, а более доступные примеры / объяснения представлены на этих слайдах и в этом блоге. Главное помнить, что ordLT Символ, созданный отражением, вначале будет рассматриваться как совершенно не интерпретируемая функция в логике: единственное, что LH знает о нем, это что-то вроде a0 == a1 ==> b0 == b1 ==> ordLT a0 b0 == ordLT a1 b1 (если вы называете это на идентичных входах, результаты идентичны).

Для того, чтобы сделать что-то полезное с ordLT в логике нужно будет позвонить ordLT на уровне значений где-то в области видимости, которая покажет значение этого конкретного вызова, так как тип возвращаемого значения ordLT (функция уровня значения) утверждает что-то о выводе ordLT (неинтерпретируемая функция логического уровня) на этих входах. Примеры приведены в слайдах, связанных выше, и в документе. Надеюсь, этого достаточно, чтобы вы начали!