haskell - 如何测试递归结构的相等性？

Question

我想typeCheck两个 numberList s。这会导致无限循环。有什么解决方案可以解决我的问题？

data Type =
    Function Type Type |
    Number |
    Tuple [Type] |
    Limited [Type]
        deriving (Show, Eq)

-- type x is of type y
typeCheck :: Type -> Type -> Bool
typeCheck x y = case y of

    Function ya yr -> case x of
        Function xa xr -> typeCheck xa ya && typeCheck xr yr
        _ -> False


    Number -> x == Number 

    Tuple ys -> case x of 
        Tuple xs | length xs == length ys -> 
            all (==True) $ zipWith typeCheck xs ys
        _ -> False

Limited ys -> case x of
    Limited xs | length ys >= length xs -> 
        all (==True) $ zipWith typeCheck xs ys
    _ -> any (==True) $ map (typeCheck x) ys

{- 
 - A list of numbers can be represented as follows
 - () empty list
 - (1, ()) [1]
 - (1, (2, (3, ()))) [1,2,3]
-}

numberList = Limited [ Tuple [], Tuple [ Number, numberList ] ]

Answer 1

问题是你递归遍历结构，直到到达 Tuple 的最后一个元素。 s，最终减少到 typeCheck numberList numberList再次;一个明显的无限递归。如果您希望能够检查它们是否相等，则必须重新构造您的数据类型以明确表示这种循环。例如，您可以添加一个绑定(bind)表单，例如

Recursive "numberList" $ Limited [Tuple [], Tuple [Number, Var "numberList"]]

或者，使用 De Bruijn indices (更容易以编程方式处理，为人类编写更尴尬):

Recursive $ Limited [Tuple [], Tuple [Number, Var 0]]

这将需要您在 typeChecks 中随身携带一个堆栈。 ，以便您可以检测到例如

typeChecks' [("numberList", ...)] (Var "numberList") (Var "numberList")

并将其解析为 True .

顺便说一句， all (==True) ≡ all id ≡ and ; any (==True) ≡ any id ≡ or .

顺便说一句，您的功能可以大大简化，并避免大部分额外的 length检查，通过使用模式匹配和手动递归 typeChecks确保两个列表具有相同长度的函数:

typeCheck :: Type -> Type -> Bool
typeCheck (Function as rs) (Function as' rs') =
  typeChecks as as' && typeChecks rs rs'
typeCheck Number Number = True
typeCheck (Tuple xs) (Tuple ys) = typeChecks xs ys
typeCheck x@(Limited xs) (Limited ys)
  | length ys >= length xs = and $ zipWith typeCheck xs ys
  | otherwise = any (typeCheck x) ys
typeCheck _ _ = False

typeChecks :: [Type] -> [Type] -> Bool
typeChecks [] [] = True
typeChecks (x:xs) (y:ys) = typeCheck x y && typeChecks xs ys
typeChecks _ _ = False