git.iko.soy/Idris-dev
on 012b595 help sign in
Idris-dev/src/Core/CaseTree.hs
187 lines 6.6 kB history raw
1module Core.CaseTree(CaseDef(..), SC(..), CaseAlt(..), CaseTree,
2 simpleCase) where
4import Core.TT
5-- import Core.Evaluate
7import Control.Monad.State
9data CaseDef = CaseDef [Name] SC
10 deriving Show
12data SC = Case Name [CaseAlt]
13 | STerm Term
14 | UnmatchedCase String -- error message
15 deriving Show
17type Const = Int -- TMP until constants implemented
19data CaseAlt = ConCase Name Int [Name] SC
20 | ConstCase Const SC
21 | DefaultCase SC
22 deriving Show
24type CaseTree = SC
25type Clause = ([Pat], Term)
26type CS = Int
28simpleCase :: [(Term, Term)] -> CaseDef
29simpleCase [] = CaseDef [] (UnmatchedCase "No pattern clauses")
30simpleCase cs = let pats = map (\ (l, r) -> (toPats l, r)) cs
31 numargs = length (fst (head pats))
32 ns = take numargs args in
33 CaseDef ns (evalState (match ns pats (UnmatchedCase "Error")) numargs)
34 where args = map (\i -> MN i "e") [0..]
36data Pat = PCon Name Int [Pat]
37 | PConst Const
38 | PV Name
39 | PAny
40 deriving Show
42toPats :: Term -> [Pat]
43toPats f = map toPat (reverse (getArgs f)) where
44 getArgs (App f a) = a : getArgs f
45 getArgs _ = []
47toPat :: Term -> Pat
48toPat tm = evalState (toPat' tm []) []
49 where
50 toPat' (P (DCon t a) n _) args = return $ PCon n t args
51 toPat' (P Bound n _) [] = do ns <- get
52 if n `elem` ns
53 then return PAny
54 else return (PV n)
55 toPat' (App f a) args = do a' <- toPat' a []
56 toPat' f (a' : args)
57 toPat' _ _ = return PAny
59data Partition = Cons [Clause]
60 | Vars [Clause]
62isVarPat (PV _ : ps , _) = True
63isVarPat (PAny : ps , _) = True
64isVarPat _ = False
66isConPat (PCon _ _ _ : ps, _) = True
67-- constants too
68isConPat _ = False
70partition :: [Clause] -> [Partition]
71partition [] = []
72partition ms@(m : _)
73 | isVarPat m = let (vars, rest) = span isVarPat ms in
74 Vars vars : partition rest
75 | isConPat m = let (cons, rest) = span isConPat ms in
76 Cons cons : partition rest
77partition xs = error $ "Partition " ++ show xs
79match :: [Name] -> [Clause] -> SC -- error case
80 -> State CS SC
81match [] (([], ret) : _) err = return $ STerm ret -- run out of arguments
82match vs cs err = mixture vs (partition cs) err
84mixture :: [Name] -> [Partition] -> SC -> State CS SC
85mixture vs [] err = return err
86mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
87 conRule vs ms fallthrough
88mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
89 varRule vs ms fallthrough
91data ConType = CName Name Int -- named constructor
92 | CConst Const -- constant, not implemented yet
94data Group = ConGroup ConType -- Constructor
95 [([Pat], Clause)] -- arguments and rest of alternative
97conRule :: [Name] -> [Clause] -> SC -> State CS SC
98conRule (v:vs) cs err = do groups <- groupCons cs
99 caseGroups (v:vs) groups err
101caseGroups :: [Name] -> [Group] -> SC -> State CS SC
102caseGroups (v:vs) gs err = do g <- altGroups gs
103 return $ Case v g
104 where
105 altGroups [] = return [DefaultCase err]
106 altGroups (ConGroup (CName n i) args : cs)
107 = do g <- altGroup n i args
108 rest <- altGroups cs
109 return (g : rest)
110 altGroups (ConGroup (CConst c) args : cs)
111 = do g <- altConstGroup c args
112 rest <- altGroups cs
113 return (g : rest)
115 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
116 matchCs <- match (newArgs ++ vs) nextCs err
117 return $ ConCase n i newArgs matchCs
118 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
119 matchCs <- match vs nextCs err
120 return $ ConstCase n matchCs
122argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
123argsToAlt [] = return ([], [])
124argsToAlt rs@((r, m) : _)
125 = do newArgs <- getNewVars r
126 return (newArgs, addRs rs)
127 where
128 getNewVars [] = return []
129 getNewVars ((PV n) : ns) = do nsv <- getNewVars ns
130 return (n : nsv)
131 getNewVars (_ : ns) = do v <- getVar
132 nsv <- getNewVars ns
133 return (v : nsv)
134 addRs [] = []
135 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
137getVar :: State CS Name
138getVar = do v <- get; put (v+1); return (MN v "e")
140groupCons :: [Clause] -> State CS [Group]
141groupCons cs = gc [] cs
142 where
143 gc acc [] = return acc
144 gc acc ((p : ps, res) : cs) =
145 do acc' <- addGroup p ps res acc
146 gc acc' cs
147 addGroup p ps res acc = case p of
148 PCon con i args -> return $ addg con i args (ps, res) acc
149 PConst cval -> return $ addConG cval (ps, res) acc
150 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
152 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
153 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
154 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
155 | otherwise = g : addg con i conargs res gs
157 addConG con res [] = [ConGroup (CConst con) [([], res)]]
158 addConG con res (g@(ConGroup (CConst n) cs) : gs)
159 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
160 | otherwise = g : addConG con res gs
162varRule :: [Name] -> [Clause] -> SC -> State CS SC
163varRule (v : vs) alts err =
164 do let alts' = map (repVar v) alts
165 match vs alts' err
166 where
167 repVar v (PV p : ps , res) = (ps, subst p (P Bound v undefined) res)
168 repVar v (PAny : ps , res) = (ps, res)
170{-
171mkOperator :: CaseDef -> [Value] -> Maybe Value
172mkOperator (CaseDef ns casetree) args
173 | length args /= length ns = Nothing
174 | otherwise = evalArgs (zip ns args) casetree
175 where
176 evalArgs map (Case n alts) =
177 do v <- lookup n map
178 (altmap, tm) <- findAlt (getValArgs v) alts map
179 evalArgs altmap tm
180 evalArgs map (STerm tm) =
181 evalArgs map (UnmatchedCase _) = Nothing
183 getValArgs tm = getValArgs' tm []
184 getValArgs' (VApp f a) as = getValArgs' f (a:as)
185 getValArgs' f as = (f, as)
187-}