--
-- Adapted from the program "infer", believed to have been originally
-- authored by Philip Wadler, and used in the nofib benchmark suite
-- since at least the late 90s.
--
module Term (VarId, Term (..), freeVars) where
import Shows
import qualified Data.Set as Set
import Data.Set (Set)
type VarId = String
data Term = Int Int
| Var VarId
| Abs VarId Term
| App Term Term
| Let VarId Term Term
freeVars :: Term -> Set VarId
freeVars t = go t Set.empty
where
go (Int _) s = s
go (Var v) s = Set.insert v s
go (Abs v t) s = Set.delete v (go t s)
go (App f t) s = go f (go t s)
go (Let v a b) s = go a (Set.delete v (go b s))
instance Show Term where
showsPrec d = showsTerm d
showsTerm :: Int -> Shows Term
showsTerm d (Int i) = shows i
showsTerm d (Var x) = showsString x
showsTerm d (Abs x v) = showsParenIf (d>0)
(showsString "\\" . showsString x . showsAbs v)
showsTerm d (App t u) = showsParenIf (d>1)
(showsTerm 1 t . showsChar ' ' . showsTerm 2 u)
showsTerm d (Let x u v) = showsParenIf (d>0)
(showsString "let " . showsString x .
showsString " = " . showsTerm 1 u .
showsString " in " . showsTerm 0 v)
showsAbs :: Shows Term
showsAbs (Abs x t) = showsString " " . showsString x . showsAbs t
{- ELSE -}
showsAbs t = showsString ". " . showsTerm 0 t