一个40行的Lambda Exp evaluator

{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE ViewPatterns #-}
type Identifier = String

data LambdaExp =
    Var {
        name :: Identifier
        } |
    Function {
        para :: Identifier,
        body :: LambdaExp
        } |
    App {
        func :: LambdaExp,
        arg :: LambdaExp
        }

eval :: LambdaExp -> LambdaExp
eval x@(Var n) = x
eval (Function p b) = Function p $ eval b
eval x@(App f a) = case f of
    Var _ -> x
    App _ _ -> let f' = eval f
                   a' = eval a
                in case f' of
                     Function p b -> replace b p a
                     _ -> App f' a'
    Function p b -> let b' = eval b
                        a' = eval a
                     in replace b' p a

--         expression   replacee      replacer
replace :: LambdaExp -> Identifier -> LambdaExp -> LambdaExp
replace x@(Var n) from to = if n == from
                               then to
                               else x
replace x@(Function p b) from to = if p == from
                                      then x
                                      else Function p $ replace b from to
replace (App f a) from to = let t x = replace x from to
                             in App (t f) (t a)

还实现了一个Show Class和Read Class就不发了

略trivial

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s