Help us understand the problem. What is going on with this article?

Haskell で逆ポーランド記法計算機を作る

More than 5 years have passed since last update.

昔やった勉強会の資料が出てきたので掲載。

Haskell 初心者向けの記事で、実数の計算・リスト・関数適用・関数定義・関数合成・パターンマッチ・ポイントフリー(名前は出てこない)・型の作成・畳み込みあたりが学べます。


Haskell 入門ハンズオン in 明石 #AkashiHaskell

2012.10.28

逆ポーランド記法 (後置記法、Reverse Polish Notation、RPN)用の計算機を作ることを目標とします。

1. 数値計算

+, -, *, / が普通に使えます。div, mod は整数での除算・剰余を表します。

GHCi を使用します。このテキストでは ghci> をプロンプトとします。

ghci> 1+2*3
7
ghci> 5/3
1.6666666666666667
ghci> 5 `div` 3
1
ghci> 5 `mod` 3
2

単項の - については必ず括弧が必要です。

ghci> 2*(-4)
-8

div, mod は次のように書くこともできます。

ghci> div 5 3
1
ghci> mod 5 3
2

反対に + 等は括弧で囲むと次のように書くこともできます。

ghci> (+) 1 ((*) 2 3)
7

2. 関数

2.1. 関数評価

関数適用(関数呼び出し)の例を上げます。succ は「後ろ」を求める関数、max は「大きい方」を得る関数です。

ghci> succ 5
6
ghci> succ (-3)
-2
ghci> max 12 20
20

2.2. 関数定義

次は関数定義です。円の面積を求める circleArea 関数を作ってみましょう。

ghci> let circleArea r = r*r*pi
ghci> circleArea 4
50.26548245743669

5を加算する関数 add5 を作ってみます。

ghci> let add5 x = 5 + x

先に出て来たように + は次のように書くこともできます。

ghci> let add5 x = (+) 5 x

引数が式の1番後ろの場合、引数を省略することができます。

ghci> let add5   = (+) 5

+ を中置にして次のように書くこともできます。

ghci> let add5   = (5 +)

2引数をとって加算する関数 add を例に作ってみます。

ghci> let add x y = x + y

前置にすると。

ghci> let add x y = (+) x y

これも引数が省略できます。

ghci> let add     = (+)

関数合成

ある関数 $f$ と $g$ との合成関数 $h = f∘g$ つまり $h = \lambda x. f(g(x))$ を作る場合は次のように書けます。

ghci> let h = f . g
ghci> let f = (*2) . (+1)
ghci> f 3
8
ghci> f 8
18

練習

circleArea 関数を引数なしの形で作ってみましょう。ただし、冪乗を表す関数は (**) です。

ghci> 2 ** 3
8
ghci> (**) 3 2
9

3. リスト

リストの作り方。下記コードは全て同じリストを作ります。(:) は Lisp の cons に当たります。

[1, 2, 3, 4]
1:[2, 3, 4]
1:(2:(3:(4:[])))
1:2:3:4:[]
[1..4]

基本的なリスト操作。headtailinitlast を紹介します。

ghci> let l = [1, 2, 3, 4]
ghci> head l
1
ghci> tail l
[2,3,4]
ghci> init l
[1,2,3]
ghci> last l
4

練習

リストの2番目を表す関数を作ってみましょう。またそれを引数なしの形で作れますか?

4. 型

よく使う基本的な型は次の通り。

Int
Double
Char
Bool
String = [Char]

[Char]Char のリスト型を表し String はその別名です。一般に [a]a 型を要素に持つリスト型を表します。

次は関数の型について。

大文字にする関数である toUpper の型は Char -> Char と表されて、Char を取って Char を返す関数と読みます。toUpperData.Char モジュールにあるため Data.Char.toUpper と書きます。

head の型は [a] -> a と表されて、ある型 a のリストを取って a を返す関数と読みます。例えば、[Int] を与えられると Int を返します。

(+) の型は Num a => a -> a -> a と表されます。 Num a => については詳しい解説はしませんが、「型 a は数値として扱えるものに限る」という意味です。a -> a -> a は、ある型 a の第1引数とそれと同じ型 a の第2引数を取って型 a を返す関数と読みます。

C 言語と同じでシングルクオートで Char 型のリテラルを、ダブルクオートで String 型を表します。

GHCi で :type もしくはその略の :t で型を調べることができます。式 :: 型の形で表されます。

ghci> :type 1
1 :: Num a => a
ghci> :t ['t', 'k']
['t','k'] :: [Char]
ghci> :t "Akashi"
"Akashi" :: [Char]
ghci> :t Data.Char.toUpper
Data.Char.toUpper :: Char -> Char
ghci> :t head
head :: [a] -> a
ghci> :t (+)
(+) :: Num a => a -> a -> a

関数を表す -> は右結合性なので a -> a -> aa -> (a -> a) と等価です。つまり本当は、「a を取って『a を取って a を返す関数』を返す関数」です。なので (+) 1 の型は Num => a -> a となります。そういうわけで先に出てきた以下のコードが成り立つわけです。

ghci> let add5 x = (+) 5 x
ghci> let add5   = (+) 5

厳密には Haskell には1引数関数しかありませんが、(+)max などは便宜上2引数関数として扱います。

5. 畳み込み

今回は、再帰を書くことを避ける手段の1つ「畳み込み (fold)」を使います。リストの要素を順番に使いながらある値を更新していくときに使用します。単純な例として1から10までを足していくことを考えてみます。

foldl (+) 0 [1..10]

foldl の説明

foldl 更新に使う関数 更新される値の初期値 リストというように使います。「更新に使う関数」の引数と返り値は前回の更新された値 -> 今回使うリストの要素 -> 新しく更新された値です。上の例ならこの関数は (+) に当たります。

次のコードで引数に与えられたリストの和を求める関数が作れますね。

ghci> let sum' = foldl (+) 0

練習

次のコードは、与えられたリストの逆順のリストを作る関数です。

ghci> let reverse' = foldl (\acc x -> x:acc) []

解読してみましょう。分からなければ上図のような図を描いてみましょう。:tで型を調べると期待通りになっていますか?

6. パターンマッチ

Haskell にはパターンマッチと呼ばれるものがあります。まず例を見ましょう。:{:} は複数行の入力を GHCi に与えるためのものです。

ghci> :{
ghci| let say 1 = "one"
ghci|     say 2 = "two"
ghci|     say _ = "other"
ghci| :}

引数が 1 のときは "one" を、引数が 2 のときは "two" を、そのほかのときは "other" を返します。_ は何にでもマッチします。

変数にマッチさせると後からその変数を参照することができます(下のコードの x)。_ は後から参照しないことを表す特別な変数です。

ghci> let id' x = x

リストに対してパターンマッチすることもできます。

ghci> let head' (x:_) = x
ghci> let head2 (x:y:_) = [x,y]

練習

tail 関数を自前で作ってみましょう。

7. 新しい型とその値を作る

対話環境 (GHCi) ではここのコードを実行できないのでソースファイルを作ってそこで作業します。(バージョン7.4.1以降は対話環境でも実行できるらしい。)

  1. 好きなところに Sample1.hs というファイルを作る。
  2. GHCi を起動する
  3. :cd foo/bar で Sample1.hs のあるディレクトリーまで移動する
  4. :load Sample1.hs でロードします。(:l でもOK)
  5. ソースコードを書き換えたら :reload でリロードします。(:r でもOK)

まずは曜日を表す型とその値を作ってみましょう。

data Day = Sunday | Monday | Tuesday | Wednesday | Thurseday | Friday | Saturday deriving Show

これで Day という型ができ Sunday から Saturday までの値ができました。C 言語でいうと列挙型のような使い方です。deriving Show はおまじないです。値を文字列にすることをできるようにする役割があります。

次は C 言語でいう構造体のような使い方の例をあげます。

data Person = Person String Int deriving Show

名前(String)と年齢(Int)を持った Person 型を作りました。使い方は下のコードのようになります。GHCi にロードして使います。

ghci> :load Sample1.hs
ghci> let kakkun61 = Person "Okamoto" 23
ghci> kakkun61
Person "Okamoto" 23

パターンマッチすることもできます。それぞれ Person 型から名前と年齢を取り出す関数です。

ghci> let name (Person s _) = s
ghci> let age (Person _ i) = i

列挙型的なものと構造体的なものと合わせて使うこともあります。2分木を表すデータ構造を作りたいとしましょう。

data Tree = Node Int Tree Tree | Empty deriving Show

Tree型の解説

下のコードで上の画像の2分木が作れます。

ghci> let tree = Node 1 (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)) (Node 5 Empty (Node 6 Empty Empty))

練習

週末かどうかを判定する isWeekend :: Day -> Bool 関数を作ってみましょう。

1才年をとった Person 型を返す getOld :: Person -> Person 関数を作ってみましょう。

逆ポーランド記法計算機

rpnCalc :: [RPN の式の要素] -> Double というような関数を考えましょう。

まずは型を決めなければいけません。「RPN の式の要素」を表す型を Haskell で作りましょう。今回は「RPNの式の要素」に、数と +、-、*、/ を考えます。よって次のコードのように型とその値を作ります。

data RpnElem =
    Number Double
  | Add
  | Subtract
  | Multiple
  | Divide

よって Haskell のコードでは RPN の式の “1” は [Number 1] に、“8 6 3 / +” は [Number 8, Number 6, Number 3, Divide, Add] になります。

型ができたので次は動作を考えていきましょう。とりあえず RPN の式の計算方法をおさらいです。“1 2 + 3 * 4 5 - /” を計算してみます。

逆ポーランド記法の式の計算方法

RPN の式の要素を順番に使い、スタックを更新していっています。つまり「リストの要素を順番に使いながらある値を更新していく」に合致します。ということは畳み込みが使えるわけです。

foldl rpnCalc' [] [...]

上の式が今回作る関数の中心部分となります。rpnCalc' は上図に橙色に当たる関数であり、前の状態のスタックを表すリストと、今回使う RPN 式の要素をとって、新しい状態のスタックを表すリストを返します。rpnCalc' の次の [] はスタックの初期値です。そして [...][RpnElem] 型の値を表します。

rpnCalc' の型は [Double] -> RpnElem -> [Double] となります。次に実装ですが、RpnElem によって場合分けをする必要があります。パターンマッチを使えばいいですね。

rpnCalc' _ (Number x) = ...
rpnCalc' _ Add        = ...
rpnCalc' _ Subtract   = ...
rpnCalc' _ Multiple   = ...
rpnCalc' _ Divide     = ...

第2引数が Number x にマッチした場合を考えましょう。このときはx をスタックにプッシュするわけですから、第1引数のリストの先頭に x を追加します。上図のスタックの上方向がリストの左方向に対応します。

rpnCalc' s (Number x) = x:s

第2引数が Add にマッチした場合は、スタックの上から2番目と1番目を足し算しその結果をスタックに積みます。Multiple の場合もほとんど同じです。

rpnCalc' (x:y:xs) Add      = (y + x:xs)
rpnCalc' (x:y:xs) Multiple = (y * x:xs)

第2引数が Subtract にマッチした場合は、スタックの上から2番目から1番目を引き算しその結果をスタックに積みます。Divide の場合もほとんど同じです。

rpnCalc' (x:y:xs) Subtract = (y - x:xs)
rpnCalc' (x:y:xs) Divide   = (y / x:xs)

ここまでくればほぼできたも同然です。foldl rpnCalc' [] では型が [RpnElem] -> [Double] ですので返り値を Double にしたいです。リストの先頭を取り出せばいいので head が使えます。先頭といっても要素1つのリストなのですが。

以上をまとまると下記のコードになります。

data RpnElem =
    Number Double
  | Add
  | Subtract
  | Multiple
  | Divide

rpnCalc :: [RpnElem] -> Double
rpnCalc = head . foldl rpnCalc' []

rpnCalc' :: [Double] -> RpnElem -> [Double]
rpnCalc' (x:y:xs) Add        = (y + x:xs)
rpnCalc' (x:y:xs) Subtract   = (y - x:xs)
rpnCalc' (x:y:xs) Multiple   = (y * x:xs)
rpnCalc' (x:y:xs) Divide     = (y / x:xs)
rpnCalc' xs       (Number x) = (x:xs)

試しに計算してみましょう。上記のコードがワーキングディレクトリーの RpnCalc.hs ファイルに書かれているとします。

ghci> :l RpnCalc.hs
[1 of 1] Compiling Main             ( RpnCalc.hs, interpreted )
Ok, modules loaded: Main.
ghci> rpnCalc [Number 1]
1.0
ghci> rpnCalc [Number 1, Number 2, Add]
3.0
hgci> rpnCalc [Number 1, Number 2, Add, Number 3, Multiple, Number 4, Number 5, Subtract, Divide]
-9.0

練習

この計算機に剰余を追加してみましょう。

Why do not you register as a user and use Qiita more conveniently?
  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
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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