今更

大分前にHaskellで、多項式周りのアルゴリズムを色々実装して遊んでたけど、多項式型は、たぶん、誰でも考えるとおり

data Polynomial a = Const a
                  | Var String
                  | PLUS (Polynomial a) (Polynomial a)
                  | MULT (Polynomial a) (Polynomial a) deriving (Show,Read)

instance (Num a,Ord a) => Num (Polynomial a) where
 p+q = normalize(PLUS p q)
 p*q = normalize(MULT p q)
 p-q = normalize(PLUS p (MULT (Const (negate 1)) q)
 fromInteger n = Const (fromInteger n)

みたいな定義になってる。normalizeは、多項式を適当な標準形に直す関数。

で、がんばってパーサ書いたり、変数に値代入した時は〜とか色々やってたけど、Haskellって

Prelude> (\x y -> 2*x*x+y+3) (Var "x") (Var "y")
PLUS (MULT (Const 2) (MULT (Var "x") (Var "x"))) (PLUS (Var "y") (const 3))
Prelude> (\x y -> 2*x*x+y+3) 4 (Var "hoge")
PLUS (Var "hoge") (Const 35)

とかできてしまうんだよなぁって、気付いた。大したことじゃないけど、私は結構感動した。

逆もできるとよい。つまり、PLUS (MULT (Const 2) (MULT (Var "x") (Var "x"))) (PLUS (Var "y") (const 3))みたいな表現から、(\x y -> 2*x*x+y+3)みたいな式を得たい。式つくるだけなら、

--Language.Haskell.THをimportすること
expandToHs :: Polynomial Integer -> Exp
expandToHs p = LamE (map VarP $ vars p) (mkBody p)
 where
  vars(Const _) = []
  vars(Var x) = [mkName x]
  vars(PLUS p q) = nub $ (vars p)++(vars q)
  vars(MULT p q) = nub $ (vars p)++(vars q)
  mkBody (Const n) = (LitE (IntegerL n))
  mkBody (Var v) = (VarE (mkName v))
  mkBody (PLUS p q) = InfixE (Just (mkBody p)) (VarE (mkName "+")) (Just (mkBody q))
  mkBody (MULT p q) = InfixE (Just (mkBody p)) (VarE (mkName "*")) (Just (mkBody q))

とかでしまい

Prelude> ppr $ expandToHs ((\x y ->2*x*x*x+y*3) (Var "a") (Var "b"))
\a b -> (2 * (a * (a * a))) + (3 * b)

で、evalすればいいんだけど、そうすると、モナドが顔を出すので、なんかイヤ。型に厳しいhaskellでは仕方ないか