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

Wed Nov 19 23:34:52 JST 2014 (modified: Sun Oct 1 10:50:27 JST 2017)
views: 2832, keywords: この記事は最終更新日が6年以上前のものです。

出典: USP magazine 7月号

各号の一覧へ

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]【名】死刑執行、処刑
ノート   このエントリーをはてなブックマークに追加 
 

やり散らかし一覧

記事いろいろ