上田ブログ

生きるフリー素材化への厳しい修行(生きるフリー素材だとは言っていない)

お知らせ: 本買ってくださーい / 

  このエントリーをはてなブックマークに追加 
   

USP Magazine 2014年7月号「シェル芸勉強会後追い企画 Haskellでやってはいかんのか?

出典: USP magazine 7月号

<iframe src="http://rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=ryuichiueda-22&o=9&p=8&l=as4&m=amazon&f=ifr&ref=ss_til&asins=490480709X" style="width:120px;height:240px;" scrolling="no" marginwidth="0" marginheight="0" frameborder="0">

各号の一覧へ

4. シェル芸勉強会後追い企画: Haskellでやってはいかんのか?

4.1. はじめに

 皆さん、しらばっくれてますか? 締め切り後からおもむろに書き始める、 ダメな感じ満載の上田です [2] 。 いやあね、もう歳で、とにかく物忘れが酷い酷い。 この前なんか、 自首しようと思ったのに忘れていて、 家までFBIが来て大変でした [3]

 反省はほどほどに、はじめましょう [5] 。 まず一つご報告ですが、 Haskellのインストール等の情報を私のサイトにまとめました。

/?page_id=2944

にあります。続きはWebで。面会は刑務所で。

4.2. おさらい

 前回からシェル芸勉強会の第1回2問目をやっちょります。 環境はLinuxを想定しています。

/etc/passwd から、次を調べてください。 「ログインシェルがbashのユーザとshのユーザ、どっちが多い?」

ほんと、しらねーよという感じですが [6] 、前回から真面目に取り組んできました。 前回までで完成したコードを図1に示します。

  • 図1: 前回の最後のコードq1_2_3.hs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_3.hs
import Data.List
import Data.List.Split

main = getContents >>= putStr . main'

main' :: String -> String
main' cs = unlines $ shellCount $ map getShell (lines cs)

getShell :: String -> String
getShell ln = last $ splitOn ":" ln

shellCount :: [String] -> [String]
shellCount shs = map f $ shellCount' [ (1,s) | s <- (sort shs) ]
 where f (n,str) = unwords [show n,str]

shellCount' :: [(Int,String)] -> [(Int,String)]
shellCount' shs = shs

 関数 shellCount' が今のところダミーになっています。 実行すると図2のような出力が出ます。

  • 図2: q1_2_3をexecution [9]

 おさらいついでにもう一つ補足すると、 図1の q1_2_3.hs の15行目の show 関数は、数値等を文字列に変換する関数です。 ghciで調べると、図3のような型です。

  • 図3: showの型
1
2
Prelude> :t show
show :: Show a => a -> String

ここで、 Show a というのは、 「 show が使える任意の型」という意味です。 そのような型がどのように定義されるのかは、 死人が出そうなので説明をやめておきます [4] 。代わりに show の動作を図4にお見せします。

  • 図4: showの動作
1
2
3
4
5
6
Prelude> show 0.1
"0.1"
Prelude> show 1
"1"
Prelude> show 1e+100
"1.0e100"

4.3. 開始!

 Haskellの内部では各レコードは次のような二つの値の対になっています。

(1,"/bin/bash")

このような対をHaskellでは「タプル」と呼びます。 この例のタプルの型は図5のような感じ。

  • 図5: タプルの型
1
2
Prelude> :t (1,"/bin/bash")
(1,"/bin/bash") :: Num t => (t, [Char])

また、 show の型のように Num t => というのが 出てきましたが、これも数字に属する任意の型 t という意味になります。 「1」の型が不定 [7] なのでややこしい出力になってしまいましたが、 要は数字と文字列のタプルです。 これがリストになったものが、18行目の入力 shs です。 18行目の右辺で、例えば

[(1,"/bin/bash"), (1,"/bin/bash"), (1,"/bin/sh")]

とあったら

[(2,"/bin/bash"), (1,"/bin/sh")]

とまとめるコードを右辺に書きます。

4.4. パターンマッチで場合分け

 まとめる戦略を次のように考えます。 リスト [a,b,c,...] (a,b,cがそれぞれタプル)に対して、

  1. リストの先頭二つの要素aとbを比較
  2. aとbに入っているシェルの名前が一致: タプル中の数字を足し合わせて一つの要素にまとめる
  3. 一致しない: aをそのままにして、bとcを比較

という手続きを書いていこうと思います。

 しかしその前に、 じゃあリストに1個しか要素が無かったとき、 あるいは0個だったときのことも考えておかないといけません。 Haskellでは図6のようなコードを書きます。

  • 図6: パターンマッチを書いたq1_2_4.hs
1
2
3
4
5
6
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_4.hs
(中略)
shellCount' :: [(Int,String)] -> [(Int,String)]
shellCount' [] = []
shellCount' [a] = [a]
shellCount' shs = shs

 これは4行目がリストが空だったときの対応、 5行目がリストの要素が1個だったときの対応を示しています。 このように、Haskellでは関数を複数定義することができ、 引数の条件によって適用される関数を変えることができます。 この機能は「パターンマッチ」と呼ばれます。 引数の条件(パターン)は、上から順に照合され、 マッチしたらその行の関数が適用されます。 従って、要素数が二つ以上の場合は、6行目の関数が適用されます。

4.5. パターンの書き方

 さて、図6の6行目の shellCount' に、 リストをまとめる処理を書きましょう。 まだ完成ではありませんが、 まず次のように6行目の関数を書き換えます。

 まず、6行目の引数が ((n1,s1):(n2,s2):ss) と書き変わっています。 まず、「 : 」ですが、これは図7のような型の演算子です。 演算子の型を調べるときは括弧で囲みます。

  • 図7: 「:」の型
1
2
Prelude> :t (:)
(:) :: a -> [a] -> [a]

これだけでは分かりませんが、 : は 「要素一つをリストの先頭にくっつける」 という演算子です。

 ですので ((n1,s1):(n2,s2):ss) は、 「 ss という名前のリストに (n1,s1)(n2,s2) をくっつけたもの」 という意味になります。 ss は空リストでもよいので、 パターンとして見ると、 要素数が2個以上のリストを意味することになります。

 そして、ここで使った n1,s1,n2... は、右辺で自由に使えます。

4.6. ガードでも場合分け

 次に、図8のところまで書き進めてみました。 7,8行目にまた珍妙な書き方が登場しましたが、 これは「ガード」と呼ばれるものです。 これも関数の定義を場合分けしている書き方で、 7行目が s1s2 が一致している場合に 7行目の右側を評価する、 その他の場合には8行目の右辺を評価するという意味になります。

  • 図8: ガードを使ったq1_2_5.hs
1
2
3
4
5
6
7
8
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_5.hs
(中略)
shellCount' :: [(Int,String)] -> [(Int,String)]
shellCount' [] = []
shellCount' [a] = [a]
shellCount' ((n1,s1):(n2,s2):ss)
 | s1 == s2 = (n1+n2,s1):ss
 | otherwise = ((n1,s1):(n2,s2):ss)

 パターンマッチと違って、ガードでは値の比較ができます。 パターンマッチは型の比較しかできません。

 さて、肝心の7, 8行目の右辺の処理ですが、 7行目は二つの要素をまとめて、残りのリストとくっつけています。 8行目はそのままリストを返しています。

4.7. 再帰処理を行う

 このままこのコードをコンパイルして実行してみると、 図9のように先頭の2行だけ集計されて出力されます。 処理が連鎖するように、もうちょっとだけ加筆が必要です。

  • 図9: q1_2_5の実行
1
2
3
4
5
ueda@remote:~/GIT/USPMAG/SRC$ cat /etc/passwd |
 ./q1_2_5 | head -n 3
2 /bin/bash
1 /bin/bash
1 /bin/false

 完成したコード全体を図10に示します。

  • 図10: 完成!(q1_2_6.hs)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_6.hs
import Data.List
import Data.List.Split

main = getContents >>= putStr . main'

main' :: String -> String
main' cs = unlines $ shellCount $ map getShell (lines cs)

getShell :: String -> String
getShell ln = last $ splitOn ":" ln

shellCount :: [String] -> [String]
shellCount shs = map f $ shellCount' [ (1,s) | s <- (sort shs) ]
 where f (n,str) = unwords [show n,str]

shellCount' :: [(Int,String)] -> [(Int,String)]
shellCount' [] = []
shellCount' [a] = [a]
shellCount' ((n1,s1):(n2,s2):ss)
 | s1 == s2 = shellCount' $ (n1+n2,s1):ss
 | otherwise = (n1,s1):(shellCount' $ (n2,s2):ss)

 さて、コードの解説をば。 q1_2_5.hsq1_2_6.hs の違いですが、まず、 q1_2_6.hs の21行目で、作ったリストに再度、 自分自身 shellCount` を適用しています。 22行目では、最初の要素 (n1,s1) をどけて、 二番目以降のリスト (n2,s2):ssshellCount' を適用し、 その出力と (n1,s1) をくっつけています。

 これで、リストに同じシェルのタプルが続けば どんどんタプル中の数字が加算されていき、 そうでなければ次のシェルの個数の集計が始まるという 処理になりました。このような再帰処理は、 for文の代わりとなるため、 Haskellではよく使います。

 実行してみましょう。図11のように答えが出ます。

  • 図11: q1_2_6の実行
1
2
3
4
5
6
ueda@remote:~/GIT/USPMAG/SRC$ cat /etc/passwd | ./q1_2_6
3 /bin/bash
4 /bin/false
17 /bin/sh
1 /bin/sync
1 /usr/sbin/nologin

4.8. もっと良い別解

 ・・・でめでだしめでたしだったのですが、 一通り説明を終えて、 「もっと単純化できるんじゃね?」 と気づいたので、そちらのコードも図12に晒しておきます [8] 。 回答は無限にあるので、もっといい方法があったら教えてください。 それにしても、ちょっと回りくどかったかもしれません・・・。

  • 図12: 回りくどくないq1_2_7.hs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_7.hs
import Data.List
import Data.List.Split

main = getContents >>= putStr . main'

main' :: String -> String
main' cs = unlines $ shellCount $ sort $ map getShell (lines cs)

getShell :: String -> String
getShell ln = last $ splitOn ":" ln

shellCount :: [String] -> [String]
shellCount [] = []
shellCount (s:ss) = (show (1 + length t) ++ (' ':s)) : shellCount d
 where t = takeWhile (== s) ss
 d = dropWhile (== s) ss

 このコードでは main'getShell からシェルの名前を受け取ったら すぐに sort して shellCount に渡しています。 shellCount はシェルの名前が入った文字列のリスト [String] を受け取りますが、 それを where 以下で「先頭と同じシェルのリスト」 と、「それ以外のリスト」に分けています。 それぞれ「 td 」と名付けています。

  takeWhiledropWhile の動作を図13に示しておきます。

  • 図13: takeWhile, dropWhile
1
2
3
4
Prelude> takeWhile (==1) [1,1,2,3,4]
[1,1]
Prelude> dropWhile (==1) [1,1,2,3,4]
[2,3,4]

 これで、 t の長さに1を足したものが該当するシェルの個数となります。 また、 d を再度 shellCount に入力すれば、 再帰的に各シェルの個数を集計できます。

 さらにこのコードを図14のように縮めてみます。 だんだんシェル芸に見えてきませんでしたか? だんだんシェル芸に見えてきませんでしたか?

  • 図14: mainがシェル芸っぽいq1_2_8.hs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ueda@remote:~/GIT/USPMAG/SRC$ cat q1_2_8.hs
import Data.List
import Data.List.Split

main = getContents >>= putStr . unlines . shellCount .
 sort . map (last . splitOn ":") . lines

shellCount :: [String] -> [String]
shellCount [] = []
shellCount (s:ss) = (show (1 + length t) ++ (' ':s)) : shellCount d
 where t = takeWhile (== s) ss
 d = dropWhile (== s) ss

4.9. 終わりに

 今回は第1回シェル芸勉強会の2問目の答えまで行き着きました。 パターンマッチ、ガード、再帰処理と、 Haskellっぽいものがたくさんでてきましたが、 粘り強く文法を確認していただければと。

 次回は3問目から!キリがよい!

4.10. お知らせ:コード募集

本稿で出た問題のHaskellのコードを、 名前あるいはハンドルネームと共に送ってください。 短いもの、あるいは変態的なものをお願いいたします。

email: 編集部のメールアドレス

脚注

[1]順に助教、アドバイザリーフェロー、会長。
[2]ごめんなさいごめんなさい。ウルトラスーパーごめんなさい。
[3]この物語はノンフィクションです。
[4]「型クラス」というのがキーワードですのでご調査を。
[5]反省の色がない。
[6]おい。
[7]Int あるいは Integer
[8]記事を書いていて一番怖い現象が起きた瞬間である。そのまま押し切る(おい)。
[9]【名】死刑執行、処刑


Article Info

created: 2014年 11月 19日 水曜日 23:34:52 JST
modified: 2017年 10月 1日 日曜日 10:50:27 JST
views: 396
keywords: