M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Functional Programming

Haskell Programming

[ Home | Functional ]

WHAT'S NEW

CONTENTS

お気楽 Haskell プログラミング入門

CONTENTS

はじめに

Haskell は「遅延評価」を採用した純粋な関数型プログラミング言語です。一般に、副作用のない関数型言語を「純関数型言語」といいます。ML 系の言語 (Standard ML や OCaml) も関数型言語ですが、変数の破壊的代入や入出力処理などの副作用を許しているため、純関数型言語とはいえません。Haskell の場合、副作用がある処理は「IO モナド (IO Monad) 」によって分離 (隔離) されているので、それ以外の処理は数学の関数 (数式) のようにプログラミングすることができます。

M.Hiroi は Haskell でプログラミングするのは初めてです。Haskell の特徴である「遅延評価」と「モナド」を使いこなすことができるように、簡単なプログラムを作りながら Haskell を勉強していきたいと思っております。まあ、初心者が作るプログラムなので、Haskell らしい綺麗なプログラムは書けないと思います。間違いやお気づきの点がありましたらご指摘いただけると助かります。たいしたことはできませんが、よろしければお付き合いくださいませ。

●ダウンロード

Haskell には複数の処理系がありますが、本ページでは GHC (Glasgow Haskell Compiler) を使うことにします。GHC は次のサイトからダウンロードできます。Windows 用のバイナリが用意されているので、とても簡単にインストールすることができます。

Haskell Platform は GHC に加え、GHC には含まれていないライブラリやツールが含まれています。M.Hiroi は Haskell Platform からダウンロードしました。

●プログラムの実行

GHC はコンパイラ (ghc) とインタプリタ (ghci) があります。また、Haskell をスクリプト言語のように実行するためのコマンド runghc も用意されています。たとえば、シェルで ghci を起動すると、メッセージとプロンプト Prelude> が表示されます。この状態で Haskell のプログラムを入力して簡単に実行することができます。終了する場合はコマンド :quit (または :q) か CTRL-D を入力してください。 

C>ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 1 + 2 * 3
7
Prelude> :q
Leaving GHCi.

C>

●簡単なベンチマーク

GHC はプログラムをネイティブコードにコンパイルするので、バイトコードにコンパイルする処理系よりもプログラムを高速に実行することができます。その実行速度ですが、たらいまわし関数を使って調べてみました。 

リスト：たらいまわし関数 (Haskell)

module Main (main) where

import Data.Time

tak :: Int ->  Int -> Int -> Int
tak x y z =
  if x <= y then z
  else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y)

-- 時間計測
main :: IO ()
main = do
  x <- getCurrentTime
  print (tak 20 10 0)
  y <- getCurrentTime
  print (diffUTCTime y x)

ファイル名を tak.hs とすると、シェル上で次のように入力すると実行ファイルを生成することができます。 

C> ghc -O tak.hs

-O は最適化を指定するオプションです。

それでは実行結果を示します。tak 20 10 0 を計算しました。使用した GHC のバージョンは ver 7.4.1 です。比較のため、Ruby, Python, CLISP (Common Lisp), SBCL (Common Lisp), Gauche (Scheme), SML/NJ, OCaml (ocamlc, ocamlopt), GCC (Ｃ言語) の実行結果を示します。 GCC, SBCL, ocamlopt, SML/NJ, GHC 以外の処理系はプログラムをバイトコードにコンパイルするものです。

表 : tak 20 10 0 の結果
処理系秒
Python (ver 2.7.3)14.51
Ruby (ver 1.9,3)11.35
CLISP (ver 2.48)5.71
Gauche (ver 0.9.2)4.65
ocamlc (ver 3.12.1)3.14
SBCL (ver 1.0.55)0.94
SML/NJ (ver 110.74)0.57
GCC -O (ver 4.5.3)0.37
SBCL (最適化)0.34
GHC -O (ver 7.4.1)0.31
GCC -O2 (ver 4.5.3)0.30
ocamlopt (ver 3.12.1)0.16

GHC は SML/NJ や SBCL よりも速い結果になりましたが、OCaml にはかないませんでした。それでも、GCC と同程度の速度をたたき出しているのですから、GHC は大変優れたコンパイラ (処理系) だと思います。

なお、たらいまわし関数には tak のほかにも tarai という関数があります。 

リスト：たらいまわし関数 (2)

tarai :: Int ->  Int -> Int -> Int
tarai x y z =
  if x <= y then y
  else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)

関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。

実をいうと、関数 tarai は「遅延評価」を行う処理系では高速に実行できることが知られています。実際に Haskell で tarai を実行すると、他の処理系とは比較にならないほど高速になります。興味のある方は試してみてください。

●FizzBuzz 問題

それでは簡単な例題として FizzBuzz 問題を Haskell で解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。

ここでは、FizzBuzz 問題を少し変えて、1 から n までの整数を文字列に変換し、それをリストに格納して返すことにします。たとえば、1 から 15 までの場合は次のようになります。 

fizzbuzz 15 => ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]

プログラムは次のようになります。 

リスト : FizzBuzz 問題 (fizzbuzz.hs)

toStr :: Int -> String
toStr x = if x `mod` 15 == 0 then "FizzBuzz"
          else if x `mod` 3 == 0 then "Fizz"
          else if x `mod` 5 == 0 then "Buzz"
          else show x

fizzbuzz :: Int -> [String]
fizzbuzz n = map toStr [1 .. n]

関数 toStr は数値を文字列に変換します。Haskell の場合、演算子 :: はデータ型を指定するために使います。ML と違ってコンス演算子ではないので注意してください。関数の型を指定しなくでも Haskell の型推論によりプログラムは動作しますが、きちんと型を書くことが Haskell の流儀のようです。

Int は整数値、String は文字列を表します。toStr の型は整数値を受け取って文字列を返す関数であることがわかります。mod は剰余を求める関数です。Haskell の場合、関数を二項演算子として使う場合はバッククォート (`) で囲みます。show はデータを文字列に変換する関数です。なお、toStr は if を使わないでガードや case を使ってプログラムすることもできます。

関数 fizzbuzz は数値を受け取って文字列を格納したリストを返します。Haskell の場合、[1 .. n] で 1 から n までの整数値を格納したリストを生成することができます。ここで、[1 ..] のように終端を省略すると「無限リスト」になります。あとは、生成したリストにマップ関数 map で toStr を適用すればいいわけです。

実行結果は次のようになります。 

Prelude> :l fizzbuzz.hs
[1 of 1] Compiling Main             ( fizzbuzz.hs, interpreted )
Ok, modules loaded: Main.
*Main> fizzbuzz 100
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14",
"FizzBuzz","16","17","Fizz","19","Buzz","Fizz","22","23","Fizz","Buzz","26",
"Fizz","28","29","FizzBuzz","31","32","Fizz","34","Buzz","Fizz","37","38",
"Fizz","Buzz","41","Fizz","43","44","FizzBuzz","46","47","Fizz","49","Buzz",
"Fizz","52","53","Fizz","Buzz","56","Fizz","58","59","FizzBuzz","61","62",
"Fizz","64","Buzz","Fizz","67","68","Fizz","Buzz","71","Fizz","73","74",
"FizzBuzz","76","77","Fizz","79","Buzz","Fizz","82","83","Fizz","Buzz","86",
"Fizz","88","89","FizzBuzz","91","92","Fizz","94","Buzz","Fizz","97","98",
"Fizz","Buzz"]

ghci でプログラムをロードする場合、コマンド :load または :l を使います。:l fizzbuzz.hs でファイルをロードすれば、ghci で関数 fizzbuzz を呼び出すことができます。

Yet Another Haskell Problems

参考文献と URL

  1. Miran Lipovaca (著), 田中英行, 村主崇之 (共訳),『すごい Haskell たのしく学ぼう！』, オーム社, 2012
  2. Miran Lipovaca, 『Learn You a Haskell for Great Good!』(英語)
  3. Paul Hudak, John Peterson and Joseph Fasel (著), 山下伸夫 (訳), 『やさしい Haskell 入門 (バージョン98)』

Haskell Programming (お気楽 Haskell プログラミング入門を含む本ページ) の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。Haskell Programming で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

Copyright (C) 2013 Makoto Hiroi
All rights reserved.
[ Home | Functional ]