Haskell(というか主に遅延評価)について
この記事はAizu Advent Calendar 2016 18日目の記事です。
前の人は、@lycoris0731 さん、次の人は @nktafuse さんです。
自分のこと
Noahです。学部一年です。
特に好きな分野とかは無いのですが、今回は『Haskellいいぞっ』という点と、Haskellの評価戦略(主に遅延評価と正格評価のこと)を書いていきたいと思います。
自分も初めて半年も経っていないのでわからないことも多いのですが、その点はご了承ください。
Haskell とは
何をもって関数型プログラミングとするか、関数型プログラミングを行っているコミュニティ内でも正確な定義や合意というものは存在しないが、一般的には、手続き型プログラミングがコマンド実行の列としてプログラムを記述していくのに対し、関数型プログラミングは複数の式を関数の適用によって組み合わせていくプログラミングスタイルである、ということは広く認められている。 by 関数型言語 - Wikipedia
つまり、Cなどが代表される手続き型言語は、
// nは任意の数 sum = 0; for (i = 0; i < n; i++){ sum += i; }
このような感じで、命令を並べ、順番に実行するのに対し、関数型言語(今回はHaskell)では
sum' :: Int -> Int --sum'としたのは、すでにsum関数がすでにPreludeというモジュールに定義されているからです。 sum' 0 = 0 sum' n = n + sum' (n - 1)
このように、関数の適用を組み合わせてプログラミングします。(この例では再帰を利用して0-nまでの合計値を出しています)
forは特にそうなのですが、変数に値を代入する行為、いわゆる副作用を排除した考えを関数型プログラミングでは用います。そのため、for(一応、forのようなものはHaskellに存在はするが)は、基本的にはあまり使いません
Haskellでは変数に値を入れることを束縛といいます。
値を束縛することで、変数を利用します。
一旦束縛したら、中身は変えられません。これは副作用を無くすことで生まれる参照透明性を確保するためです。
そんなの不便じゃないか??と思う方もいらっしゃると思いますが、プログラミングスタイルに慣れればこれは理にかなっているものだと感じられるようになります。
関数色々
Haskellは関数を第一級オブジェクトとして扱います。
つまり、関数を変数に束縛することや、関数の返り値として関数を返すことも可能です。
関数を引数に取る例としてmap関数があります。
map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map f xs
一番上に書いてあるものは関数の型宣言です。
f :: Int -> Int -- Int型を受取り、Int型を返す g :: (Int -> Int) -> Int -- Intを受け取りIntを返す関数、を受取、Intを返す。
map関数は、a型を受取りb型を返す関数(f) と、a型のリスト( (x:xs) ) を受取り、a型のリストの中身それぞれに関数を適用した値(b型)をリストにして返す関数です。
rubyなどのmapメソッドと同じ挙動ですね。
ちなみに、関数の型宣言で用いられているIntのように最初の文字が大文字のものは型ですが、aなどのように最初が小文字なものは型変数といい、任意の型(CharやInt, Integerなど)にできます。
更に、リスト (x:xs) で、リストの先頭要素とそれ以外の要素に分けて名前を付ける事ができます。
(:) はコンスと呼ばれる関数で、Lisp等のconsとおなじだと考えればいいです。
遅延評価と正格評価
Haskellの大きな特徴として、遅延評価を採用している点があります。
CやRubyなどでは、標準で正格評価を行います。
遅延評価が採用されると何が嬉しいかというと、簡単な例では無限リストを扱えます。
ghci > take 3 [1,2..] [1,2,3]
[1,2..]は、[1,2,3,4,5,...100,...10000000,....]と続く無限リストです。
take関数は、引数として与えたリストから指定された分だけ、先頭要素からリストにして返します。
普通こんなものを扱うと引数のリストを評価するために無限に処理が行われますが遅延評価を評価戦略にしていると、必要な分だけ処理するので、上記の例では先頭要素3つ分だけ評価します。
他の例では、たらい回し関数と言うものが有り、
tarai :: Int -> Int -> Int -> Int tarai x y z | x <= y = y | otherwise =tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)
以下にRubyでのコードも記述します。
def tarai(x, y, z) x<=y ? y : tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) end
そして、引数として(10, 5, 0)を与えたときのHaskellでの実行時間と、Rubyでの実行時間は以下の通りです。
*Main> tarai 10 5 0 10 (0.01 secs, 90,672 bytes)
% ruby tarai.rb user system total real 0.020000 0.000000 0.020000 ( 0.015592)
そんなに変わりませんね。体感時間でも両方一瞬で終わります。
次に引数として(14, 7, 0) を与えたときです。
*Main> tarai 14 7 0 14 (0.01 secs, 99,784 bytes)
% ruby tarai.rb user system total real 24.420000 0.090000 24.510000 ( 24.838016)
totalの時間が (10, 5, 0) のときより遥かに大きくなっています。
なぜこうなったかというと、Haskellの遅延評価が上手く効いているのです。
たらい回し関数では関数を実行する際に、引数(x', y', z') = ( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) [ 区別を付けるために引数はx', y', z'にしています ] のなかでx', y' を評価し、 y'<=x' となったときは、z'の部分は利用されず評価をしても値を利用することがありません。
遅延評価は、必要になったら評価する評価戦略なので、x'<=y'となったときには評価に不要なz'部分は評価せずに素直にy'を返します。
otherwise、つまりそれ以外になって、z'が必要になったときに初めてz'を評価するのです。
最後に
以上です。少々間違いもあるかもしれませんが、関数型やる人が増えてほしいなと切実に思います。
参考にしたサイトなど
Haskell
- すごくえっちな本
- 関数プログラミング実践入門(書籍)
時間の計測
おわり
数学ガールとやら
Noahです。
数学ガールを最近ちまちま読んでます。
なにしろ自分は、ここやTwitterに何回書いたか分からないけれど、兎にも角にも数学弱者なので勉強しようと思っても大学講義の微積Iや力学はさっぱりわからなかった。
微積分を高校時代に数IIの範囲までしかやってなかったので地獄を見ることは分かってた。分かってはいたんだ。
一ヶ月くらい前だが、同じクラスの数学好きな某氏に「数学ガール」なる本を勧められて、ちょうど数学のレポートに読書感想文(?)があったので読んでみた。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/03/02
- メディア: 単行本
- 購入: 19人 クリック: 779回
- この商品を含むブログ (102件) を見る
その本にコンピュータ理工学らしく「乱択アルゴリズム」を選んだわけだが、
線形探索や、二分探索などのオーダ記法のところは、
応用情報や基本情報の取得の際に覚えはしたものの理屈では分かってないところもあったのだが、やっとこの本で理解できた。
(試験を受けた当時は log n なんていうのも理解はしていなかった。高校生なのに。)
少々難しかったがなんとか最後まで読んだ。(理解しているかはさておき。)
何周かする必要がある。繰り返し大事。
そこで、先日「数学ガールの秘密ノート」シリーズを思い出した。
「数学ガールの秘密ノート」シリーズのほうが易しいことは数学好きな某氏や先輩に聞いていたので、長期貸出を行っている大学内の図書館から、
「微分を追いかけて」、
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/04/18
- メディア: 単行本
- この商品を含むブログ (12件) を見る
「数列の広場」、
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/10/18
- メディア: 単行本
- この商品を含むブログ (12件) を見る
「ベクトルの真実」
数学ガールの秘密ノート/ベクトルの真実 (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/11/18
- メディア: 単行本
- この商品を含むブログ (10件) を見る
上記三冊を借りることに成功。
それが今日の昼過ぎくらいの出来事だったが、未だ選んだ一冊目の「微分を追いかけて」の2章程度までしか読んではいない。
が、最初の最初から教えてくれるのが自分のような人間には、本当にありがたい。
一ヶ月は借りれるので何周か周って読めると思う。…思う。
資格試験とか大学とか
Noahです
推薦入試で某コンピュータ理工学の公立大学に入って、なんとなしに半年程度過ごしてきましたけど、
プログラミングを高校時代、趣味の範囲でやってるだけで高校ではCOBOLとかいう化石を触ってたのでそもそも大して出来るわけではないですが、なんとかCからやっていけてるので安心。
先輩方のすごいHな本(すごいHaskellたのしく学ぼう!)の読書会に参加したり、オブジェクト指向としてや、TwitterのAPIを叩くためにRubyを触ったりしながら、最近はとにかくプログラミングしかやってませんけど、
友人がそういえばIPAの情報処理技術者試験受けると言っていたので、自分の体験記として、高校時代を忘れないように備忘録しておきます
動機
そもそもこの試験を知ったのは高校1年でした。
高校2年で、公益財団法人全国商業高等学校協会の主催する地方大会、全国大会でそこそこいい成績残せてたので、なし崩し的に基本情報を受けることに。
基本情報技術者試験は、午前試験、午後試験とに区分が分かれており、両方で合格する必要がある。
午前は小問80題、四択のマークシートであり、60%正答で合格。
分野は、テクノロジ系、マネジメント系、ストラテジ系などで試験範囲は広い。そして浅い。
午後は大問13題から7題解く。午前と同じく60%正答で合格。
具体的には、大問1はセキュリティ問題で必須。配点は12点
大問2-7は、DB、ネットワーク、ソフトウェア設計、などなどから4題選択。配点はそれぞれの大問で12点
大問8は擬似言語。必須。配点は20点と高い
大問9-13は各種プログラミング言語。表計算は楽。COBOLムズい(あくまで個人的感想)。配点は20点。
基本情報では、自分は一回落ちてます。COBOLで受けてはいけない。合格したいなら表計算だ。
因みに配点はうろ覚えなのであまり参考にしないでください。
使用した参考書
- 作者: 角谷一成,イエローテールコンピュータ
- 出版社/メーカー: 技術評論社
- 発売日: 2016/01/21
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
平成28年度【秋期】基本情報技術者 パーフェクトラーニング過去問題集 (情報処理技術者試験)
- 作者: 山本三雄
- 出版社/メーカー: 技術評論社
- 発売日: 2016/06/18
- メディア: 大型本
- この商品を含むブログを見る
最初は合格教本をサラッと読んで、あとは過去問ばかりやるだけ。
一回目の受験までで大体5ヶ月程度かけて、一日三時間程度過去問と向き合って、
一回コケてからは一日1時間は過去問と向き合って知識忘れないように半年継続して勉強。
正直、午前は過去問ばかり出されるので、過去問をやってれば(暗記してしまえば)大して心配することはないが、
午後は少しひねられる上に、擬似言語で躓くときが多々あるので注意。
しかし結局午後も問題に慣れれば本番で躓くこともないと思われます。
応用情報
そして基本情報は合格した後、部活の顧問に次のレベルの応用情報技術者試験を勧められ、某コンピュータ理工学の公立大学に入ろうとこの頃に決めていたので受験。
基本情報をやってだいたい情報処理技術者試験の出題傾向がわかったので、難しいことはなかった。
応用情報技術者試験は基本情報と同じで、午前試験、午後試験の両方に合格する必要がある。
午前試験は、基本情報の午前試験に少し深いところまで突っつく感じのレベル。基本情報もだが、過去問をそつなくこなせるようになれば受かることだけはできる。60%正答で合格。
問題は午後試験だが、午後試験は、大問11題から5問選択。それぞれおそらく配点は各20点だと思われる(自己採点ではそのように採点した)。60%正答で合格。
大問1はセキュリティ。必須問題。
大問2-11では、経営戦略、プログラミング、DB、ネットワーク、ソフトウェア開発、マネジメントなど、多くの中から4題選択。
基本情報に比べ問題数が少ないが、大半の問題は「記述式」である。
国語力が試される試験なのかコレ、と、疑問になるが国語力は重要。
文字数制限の有る記述式なので、簡潔に、分かりやすく書く必要がある。
使用した書籍
(PDF・スマホ単語帳付)徹底攻略 応用情報技術者教科書 平成28年度(2016年度)
- 作者: 株式会社わくわくスタディワールド瀬戸美月
- 出版社/メーカー: インプレス
- 発売日: 2015/11/06
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
2016 応用情報技術者 午後問題の重点対策 (午後対策シリーズ)
- 作者: 小口達夫
- 出版社/メーカー: アイテック
- 発売日: 2015/11/27
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
午前問題は過去問をそつなくこなせるようになればいいので、午後を重点的に勉強する。
自分の場合、問題慣れする必要があるので、最低でも3年分、6回はこなした。
教科書というものは補助的に使い、ほとんどは過去問をこなす。
基本情報である程度インプットしていたので、今回はインプットはそんなにしなく、ひたすらアウトプットばかりしたのでノートはかなり消費した。
12月から勉強を始めたので実質勉強時間は4ヶ月で一日4時間程度。
過去問をやりすぎると問題を見た瞬間に答えが浮かぶようになるが、それでは本質を理解できてないので理解するまでこなす。
おかげで応用情報は一発で取れた。
以下の書籍も少々使った。が、応用情報の取得には過去問をやるのが一番なので軽く触れる。
- 作者: 竹下隆史,村山公保,荒井透,苅田幸雄
- 出版社/メーカー: オーム社
- 発売日: 2012/02/25
- メディア: 単行本(ソフトカバー)
- 購入: 4人 クリック: 34回
- この商品を含むブログ (35件) を見る
- 作者: 齋藤孝道
- 出版社/メーカー: オーム社
- 発売日: 2013/09/01
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (3件) を見る
ネットワークの知識を得るため。当初はネスペ、セスペを高校時代で合格することが目標(いや今も取れてないけど)だったので、購入。ネットワークまわりの知識が得られる。大きい本。
プログラマのための論理パズル 難題を突破する論理思考トレーニング
- 作者: Dennis E. Shasha,吉平健治
- 出版社/メーカー: オーム社
- 発売日: 2009/03/26
- メディア: 単行本
- 購入: 21人 クリック: 412回
- この商品を含むブログ (63件) を見る
これは、午後問は頭をつかうので頭の体操にと購入。
しかし、試験を受けた当初はまだ自分のレベルが足りてない上にこの本は難しい事この上ないので現在積み中。いずれ解くぞ。
こんな感じで書いててふと思ったけど大学に入ってからは、やれ微積だ、やれ線形代数だ、やれ力学だのと数学関連で血反吐を吐くはめになったのだが、これは紛れも無く商業高校から理工系大学にはいった宿命とも思われる。
その度に高校時代俺何やってたんだろうな…と思うことも多々あるので、某コンピュータ理工学の公立大学に推薦入試で入学を考えている商業高校の受験生の方々は基本情報や応用情報を勉強する前に数学Ⅲまでをしっかり履修するべきだと思います。
(あ、でも資格ないと推薦もらえないっけ…?)
ハッカーと画家
立ち読みしてたらなかなか面白かったから購入。
買ったのはちょっと前で、読んだのも最近だけど。
あまり考えずにさらさらと読んだから、あまり、理解はしていないけど、ただ、Lispが素晴らしいという事は理解できた。
Lispみたいな妙な構文を持っているものはあまり触りたくないし、ましてやEmacsならまだしもVim使ってるから余計関わりがない。
でも、絵の線を描く時みたいに適当なコード作っては走らせて改良してまた走らせてまた改良して…っていうのは、確かにわかる気がする。
高校の授業では、『まず流れ図(フローチャート)を作り〜』から始まって、『コーディングをして〜』という方式で、その時はそれが普通だと思い込んでたけど、内心『それくらいの処理なら直接コーディング出来ることない?!』とか思ってたけど、それから徐々に試作的なものを作って形作る方式に変えてったな…
授業ではCOBOLだったからかどうかわからないけど、実行する機会は殆どなくてコーディング用紙とか言う紙にコード書いて、後は先生のチェックとかそんなんだったし(笑)
とか書いてて色々高校生活であった事を思い出したりしなかったり。
大学から出てる課題終わらそー、、、
yacc/lex覚え書き part1
なーんかYaccとLexについて書いている所が少ないので、備忘録として書いておく。
Yaccとは何かというと、
Yacc(Yet Another Compiler Compiler、ヤック)はパーサジェネレータの一つである。1970年代にAT&TでUNIX用にステファン(スティーブ)・ジョンソンが開発した。--Yacc - Wikipedia より
んで、Lexはというと、
Lex(レック、レックス)はレキシカルアナライザ(字句解析プログラム、字句解析器)を生成するプログラムである。コンパイラの作成のためにパーサジェネレータのyaccとともに使用されることも多い。 --Lex - Wikipedia より
という事らしい。
要は、コンパイラの処理手順の、"字句解析"をLexが、"構文解析"を、Yaccが行っている
それぞれの書き方はまた次回。