代表技術通信～Get Programming with Haskell⑧

草場代表

2020/12/02

こんばんは。代表の草場です。

Haskell触ります。「Get Programming with Haskell」についてです。レッスン6の続きです。

レッスン6. リスト

レッスン6を読んだ後は

リストを構成する部品を識別する
リストの作り方を知る
関数型プログラミングにおけるリストの役割を理解する
リスト上で共通の機能を使用する
怠惰な評価(lazy evaluation)の基本を学ぶ

がわかるようになります。

Haskell（および関数型プログラミング全般）では、基本的なデータ構造はリストです。リストを分解して元に戻す基本を学び、Haskell が提供するリストに不可欠な関数のいくつかを学びます。最後に、Haskellのもう一つのユニークな機能である遅延評価をみます。遅延評価を利用し、無限に長いリストを表現して作業することができます。

次のように考えてみます。

あなたは1万人の従業員がいる会社で働いていますが、その中の何人かが仕事後のソフトボールチームでプレーしたいと思っています。この会社には5つのチームがあり、色にちなんで名付けられています。

teams = ["red","yellow","orange","blue","purple"]

従業員のリストを持っていて、それらをできるだけ均等に正しいチームにマッチさせたいとします。このタスクを実行するためにHaskellのリスト関数を使用できる簡単な方法は何でしょうか？

6.1. リストのアナトミー

リストは関数型プログラミングにおいて最も重要なデータ構造です。重要な理由の一つは、リストが本質的に再帰的であるということです。リストとは、空のリストか、別のリストに続く要素のことです。リストを分解して構築することは、関数型プログラミングの多くのテクニックの基本的なツールです。

リストを分解するときの主な要素は、head、tail、そしてend（[]で表される）です。headはリストの最初の要素にすぎません。

GHCi> head [1,2,3]
1
GHCi> head [[1,2],[3,4],[5,6]]
[1,2]

endはheadの後に残っているリストの残りです。

GHCi> tail [1,2,3]
[2,3]
GHCi> tail [3]
[]

要素が1つだけのリストのendは[]で、これがリストの終わりを示します。このリストの終わりは空のリストです。しかし、空のリストは、先頭も末尾もないので、他のリストとは異なります。headやtailを[]で呼び出すとエラーになります。headとtailを見てみると、リストを扱う際の再帰的な性質が見えてきます。

関数型プログラミングでは、リストを構築することはリストを分解するのと同じくらい重要です。リストを構築するために必要なのは、1つの関数とinfix演算子(:)だけで、これはcons(コンストラクトの略)と呼ばれています。ここではこの操作を consing と呼ぶことにします。リストを作るには、ある値を取り、それを別のリストと一緒に cons する必要があります。リストを作る最も簡単な方法は、空のリストで値をconsすることです。

GHCi> 1:[]
[1]

Haskellでは、リストはすべてコンシング演算の束として表現され、[…]記法は構文的な糖分（syntactic sugar、物事を読みやすくするためだけに設計されたプログラミング言語の構文の機能)です。

GHCi> 1:2:3:4:[]
[1,2,3,4] GHCi> (1,2):(3,4):(5,6)：[]
[(1,2),(3,4),(5,6)]

これらのリストはすべて空リスト[]で終わることに注意してください。定義によれば、リストは常に別のリストと値を組み合わせたものです。必要であれば、既存のリストの先頭に値を付けることができます。

GHCi> 1:[2,3,4]
[1,2,3,4]

これまでに見てきた文字列は、それ自体が文字のリストのための構文的な糖質であることは注目に値します。

GHCi>['h','e','l','l','o']
"hello"
GHCi> 'h':'e':'l':'l':'o':[]
"hello"

覚えておくべき重要なことは、Haskellではリストのすべての要素が同じ型でなければならないということです。例えば、”ello “は単なる文字のリストであり、’h’ (シングルクォーテーション)は文字だからです。

GHCi> 'h': "ello"
"hello"

しかし、”h “は1文字のリストであり、”ello “の中の値は個々の文字なので、”h”（二重引用符）を “ello “に代入することはできません。これは構文上の糖質を取り除くとより明らかになります。

GHCi> "h": "ello" 1
GHCi> ['h']:['e','l','l','o'] 2
GHCi> 'h':[]:'e':'l':'o':[] 3

1：エラー!
2：砂糖の層が1つ削除された同じコード
3：完全に脱芒

2つのリストを結合したい場合は、++を使って結合する必要があります。

GHCi> "h" ++ "ello"
"hello"
GHCi> [1] ++ [2,3,4]
[1,2,3,4]

consingは、リスト上で再帰的な関数を書く際に不可欠な部分なので、理解することが重要です。関数型プログラミングにおけるほぼすべての逐次操作には、リストを構築したり、リストを分割したり、あるいはそれらを組み合わせたりすることが含まれます。

6.2. リストと怠惰な評価

Haskellではリストが非常に重要なので、データの範囲を素早く生成する方法はたくさんあります。以下にいくつかの例を示します。

GHCi> [1 ... 10] 1
[1,2,3,4,5,6,7,8,9,10]
GHCi> [1,3 ... 10] 2
[1,3,5,7,9]
GHCi> [1, 1.5 ... 5] 3
[1.0,1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0]
GHCi> [1,0 ... -10] 4
[1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]

1： 1から10までの数字のリストを生成します。
2：次のステップの3を加えると奇数が生成されます。
3： 0.5の増分リストを生成する
4：減分リストを生成する

範囲に上限を付け忘れた場合はどうなるのでしょうか？

GHCi> [1 ...]
[1,2,3,4,5,6,7,8,9,10,11,12 ..

無限のリストが生成されます。面白いのは、このリストを変数に代入したり、関数で使うことができることです。

Simple x = x
longList = [1 ... ]
stillLongList = simple longList

このコードはコンパイルされます。無限リストを定義し、それを関数で使用できます。Haskellは遅延評価と呼ばれる特殊な評価を使用しています。遅延評価では、必要になるまでコードは評価されません。longListの場合、リスト内の値は計算に必要ありませんでした。

遅延評価には長所と短所があります。メリットのいくつかを見るのは簡単です。まず、絶対に必要のないコードは計算されないという計算上の利点があります。もう一つの利点は、無限リストのような興味深い構造を定義して使用できることです。これは多くの実用的な問題に役立ちます。
遅延評価の欠点はあまり目立ちません。最大のデメリットは、コードの性能を推論するのがはるかに困難になることです。この些細な例では、simple に渡された引数が評価されないことは簡単にわかりますが、もう少し複雑になると、このことはそれほど明白ではなくなります。さらに大きな問題は、評価されない関数の大規模なコレクションを簡単に構築できることです。

6.3. リスト上の共通関数

リストは非常に重要なものなので、Haskell の標準ライブラリモジュールである Prelude には、さまざまな便利な関数が組み込まれています。ここまでで、リストを分解して元に戻すことができる head, tail, : と ++ を見てきました。リストには他にもたくさんの便利な関数があり、Haskell を書くときに頻繁に出てきますので、それらをよく知っておくとよいでしょう。

6.3.1. !!演算子

リストの特定の要素にインデックスでアクセスしたい場合は、!！演算子を使います。リストと数字を受け取り、リストのその位置にある要素を返します。リストのインデックスは0から始まります。

GHCi> [1,2,3] !! 0
1
GHCi> [puppies]」!! 4
'i'
GHCi> [1...10] !! 11
*** Exception: Prelude.!!: index too large

どんなインフィックス演算子でも、括弧で囲むことでプレフィックス関数のように使うことができます。

GHCi> (!!) [1,2,3] 0
1

プレフィックス記法を使用することで、部分的な適用などを容易にすることができます。プレフィックス記法は、他の関数の引数として演算子を使用する際にも便利です。接頭辞演算子を使用して部分適用を行うこともできますが、式を括弧で囲む必要があります。

GHCi> paExample1 = (!!) "dog"
GHCi> paExample1 2
'g'
GHCi> paExample2 = ("dog" !!)
GHCi> paExample2 2
'g'

paExample2 では、infix のバイナリ演算子で部分適用がどのように動作するかを見ています。セクションと呼ばれるバイナリ演算子で部分適用を行うには、式を括弧で囲む必要があります。右側の引数だけを含めると、関数は左端の引数を待ち、左側の引数だけを含めると、右側の引数を待つ関数が得られます。右の引数の部分適用を作成するpaExample3です。

GHCi> paExample3 = (!! 2)
GHCi> paExample3 "dog"
'g'

セクションについて覚えておくべき重要なことは、括弧は任意ではないということです。

6.3.2.長さ

length関数は、リストの長さを調べます。

GHCi> length [1..20]
20
GHCi>length[(10,20),(1,2),(15,16)
3
GHCi>length "quicksand"
9

6.3.3. リバース

リバースはリストを反転させます。

GHCi> reverse [1,2,3]
[3,2,1]
GHCi> reverse "cheese"
"eseehc"

リバースを使って基本的な回文チェッカーを作ることができます。

isPalindrome word = word == reverse word

GHCi> isPalindrome "cheese"
False
GHCi> isPalindrome "racecar"
True
GHCi> isPalindrome [1,2,3]
False
GHCi> isPalindome [1,2,1]
True

6.3.4. elem

elem関数は、値とリストを受け取り、その値がリストにあるかどうかをチェックします。

GHCi> elem 13 [0,13 .. 100]
True
GHCi> elem 'p' "cheese"
False

elem は、読みやすさのために infix 演算子として扱いたい関数です。どんなバイナリ関数でも、バッククォート (`) で囲むことで infix 演算子として扱うことができます。たとえば、関数 respond は文字列に感嘆符があるかどうかによって異なるレスポンスを返します。

respond phrase = if '!' `elem` phrase
then "wow!"
else "uh.. okay"

GHCi> respond "hello"
"uh.. okay"
GHCi> respond "hello!"
"wow!"

6.3.5. テイクアンドドロップ

take関数は数値とリストを引数にとり、リストの最初のn個の要素を返します。

GHCi> take 5 [2,4..100]
[2,4,6,8,10]
GHCi> take 3 "wonderful"
"won"

リストが持っている値よりも多くの値を要求した場合、take はそれが可能な値をエラーなく与えます。

GHCi> take 1000000 [1] [1]

take は、リスト上の他の関数と組み合わせて使うのが最も効果的です。リストの最後の n 個の要素を取得するために take と reverse を組み合わせることができます。

takeLast n aList = reverse (take n (reverse aList))

GHCi> takeLast 10 [1...100]
[91,92,93,94,95,96,97,98,99,100]

drop関数は、リストの最初のn個の要素を削除することを除いて、takeと似ています。

GHCi> drop 2 [1,2,3,4,5]
[3,4,5]
GHCi> drop 5 "very awesome"
"awesome"

6.3.6.zip

zipは、2つのリストをタプルのペアに結合したいときに使用します。zip の引数は 2 つのリストです。片方のリストの方が長い場合は、2つのリストのうちの1つが空になると、zipは停止します。

GHCi> zip [1,2,3] [2,4,6]
[(1,2),(2,4),(3,6)]
GHCi> zip "dog" "rabbit"
[('d','r'),('o','a'),('g','b')]
GHCi> zip ['a' ... 'f'] [1 ...]
[('a',1),('b',2),('c',3),('d',4),('e',5),('f',6) ]

6.3.7. サイクル

cycle関数は特に興味深いもので、遅延評価を使って無限リストを作成します。リストが与えられると、サイクルはそのリストを無限に繰り返します。これはやや役に立たないように見えるかもしれませんが、驚くほど多くの状況で便利です。例えば、数値計算ではn個のリストが必要になることがよくあります。cycleを使えば、この関数を作るのは簡単です。

ones n = take n (cycle [1])

GHCi> ones 2
[1,1]
GHCi> ones 4
[1,1,1,1]

サイクルは、リストのメンバーをグループに分けるのに非常に便利です。ファイルのリストを分割して、それらをn個のサーバーに配置したり、同様に従業員をn個のチームに分散させたりしたいと想像してみてください。一般的な解決策は、いくつかのグループとリストを受け取り、グループを循環させてメンバーを割り当てる新しい関数の assignToGroups を作ることです。

assignToGroups n aList = zip groups aList
where groups = cycle [1..n]

GHCi> assignToGroups 3 ["file1.txt","file2.txt","file3.txt"
,"file4.txt","file5.txt","file6.txt","file7.txt"
,"file8.txt"]

[(1,"file1.txt"),(2,"file2.txt"),(3,"file3.txt"),(1,"file4.txt"),
(2,"file5.txt"),(3,"file6.txt"),(1,"file7.txt"),(2,"file8.txt")]

GHCi> assignToGroups 2 ["Bob","Kathy","Sue","Joan","Jim","Mike"]
[(1,"Bob"),(2,"Kathy"),(1,"Sue"),(2,"Joan"),(1,"Jim"),(2,"Mike")]

リスト上のすべての関数が標準のPreludeモジュールに含まれているわけではありません。Preludeに自動的に含まれるものを含め、すべてのリスト関数はData.Listモジュールに含まれています。