実例によるPureScript

ウェブのための関数型プログラミング

Phil Freeman, "PureScript by Example - Functional Programming for the Web"

4 再帰、マップ、畳み込み

4.1 この章の目標

この章では再帰関数を使ってどのようにアルゴリズムを構造化するかについて見ていきましょう。再帰はこの本を通じて使用する関数型プログラミングの基本的な手法です。

また、PureScriptの標準ライブラリから標準的な関数をいくつか扱います。mapfoldのような関数だけでなく、filterconcatMapといった便利で特殊なものについても見ていきます。

この章では仮想的なファイルシステムを操作する関数のライブラリを動機付けに用います。この章で学ぶ手法を応用して、模擬的なファイルシステムによって表されるファイルのプロパティを計算する関数を記述します。

4.2 プロジェクトの準備

この章のソースコードには、src/Data/Path.purssrc/FileOperations.pursという2つのファイルが含まれています。

Data.Pathモジュールには、仮想ファイルシステムが含まれています。このモジュールの内容を変更する必要はありません。

FileOperationsモジュールは、Data.Path APIを使用する関数が含まれています。演習への回答はこのファイルだけで完了することができます。

このプロジェクトには以下のBower依存関係があります。

4.3 はじめに

再帰は一般のプログラミングでも重要な手法ですが、純粋関数型プログラミングでは特に当たり前のように用いられます。この章で見ていくように、再帰はプログラムの変更可能な状態を減らすために役立つからです。

再帰は分割統治(Divide and conquer)戦略と密接な関係があります。分割統治とはすなわち、いろいろな入力に対する問題を解決するために、入力を小さな部分に分割し、それぞれの部分について問題を解いて、部分ごとの答えから最終的な答えを組み立てるということです。

それでは、PureScriptにおける再帰の簡単な例をいくつか見てみましょう。

次は階乗関数(factorial function)のよくある例です。

fact :: Number -> Number
fact 0 = 1
fact n = n * fact (n - 1)

部分問題へ問題を分割することによって階乗関数がどのように計算されるかがわかります。より小さい数へと階乗を計算していくということです。ゼロに到達すると答えは直ちに求まります。

次はフィボナッチ関数(Fibonnacci function)を計算するという、これまたよくある例です。

fib :: Number -> Number
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

やはり部分問題の解決策を考えることで全体を解決していることがわかります。この場合、fib (n - 1)fib (n - 2)という式に対応した2つの部分問題があります。これらの2つの部分問題が解決されているときに、部分的な答えを加算することで答えを組み立てることができます。

4.4 配列上での再帰

再帰関数の定義は、Number型だけに限定されるものではありません!本書の後半でパターン照合(pattern matching)を扱うときに、いろいろなデータ型の上での再帰関数について見ていきますが、今は数と配列に限っておきます。

入力がゼロでないかどうかについて分岐するのと同じように、配列の場合も、配列が空でないかどうかについて分岐していきます。再帰を使用して配列の長さを計算する次の関数を考えてみます。

import Data.Array (null)
import Data.Array.Unsafe (tail)

length :: forall a. [a] -> Number
length arr = 
  if null arr
  then 0 
  else 1 + length (tail arr)

この関数では配列が空かどうかで分岐するために if ... then ... else式を使っています。このnull関数は配列が空のときにtrueを返します。空の配列の長さはゼロであり、空でない配列の長さは配列の先頭を取り除いた残りの部分の長さより1大きいというわけです。

この例はJavaScriptで配列の長さを調べるのにはどうみても実用的な方法とはいえませんが、次の演習を完了するための手がかりとしては充分でしょう。

演習

  1. (簡単) 入力が偶数であるとき、かつそのときに限りtrueに返すような再帰関数を書いてみましょう。

  2. (少し難しい) 配列内の偶数の数を数える再帰関数を書いてみましょう。ヒントData.Array.Unsafeモジュールの head関数を使用します。

4.5 マップ

map関数は配列に対する再帰関数のひとつです。これは、配列の各要素に順番に関数を適用することによって、配列の要素を変換するために使用されます。そのため、配列の内容は変更されますが、その形状(ここでは「長さ」)は保存されます。

本書で後ほど型クラス(type class)を扱うとき、形状を保存しながら型構築子のクラスを変換する関手(functor)と呼ばれる関数を紹介しますが、その時にmap関数は関手の具体例であることがわかります。

それではpscimap関数を試してみましょう。

$ psci

> :i Data.Array
> map (\n -> n + 1) [1, 2, 3, 4, 5]

[2, 3, 4, 5, 6]

mapがどのように使われているかに注目してください。最初の引数には配列がどのように対応付けられるかを示す関数、第2引数には配列そのものを渡します。

4.6 中置演算子

バッククォート(`)で関数名を囲むと、対応関係を表す関数と配列の間にmap関数を書くことができます。

> (\n -> n + 1) `map` [1, 2, 3, 4, 5]

[2, 3, 4, 5, 6]

この構文は中置関数適用と呼ばれ、どんな関数でもこのように中置することができます。普通は2引数の関数に対して使うのが最も適切でしょう。

配列を扱うときは、map関数と等価な<$>という演算子が存在します。この演算子は他の二項演算子と同じように中置で使用することができます。

> (\n -> n + 1) <$> [1, 2, 3, 4, 5]

[2, 3, 4, 5, 6]

注意<$>の型は実際にはmapよりも一般的ですが、中置適用のほうが自然であるなら、mapの代わりに<$>を使ってもたいていの場合は大丈夫です。

それではmap の型を見てみましょう。

> :t map
forall a b. (a -> b) -> [a] -> [b]

map関数に適用するときにはabという2つの型を自由に選ぶことができると、この型は言っています。aは元の配列の要素の型で、bは目的の配列の要素の型です。もっと言えば、 mapが配列要素の型を変化させても構わないということです。例えば、数値を文字列に変換するのにマップを使用することができます。

> show <$> [1, 2, 3, 4, 5]

["1","2","3","4","5"]

中置演算子 <$>は特別な構文のように見えるかもしれませんが、実際には普通のPureScript関数です。中置構文を使用した単なる適用にすぎません。実際、括弧でその名前を囲むと、この関数を通常の関数のように使用することができます。これは、配列に対するmapの代わりに、括弧で囲まれた(<$>)という名前を使うことができるということです。

> (<$>) show [1, 2, 3, 4, 5]

["1","2","3","4","5"]

新しい中置演算子を定義するには、関数と同じ記法を使います。演算子名を括弧で囲み、あとは普通の関数のようにその中置演算子を定義します。たとえば、 Data.Arrayモジュールでは次のようにrange関数と同じ振る舞いの中置演算子 (..)を定義しています。

(..) :: Number -> Number -> [Number]
(..) = range

この演算子は次のように使うことができます。

> 1 .. 5

[1, 2, 3, 4, 5]

> show <$> (1 .. 5)
  
["1","2","3","4","5"]

注意: 独自の中置演算子は自然な構文を持った領域特化言語を定義するのに優れた手段になりえます。ただし、使用には充分注意してください。初心者が読めないコードになることがありますから、新たな演算子の定義には慎重になるのが賢明です。

上記の例では、1 .. 5という式は括弧で囲まれていましたが、実際にはこれは必要ありません。なぜなら、Data.Arrayモジュールは、 <$>に割り当てられた優先順位より 高い優先順位を.. 演算子に割り当てているからです。PureScriptでは予約語infixを使用して独自の演算子に優先順位を割り当てる方法が提供されています。

infix 5 ..

ここでは<$>の優先順位よりも高い優先順位5を(..)に割り当てており、これはつまり括弧を付け加える必要がないということです。

> show <$> 1 .. 5
  
["1","2","3","4","5"]

中置演算子に左結合性または右結合性を与えたい場合は、代わりに予約語 infixlinfixrを使います。

4.7 配列のフィルタリング

Data.Arrayモジュールでは他にも、mapと同様によく使われる関数filterも提供しています。 この関数は、述語関数に適合する要素のみを残し、既存の配列から新しい配列を作成する機能を提供します。

たとえば、1から10までの数で、偶数であるような数の配列を計算したいとします。これは次のように行うことができます。

> :i Data.Array

> filter (\n -> n % 2 == 0) (1 .. 10)
[2,4,6,8,10]

演習

  1. (簡単) map関数や<$>関数を使用して、 配列に格納された数のそれぞれの平方を計算する関数を書いてみましょう。

  2. (簡単) filter関数を使用して、数の配列から負の数を取り除く関数を書いてみましょう。

  3. (やや難しい) filter関数と同じ意味の中置演算子<$?>を定義してみましょう。先ほどの演習の回答を、この新しい演算子を使用して書き換えてください。また、psciでこの演算子の優先順位と結合性を試してみてください。

4.8 配列の平坦化

Data.Arrayで定義されている配列に関する標準の関数としては、concat関数もあります。 concatは配列の配列をひとつの配列へと平坦化します。

> :i Data.Array
> :t concat 

forall a. [[a]] -> [a]

> concat [[1, 2, 3], [4, 5], [6]]

[1, 2, 3, 4, 5, 6]

関連する関数として、concatmapを組み合わせたようなconcatMapと呼ばれる関数もあります。mapは(相異なる型も可能な)値からの値への関数を引数に取りますが、それに対してconcatMapは値から値の配列の関数を取ります。

実際に動かして見てみましょう。

> :i Data.Array

> :t concatMap
forall a b. (a -> [b]) -> [a] -> [b]

> concatMap (\n -> [n, n * n]) (1 .. 5)
  
[1,1,2,4,3,9,4,16,5,25]

ここでは、数をその数とその数の平方の2つの要素からなる配列に写す関数 \n -> [n, n * n]を引数にconcatMapを呼び出しています。結果は、1から5の数と、そのそれぞれの数の平方からなる、10個の数になります。

concatMapがどのように結果を連結しているのかに注目してください。渡された関数を元の配列のそれぞれの要素について一度づつ呼び出し、その関数はそれぞれ配列を生成します。最後にそれらの配列を単一の配列に押し潰し、それが結果となります。

mapfilterconcatMapは、「配列内包表記」(array comprehensions)と呼ばれる配列に関するあらゆる関数の基盤を形成しています。

4.9 配列内包表記

n の2つの因数を見つけたいとしましょう。これを行うための簡単​​な方法のひとつとしては、総当りで行う方法があります。つまり、1からnの数のすべての組み合わせを生成し、それを乗算してみるわけです。もしその積がnなら、nの因数の組み合わせを見つけたということになります。

配列内包表記を使用すると、この計算を実行することができます。psciを対話式の開発環境として使用し、ひとつづつこの手順を進めていきましょう。

n以下の数の組み合わせの配列を生成する最初の手順は、concatMapを使えば行うことができます。

1 .. nのそれぞれの数を配列1 .. nへとマッピングすることから始めましょう。

> let pairs n = concatMap (\i -> 1 .. n) (1 .. n)

この関数をテストしてみましょう。

> pairs 3
[1,2,3,1,2,3,1,2,3]

これは求めているものとはぜんぜん違います。単にそれぞれの組み合わせの2つ目の要素を返すのではなく、ペア全体を保持することができるように、内側の1 .. nの複製について関数をマッピングする必要があります。

> let pairs n = concatMap (\i -> map (\j -> [i, j]) (1 .. n)) (1 .. n)

> pairs 3
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

いい感じになってきました。しかし、[1, 2][2, 1]の両方があるように、余計な組み合わせが生成されています。jiからnの範囲に限定することで、2つ目の場合を取り除くことができます。

> let pairs n = concatMap (\i -> map (\j -> [i, j]) (i .. n)) (1 .. n)

> pairs 3
[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]

すばらしい!因数の候補のすべての組み合わせを得たので、filterを使って、積が与えられたnであるような組み合わせを選択することができます。

> :i Data.Foldable

> let factors n = filter (\pair -> product pair == n) (pairs n)
  
> factors 10
[[1,10],[2,5]]

このコードでは、purescript-foldable-traversableライブラリのData.Foldableモジュールにあるproduct関数を使っています。

うまくいきました!重複のなく、因数の組み合わせの正しい集合を見つけることができました。

4.10  do記法

機能は実現できましたが、このコードの可読性は大幅に向上することができます。mapconcatMapはとても基本的な関数で、do記法(do notation)と呼ばれる特別な構文の基盤をなしています(もっと厳密にいえば、それらの一般化である<$>>>=が基盤をなしています)。

注意mapconcatMap配列内包表記を書けるようにしているように、もっと一般的な演算子である<$>>>=モナド内包表記(monad comprehensions)と呼ばれているものを書けるようにします。本書の後半ではモナド(monad)の例をたっぷり見ていくことになりますが、それはこの章ではありません。

do記法を使うと、先ほどのfactors関数を次のように書き直すことができます。

factors :: Number -> [[Number]]
factors n = filter (\xs -> product xs == n) $ do
  i <- 1 .. n
  j <- i .. n
  return [i, j]

予約語 doはdo記法を使うコードのブロックを導入します。このブロックは幾つかの型の式で構成されています。

この新しい記法を使うとアルゴリズムの構造がわかりやすくなることがあります。心のなかで<-を「選ぶ」という単語に置き換えるとすると、「1からnの間の要素iを選び、それからiからnの間の要素jを選び、[i, j]を返す」というように読むことができるかもしれません。

最後の行のreturn関数は予約語ではないことに注意してください。これは、他の関数と同様にpsciで評価することができる、通常の関数です。ただし、psciで評価するには型を明示しなければなりません。

> return [1, 2] :: [[Number]]
[[1, 2]]

配列の場合、returnは単に1要素の配列を作成します。実際に、returnの代わりにこの形式を使うようにfactors関数を変更することもできます。

factors :: Number -> [[Number]]
factors n = filter (\xs -> product xs == n) $ do
  i <- 1 .. n
  j <- i .. n
  [[i, j]]

そして、結果は同じになります。

4.11 ガード

factors関数を更に改良する方法としては、filterを配列内包表記の内側に移動するというものがあります。これは purescript-control ライブラリにある Control.MonadPlusモジュールのguard関数を使用することで可能になります。

factors :: Number -> [[Number]]
factors n = do
  i <- range 1 n
  j <- range i n
  guard $ i * j == n
  return [i, j]

returnと同じように、guard関数は予約語ではありません。どのように動作するかを理解するために、 psciで通常の関数のようにguardを適用してみましょう。

guard関数の型は、ここで必要になる以上に一般的な型です。

> :i Control.MonadPlus
> :t guard

forall m. (MonadPlus m) => Boolean -> m Unit

今回の場合は、psciは次の型を報告するものと考えてください。

Boolean -> [Unit]

次の計算の結果から、配列におけるguard関数について今知りたいことはすべてわかります。

> :i Data.Array
> length $ guard true

1

> length $ guard false
  
0

つまり、 guardtrueに評価される式を渡された場合、単一の要素を持つ配列を返すのです。もし式が falseと評価された場合は、その結果は空です。

ガードが失敗した場合、配列内包表記の現在の分岐は、結果なしで早めに終了されることを意味します。これは、guard の呼び出しが、途中の配列に対してfilterを使用するのと同じだということです。これらが同じ結果になることを確認するために、 factorsの二つの定義を試してみてください。

演習

  1. (簡単)factors関数を使用して、整数の引数が素数であるかどうかを調べる関数 isPrimeを定義してみましょう。

  2. (やや難しい) 2つの配列の直積集合を見つけるための関数を書いてみましょう。直積集合とはつまり、要素abのすべての組み合わせの集合です。ここでaは最初の配列の要素、bは2つ目の配列の要素です。

  3. (やや難しい) ピタゴラスの三つ組数とは、a² + b² = c²を満たすような3つの数の配列 [a, b, c]のことです。配列内包表記の中でguard関数を使用して、数nを引数に取り、どの要素もnより小さいようなピタゴラスの三つ組数すべてを求める関数を書いてみましょう。その関数はNumber -> [[Number]]という型を持っていなければなりません。

  4. (難しい) Data.Foldableから any関数を探しましょう。配列内包表記の代わりにany関数を使用してfactors関数を書き換えてみましょう。注意psci によって報告されるanyの型は、必要以上に一般的です。この演習での目的には、any の型はforall a. (a -> Boolean) -> [a] -> Boolean であると考えることができます。

  5. (鬼のように難しい)factors関数を使用して、数 nのすべての因数分解を求める関数factorizationsを定義してみましょう。数nの因数分解とは、それらの積がnであるような整数の配列のことです。ヒント:1は因数ではないと考えてください。また、無限再帰に陥らないように注意しましょう。

4.12 畳み込み

再帰を利用して実装される興味深い関数としては、配列に対する左畳込み(left fold)と右畳み込み(right fold)があります。

psciを使って、Data.Foldableモジュールをインポートし、foldlfoldr関数の型を調べることから始めましょう。

> :i Data.Foldable

> :t foldl
forall a b f. (Foldable f) => (b -> a -> b) -> b -> f a -> b

> :t foldr
forall a b f. (Foldable f) => (a -> b -> b) -> b -> f a -> b

これらの型は、現在興味があるものよりも一般的です。この章の目的では、 psciは以下の(より具体的な)答えを与えていたと考えておきましょう。

> :t foldl
forall a b. (b -> a -> b) -> b -> [a] -> b

> :t foldr
forall a b. (a -> b -> b) -> b -> [a] -> b

どちらの型でも、aは配列の要素の型に対応しています。型'b'は、配列を走査(traverse)したときの結果を蓄積する「累積器」(accumulator)の型だと考えることができます。

foldl関数とfoldr関数の違いは走査の方向です。 foldrが「右から」配列を畳み込むのに対して、foldlは「左から」配列を畳み込みます。

これらの関数の動きを見てみましょう。foldlを使用して数の配列の和を求めてみます。型 aNumberになり、結果の型bNumberとして選択することができます。ここでは、次の要素を累積器に加算するNumber -> Number -> Numberという型の関数、Number型の累積器の初期値、和を求めたいNumberの配列という、3つの引数を提供する必要があります。最初の引数としては、加算演算子を使用することができますし、累積器の初期値はゼロになります。

> foldl (+) 0 (1 .. 5)
15

この場合では、引数が逆になっていても (+)関数は同じ結果を返すので、foldlfoldrのどちらでも問題ありません。

> foldr (+) 0 (1 .. 5)
15

foldlfoldrの違いを説明するために、畳み込み関数の選択が影響する例も書いてみましょう。加算関数の代わりに、文字列連結を使用して文字列を作ってみます。

> foldl (\acc n -> acc ++ show n) "" [1,2,3,4,5]
"12345"

> foldr (\n acc -> acc ++ show n) "" [1,2,3,4,5]
"54321"

これは、2つの関数の​​違いを示しています。左畳み込み式は、以下の関数適用と同等です。

((((("" ++ show 1) ++ show 2) ++ show 3) ++ show 4) ++ show 5)

それに対し、右畳み込みは以下に相当します。

((((("" ++ show 5) ++ show 4) ++ show 3) ++ show 2) ++ show 1)

4.13 末尾再帰

再帰はアルゴリズムを定義するための強力な手法ですが、問題も抱えています。入力が大きすぎる場合、JavaScriptで再帰関数を評価しようとするとスタックオーバーフローでエラーを起こす可能性があるのです。

psciで次のコードを入力すると、この問題を簡単に検証できます。

> let f 0 = 0
      f n = 1 + f (n - 1)

> f 10
10
  
> f 10000
RangeError: Maximum call stack size exceeded

これは問題です。関数型プログラミングの基本的な手法として再帰を採用しようとするなら、無限かもしれない再帰でも扱える方法が必要です。

PureScriptは末尾再帰最適化(tail recursion optimization)の形でこの問題に対する部分的な解決策を提供しています。

注意:この問題へのより完全な解決策としては、いわゆるトランポリン(trampolining)を使用したライブラリで実装する方法がありますが、それはこの章で扱う範囲を超えています。

末尾再帰の最適化が可能かどうかには条件があります。末尾位置(tail position)にある関数の再帰的な呼び出しは、スタックフレームが確保されないジャンプに置き換えることができます。それが関数が戻るより前の最後の呼び出しであるとき、呼び出しは末尾位置にあるといいます。なぜこの例でスタックオーバーフローを観察したのかはこれが理由です。このfの再帰呼び出しは、末尾位置ではないからです。

実際には、PureScriptコンパイラは再帰呼び出しをジャンプに置き換えるのではなく、再帰的な関数全体をwhileループに置き換えます。

以下はすべての再帰呼び出しが末尾位置にある再帰関数の例です。

fact :: Number -> Number -> Number
fact 0 acc = acc
fact n acc = fact (n - 1) (acc * n)

factへの再帰呼び出しは、この関数の中で起こる最後のものである、つまり末尾位置にあることに注意してください。

4.14 累積器

末尾再帰ではない関数を末尾再帰関数に変える一般的な方法としては、累積器引数(accumulator parameter)を使用する方法があります。結果を累積するために返り値を使うと末尾再帰を妨げることがありますが、それとは対照的に累積器引数は返り値を累積する関数へ追加される付加的な引数です。

たとえば、入力配列を逆順にする、この配列の再帰を考えてみましょう。

reverse :: forall a. [a] -> [a]
reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

この実装は末尾再帰ではないので、大きな入力配列に対して実行されると、生成されたJavaScriptはスタックオーバーフローを発生させるでしょう。しかし、代わりに、結果を蓄積するための2つ目の引数を関数に導入することで、これを末尾再帰に変えることができます。

reverse :: forall a. [a] -> [a]
reverse = reverse' []
  where
  reverse' acc [] = acc
  reverse' acc (x : xs) = reverse' (x : acc) xs

ここでは、配列を逆転させる作業を補助関数 reverse'に委譲しています。関数 `reverse'が末尾再帰的であることに注目してください。 その唯一の再帰呼び出しは、最後の場合の末尾位置にあります。これは、生成されたコードがwhileループとなり、大きな入力でもスタックが溢れないことを意味します。

reverse のふたつめの実装を理解するためには、部分的に構築された結果を状態として扱うために、補助関数reverse'で累積器引数の使用することが必須であることに注意してください。結果は空の配列で始まりますが、入力配列の要素ひとつごとに、ひとつづつ大きくなっていきます。後の要素は配列の先頭に追加されるので、結果は元の配列の逆になります!

累積器を「状態」と考えることもできますが、直接に変更がされているわけではないことにも注意してください。この累積器は不変の配列であり、計算に沿って状態受け渡すために、単に関数の引数を使います。

4.15 明示的な再帰より畳み込みを選ぶ

末尾再帰を使用して再帰関数を記述することができれば末尾再帰最適化の恩恵を受けることができるので、すべての関数をこの形で書こうとする誘惑にかられます。しかし、多くの関数は配列やそれに似たデータ構造に対する折り畳みとして直接書くことができることを忘れがちです。mapfoldのようなコンビネータを使って直接アルゴリズムを書くことには、コードの単純さという利点があります。これらのコンビネータはよく知られており、アルゴリズムの意図をはっきりとさせるのです。

例えば、 先ほどのreverseの例は、畳み込みとして少なくとも2つの方法で書くことができます。foldrを使用すると次のようになります。

> :i Data.Foldable
> let reverse :: forall a. [a] -> [a]
      reverse = foldr (\x xs -> xs ++ [x]) []
  
> reverse [1, 2, 3]
  
[3,2,1]

foldl を使って reverseを書くことは、読者への課題として残しておきます。

演習

  1. (簡単) foldlを使って、真偽値の配列の要素すべてが真かどうか調べてみてください。

  2. (やや難しい) 関数 foldl (==) false xs が真を返すような配列xsとはどのようなものか説明してください。

  3. (やや難しい) 累積器引数を使用して、次の関数を末尾再帰形に書きなおしてください。

    count :: forall a. (a -> Boolean) -> [a] -> Number
    count _ [] = 0
    count p (x : xs) = if p x then 1 + count p xs else count p xs
  4. (やや難しい) foldlを使ってreverseを書いてみましょう。

4.16 仮想ファイルシステム

この節では、これまで学んだことを応用して、模擬的なファイルシステムで動作する関数を書いていきます。事前に定義されたAPIで動作するように、マップ、畳み込み、およびフィルタを使用します。

Data.Pathモジュールでは、次のように仮想ファイルシステムのAPIが定義されています。

型については、型定義は次のようになっています。

root :: Path

ls :: Path -> [Path]

filename :: Path -> String

size :: Path -> Maybe Number

isDirectory :: Path -> Boolean

psci でこのAPIを試してみましょう。

> :i Data.Path

> root
/

> isDirectory root
true

> ls root
[/bin/,/etc/,/home/]

FileOperationsモジュールでは、Data.Path APIを操作するための関数を定義されています。Data.Pathモジュールを変更したり実装を理解する必要はありません。すべてFileOperationsモジュールだけで作業を行います。

4.17 すべてのファイルの一覧

それでは、内側のディレクトリまで、すべてのファイルを列挙する関数を書いてみましょう。この関数は以下のような型を持つでしょう。

allFiles :: Path -> [Path]

再帰を使うとこの関数を定義することができます。まずはlsを使用してディレクトリの直接の子を列挙します。それぞれの子について再帰的にallFilesを適用すると、それぞれパスの配列が返ってくるでしょう。concatMapを適用すると、この結果を同時に平坦化することができます。

最後に、: 演算子を使って現在のファイルも含めます。

allFiles file = file : concatMap allFiles (ls file)

それではpsci でこの関数を試してみましょう。

> :i FileOperations
> :i Data.Path

> allFiles root
  
[/,/bin/,/bin/cp,/bin/ls,/bin/mv,/etc/,/etc/hosts, ...]

すばらしい!do記法で配列内包表記を使ってもこの関数を書くことができるので見ていきましょう。

逆向きの矢印は配列から要素を選択するのに相当することを思い出してください。最初の手順は、引数の直接の子から要素を選択することです。それから、単にそのファイルに対してこの再帰関数を呼びします。do記法を使用しているので、再帰的な結果をすべて連結するconcatMapが暗黙に呼び出されています。

新しいコードは次のようになります。

allFiles' :: Path -> [Path]
allFiles' file = file : do
  child <- ls file
  allFiles' child

psci で新しいコードを試してみてください。同じ結果が返ってくるはずです。どちらのほうがわかりやすいかの選択はお任せします。

演習

  1. (簡単) ディレクトリのすべてのサブディレクトリの中まで、ディレクトリを除くすべてのファイルを返すような関数onlyFilesを書いてみてください。

  2. (やや難しい) このファイルシステムで最大と最小のファイルを決定するような畳込みを書いてください。

  3. (難しい) ファイルを名前で検索する関数whereIsを書いてください。この関数は型Maybe Pathの値を返すものとします。この値が存在するなら、そのファイルがそのディレクトリに含まれているということを表します。この関数は次のように振る舞う必要があります。

    > whereIs "/bin/ls"
    Just (/bin/)
    
    > whereIs "/bin/cat"
    Nothing

    ヒント:do記法で配列内包表記を使用して、この関数を記述してみてください。

4.18 まとめ

この章では、アルゴリズムを簡潔に表現する手段として、PureScriptでの再帰の基本を説明しました。また、独自の中置演算子や、マップ、フィルタリングや畳み込みなどの配列に対する標準関数、およびこれらの概念を組み合わせた配列内包表記を導入しました。最後に、スタックオーバーフローエラーを回避するために末尾再帰を使用することの重要性、累積器引数を使用して末尾再帰形に関数を変換する方法を示しました。