Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

【解答例】Haskellによる代数計算入門

More than 5 years have passed since last update.

リスト化

【問1】フィールドをリストにしてください。テストも修正してください。

data Add = Add [Int] deriving Show

eval (Add xs) = sum xs

tests = TestList
    [ "eval 1" ~: eval (Add [1, 1]) ~?= 1+1
    , "eval 2" ~: eval (Add [2, 3]) ~?= 2+3
    ]

ここまでのコード

括弧

【問2】内部に含まれた式を括弧で囲むように修正してください。演算子の優先順位で括弧が含意されているもの(例: 1+2*3)は除きます。

以下の場合に括弧を付けます。

  • Addの中にAddが入っている場合(例: (1+2)+3
  • Mulの中にAddが入っている場合(例: (1+2)*3
  • Mulの中にMulが入っている場合(例: (1*2)*3
strを修正
str (N x) = show x
str (Add [])       = ""
str (Add [Add xs]) = "(" ++ str (Add xs) ++ ")"
str (Add [x])      = str x
str (Add (x:y:zs))
    | isneg y      = str (Add [x])        ++ str (Add (y:zs))
str (Add (x:xs))   = str (Add [x]) ++ "+" ++ str (Add xs)
str (Mul [])       = ""
str (Mul [Add xs]) = "(" ++ str (Add xs) ++ ")"
str (Mul [Mul xs]) = "(" ++ str (Mul xs) ++ ")"
str (Mul [x])      = str x
str (Mul (x:xs))   = str (Mul [x]) ++ "*" ++ str (Mul xs)

ここまでのコード

係数

【問3】係数もVarのフィールドに入れてください。

コンストラクタを修正
data Expr = N Int
          | Var String Int Int
          | Add [Expr]
          | Mul [Expr]
          deriving (Show, Eq)
xを修正
x a n = Var "x" a n
strを修正
str (Var x  1 1) = x
str (Var x(-1)1) = "-" ++ x
str (Var x  a 1) = show a ++ x
str (Var x  a n) = str (Var x a 1) ++ "^" ++ show n

係数が負の時に+-と表示されないように調整します。

isnegを修正
isneg (N n)       | n < 0 = True
isneg (Var _ a _) | a < 0 = True
isneg _                   = False

ここまでのコード

同類項の整理

【問4】xについて同類項を整理する関数xsimplifyを実装してください。内部でxsortを使ってください。

テストに使われている特殊ケースに対応するための関数を実装します。

  • ネストしたAddをフラットにする: $x^2+(1+2x^2)+2=3x^2+3$
flatten []              = []
flatten ((Add xs1):xs2) = flatten (xs1 ++ xs2)
flatten (x:xs)          = x : flatten xs

コンストラクタのラッパーで特殊ケースに対応します。

  • ゼロを消す: $x+1-x-1=0$
  • 単項をAddから外す: $(x+2x)=3x$
add []  = N 0
add [x] = x
add xs  = Add xs

xsortを使うと降べきの順になるので、同類項のチェックが隣接する項だけで済みます。

xsimplify (Add xs) = add $ f $ getxs $ xsort $ Add $ flatten xs
    where
        getxs (Add xs) = xs
        f []  = []
        f ((N     0  ):xs) = f xs
        f ((Var _ 0 _):xs) = f xs
        f [x] = [xsimplify x]
        f ((N a1):(N a2):zs) = f $ N (a1 + a2) : zs
        f ((Var "x" a1 n1):(Var "x" a2 n2):zs)
            | n1 == n2 = f $ (a1 + a2)`x`n1 : zs
        f (x:xs) = xsimplify x : f xs
xsimplify (Mul xs) = Mul [xsimplify x | x <- xs]
xsimplify x = x

計算結果を再帰に掛けているのがポイントです。

ここまでのコード

展開

一段階

【問5】多項式の掛け算を一段階だけ展開する関数expandを実装してください。

addと同じようにコンストラクタのラッパーを作ります。

mul []  = N 1
mul [x] = x
mul xs  = Mul xs

expand (Mul xs) = mul $ f xs
    where
        f []  = []
        f [x] = [expand x]
        f (x:y:xs) = multiply x y : xs
expand (Add xs) = add $ f xs
    where
        f []  = []
        f (x:xs)
            | x /= x'   = x':xs
            | otherwise = x : f xs
            where
                x' = expand x
expand x = x

ここまでのコード

すべて

【問6】一段階で止めずにすべて展開する関数expandAllを実装してください。

結果が変わらなくなるまでexpandを繰り返します。

expandAll x
    | x /= x'   = expandAll x'
    | otherwise = x
    where
        x' = expand x

ここまでのコード

積分

【問7】不定積分を実装してください。

ExprのフィールドをIntからRationalにします。

importに追加
import Data.Ratio
Exprを修正
data Expr = N Rational
          | Var String Rational Rational
          | Add [Expr]
          | Mul [Expr]
          deriving (Show, Eq)

整数が3 % 1のように分数で表示されてしまい、テストが通らなくなります。

### Failure in: 6:str 1
expected: "1+2+3"
 but got: "1 % 1+2 % 1+3 % 1"

分母が1かどうかをチェックして表示する関数を作成します。

  • 分子・分母を取得する関数はData.Ratioで調べます。
  • テストで係数が分数のときにスペースを入れているのに対応するため、引数でサフィックスを指定します。
rstr x s
    | d == 1    = show n
    | otherwise = show n ++ "/" ++ show d ++ s
    where
        n = numerator x
        d = denominator x

rstrを使うようにstrを修正します。

strを修正(抜粋)
str (N x) = rstr x ""
str (Var x  a 1) = rstr a " " ++ x
str (Var x  a n) = str (Var x a 1) ++ "^" ++ rstr n ""

これでまたテストが通ります。

不定積分を実装します。

integrate x (Add ys) = Add $ [integrate x y | y <- ys] ++ [Var "C" 1 1]
integrate x (Var y a n)
    | x == y    = Var x (a / (n + 1)) (n + 1)
    | otherwise = Mul [Var y a n, Var x 1 1]
integrate x (N n) = Var x n 1

ここまでのコード

7shi
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away