git.iko.soy/elk
on c19392f help sign in
elk/src/Type/Occurs.hs
62 lines 1.4 kB history raw
1{-# OPTIONS_GHC -Wall #-}
2{-# LANGUAGE OverloadedStrings #-}
3module Type.Occurs (occurs) where
5import qualified Data.Map.Strict as Map
7import Type.Type as Type
8import qualified Type.UnionFind as UF
12-- OCCURS
15occurs :: Type.Variable -> IO Bool
16occurs var =
17 occursHelp [] var
20occursHelp :: [Type.Variable] -> Type.Variable -> IO Bool
21occursHelp seen var =
22 if elem var seen then
23 return True
25 else
26 do (Descriptor content _ _ _) <- UF.descriptor var
27 case content of
28 FlexVar _ ->
29 return False
31 FlexSuper _ _ ->
32 return False
34 RigidVar _ ->
35 return False
37 RigidSuper _ _ ->
38 return False
40 Structure term ->
41 let
42 go = occursHelp (var:seen)
43 in
44 case term of
45 App1 _ args ->
46 or <$> traverse go args
48 Fun1 a b ->
49 (||) <$> go a <*> go b
51 EmptyRecord1 ->
52 return False
54 Record1 fields ext ->
55 or <$> traverse go (ext : Map.elems fields)
57 Alias _ args _ ->
58 -- TODO is it okay to only check args?
59 or <$> traverse (occursHelp (var:seen) . snd) args
61 Error _ ->
62 return False