Как проверить равенство рекурсивных структур?

Question

Я хотел бы 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 с, что заканчивает сведение к typeCheck numberList numberList снова; очевидная бесконечная рекурсия. Вам нужно будет перестроить свой тип данных, чтобы представить этот тип округлости явно, если вы хотите, чтобы у них была возможность проверить их на равенство. Например, вы могли бы добавить обязательную форму, как

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