再帰、マップ、畳み込み

一時的な注意事項：本章に取り組まれているようでしたら、2023年11月に第4章と第5章とが入れ替わっていることにお気を付けください。

この章の目標

この章では、アルゴリズムを構造化するときに再帰関数をどのように使うかについて見ていきましょう。再帰は関数型プログラミングの基本的な手法であり、本書全体に亙って使われます。

また、PureScriptの標準ライブラリから標準的な関数を幾つか取り扱います。 mapやfoldといった関数だけでなく、filterやconcatMapといった特別な場合において便利なものについても見ていきます。

この章では、仮想的なファイルシステムを操作する関数のライブラリを動機付けに用います。この章で学ぶ技術を応用し、ファイルシステムのモデルにより表現されるファイルのプロパティを計算する関数を書きます。

この章のソースコードはsrc/Data/Path.pursとtest/Examples.pursに含まれています。 Data.Pathモジュールは仮想ファイルシステムのモデルを含みます。このモジュールの内容を変更する必要はありません。演習への解答はTest.MySolutionsモジュールに実装してください。それぞれの演習を完了させつつ都度Test.Mainモジュールにある対応するテストを有効にし、spago testを走らせることで解答を確認してください。

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

maybe: Maybe型構築子が定義されています。
arrays: 配列を扱うための関数が定義されています。
strings: JavaScriptの文字列を扱うための関数が定義されています。
foldable-traversable: 配列やその他のデータ構造を畳み込む関数が定義されています。
console: コンソールへの出力を扱うための関数が定義されています。

導入

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

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

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

次に示すのは階乗関数のありふれた例です。

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

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

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

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

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

配列上での再帰

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

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

import Prelude

import Data.Array (null, tail)
import Data.Maybe (fromMaybe)

length :: forall a. Array a -> Int
length [] = 0
length arr = 1 + (length $ fromMaybe [] $ tail arr)

この関数では、配列が空かどうかに基づいて分岐しています。 null関数は、空配列についてはtrueを返します。空配列は長さ0を、非空配列は尾鰭の長さより1大きい長さを持ちます。

tail関数は与えられた配列から最初の要素を除いたものをMaybeに包んで返します。配列が空であれば（つまり尾鰭がなければ）Nothingが返ります。 fromMaybe関数は既定値とMaybe値を取ります。後者がNothingであれば既定値を返し、そうでなければJustに包まれた値を返します。

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

演習

（簡単）入力が偶数であるとき、かつそのときに限りtrueに返す再帰関数isEvenを書いてみましょう。
（普通）配列内の偶数の整数を数える再帰関数countEvenを書いてみましょう。 手掛かり：head関数（これもData.Arrayモジュールから手に入ります）を使うと、空でない配列の最初の要素を見つけられます。

マップ

map関数は配列に対する再帰関数の一例です。配列の各要素に順番に関数を適用し、配列の要素を変換するのに使われます。そのため、配列の内容は変更されますが、その形状（ここでは「長さ」）は保存されます。

本書の後半で型クラスの内容を押さえるとき、map関数が形状を保存する関数のより一般的な様式の一例であることを見ていきます。この関数は関手と呼ばれる型構築子のクラスを変換するものです。

それでは、PSCiでmap関数を試してみましょう。

$ spago repl

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

mapがどのように使われているかに注目してください。最初の引数には配列上で「写す」関数、第2引数には配列そのものを渡します。

中置演算子

バッククォートで関数名を囲むと、写す関数と配列の間に、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の型を見てみましょう。

> :type map
forall (f :: Type -> Type) (a :: Type) (b :: Type). Functor f => (a -> b) -> f a -> f b

実はmapの型は、この章で必要とされているものよりも一般的な型になっています。今回の目的では、mapは次のようなもっと具体的な型であるかのように考えるとよいでしょう。

forall (a :: Type) (b :: Type). (a -> b) -> Array a -> Array b

この型では、map関数に適用するときにはaとbという2つの型を自由に選ぶことができる、ということも示されています。 aは元の配列の要素の型で、bは目的の配列の要素の型です。もっと言えば、mapが配列の要素の型を保存する必要があるわけではありません。例えば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関数の同義語として中置演算子(..)を定義しています。

infix 8 range as ..

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

> import Data.Array

> 1 .. 5
[1, 2, 3, 4, 5]

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

補足：独自の中置演算子は、自然な構文を備える領域特化言語を定義する上で優れた手段になりえます。ただし、乱用すると初心者が読めないコードになることがありますから、新たな演算子の定義には慎重になるのが賢明です。

上記の例では、1 .. 5という式は括弧で囲まれていましたが、実際にはこれは必要ありません。なぜなら、Data.Arrayモジュールは、<$>に割り当てられた優先順位より高い優先順位を..演算子に割り当てているからです。上の例では、..の優先順位は、キーワードinfixのあとに書かれた数の8 と定義されていました。ここでは<$>の優先順位よりも高い優先順位を..に割り当てており、このため括弧を付け加える必要がないということです。

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

中置演算子に（左または右の）結合性を与えたい場合は、代わりにキーワードinfixlとinfixrを使います。 infixを使うと何ら結合性は割り当てられず、同じ演算子を複数回使ったり複数の同じ優先度の演算子を使ったりするときに、式を括弧で囲まなければいけなくなります。

配列の絞り込み

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

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

> import Data.Array

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

演習

（簡単）map関数や<$>関数を使用して、配列に格納された数のそれぞれの平方を計算する関数squaredを書いてみましょう。 手掛かり：mapや<$>といった関数を使ってください。
（簡単）filter関数を使用して、数の配列から負の数を取り除く関数keepNonNegativeを書いてみましょう。 手掛かり：filter関数を使ってください。
（普通）
- filterの中置同義語<$?>を定義してください。補足：中置同義語はREPLでは定義できないかもしれませんが、ファイルでは定義できます。
- 関数keepNonNegativeRewriteを書いてください。この関数はfilterを独自の新しい中置演算子<$?>で置き換えたところ以外、keepNonNegativeと同じです。
- PSCiで独自の演算子の優先度合いと結合性を試してください。補足：この問題のための単体試験はありません。

配列の平坦化

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

> import Data.Array

> :type concat
forall (a :: Type). Array (Array a) -> Array a

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

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

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

> import Data.Array

> :type concatMap
forall (a :: Type) (b :: Type). (a -> Array b) -> Array a -> Array b

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

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

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

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

配列内包表記

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

配列内包表記を使用するとこれを計算できます。 PSCiを対話式の開発環境として使用し、1つずつこの手順を進めていきましょう。

最初の工程ではn以下の数の組み合わせの配列を生成しますが、これにはconcatMapを使えばよいです。

1 .. nのそれぞれの数を配列1 .. nへと対応付けるところから始めましょう。

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

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

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

これは求めているものとは全然違います。単にそれぞれの組み合わせの2つ目の要素を返すのではなく、対全体を保持できるように、内側の1 .. nの複製について関数を対応付ける必要があります。

> :paste
… pairs' n =
…   concatMap (\i ->
…     map (\j -> [i, j]) (1 .. n)
…   ) (1 .. n)
… ^D

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

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

> :paste
… pairs'' n =
…   concatMap (\i ->
…     map (\j -> [i, j]) (i .. n)
…   ) (1 .. n)
… ^D
> pairs'' 3
[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]

すばらしいです。因数の候補の全ての組み合わせを手に入れたので、filterを使えば、その積がnであるような組み合わせを選び出すことができます。

> import Data.Foldable

> factors n = filter (\pair -> product pair == n) (pairs'' n)

> factors 10
[[1,10],[2,5]]

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

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

do記法

しかし、このコードの可読性は大幅に向上できます。mapやconcatMapは基本的な関数であり、 do記法 (do notation) と呼ばれる特別な構文の基礎になっています（もっと厳密にいえば、それらの一般化であるmapとbindが基礎をなしています）。

補足：mapとconcatMapがあることで配列内包表記を書けるように、もっと一般的な演算子であるmapとbindがあることでモナド内包表記と呼ばれているものが書けます。本書の後半ではモナドの例をたっぷり見ていくことになりますが、この章では配列のみを考えます。

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

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

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

配列の要素を名前に束縛する式。これは後ろ向きの矢印<-で示されており、左側には名前が、右側には配列の型を持つ式があります。
名前に配列の要素を束縛しない式。 doの結果はこの種類の式の一例であり、最後の行のpure [i, j]に示されています。
letキーワードを使用し、式に名前を与える式。

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

最後の行では、pure関数を使っています。この関数はPSCiで評価できますが、型を明示する必要があります。

> pure [1, 2] :: Array (Array Int)
[[1, 2]]

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

factorsV2 :: Int -> Array (Array Int)
factorsV2 n = filter (\xs -> product xs == n) do
  i <- 1 .. n
  j <- i .. n
  [ [ i, j ] ]

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

ガード

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

import Control.Alternative (guard)

factorsV3 :: Int -> Array (Array Int)
factorsV3 n = do
  i <- 1 .. n
  j <- i .. n
  guard $ i * j == n
  pure [ i, j ]

pureと同じように、どのように動作するかを理解するために、PSCiでguard関数を適用して調べてみましょう。 guard関数の型は、ここで必要とされるものよりもっと一般的な型になっています。

> import Control.Alternative

> :type guard
forall (m :: Type -> Type). Alternative m => Boolean -> m Unit

Unit型は何ら計算する内容の無い値を表現します。すなわち具体的で意味のある値が存在しないということです。

Unitはよく型構築子に「包んで」計算の返却型として使います。その計算は具体的な値のためではなく、計算の作用（ないし結果の「形状」）のみに関心があるのです。

例えば、main関数は型Effect Unitを持ちます。この関数はプロジェクトへの入口であり、直接呼ぶものではありません。

型シグネチャ中のmの意味については第6章で説明します。

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

Boolean -> Array Unit

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

> import Data.Array

> length $ guard true
1

> length $ guard false
0

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

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

演習

（簡単）関数isPrimeを書いてください。この関数は整数の引数が素数であるかを調べます。 手掛かり：factors関数を使ってください。
（普通）do記法を使い、2つの配列の直積集合を見つけるための関数cartesianProductを書いてみましょう。直積集合とは、要素a、bの全ての組み合わせの集合のことです。ここでaは最初の配列の要素、bは2つ目の配列の要素です。
（普通）関数triples :: Int -> Array (Array Int)を書いてください。この関数は数値 $ n $ を取り、構成要素（値 $ a $、 $ b $、 $ c $）がそれぞれ $ n $ 以下であるような全てのピタゴラスの3つ組 (pythagorean triples) を返します。 ピタゴラスの3つ組は $ a ^ 2 + b ^ 2 = c ^ 2 $ であるような数値の配列 $ [ a, b, c ] $ です。 手掛かり：配列内包表記でguard関数を使ってください。
（難しい）factors関数を使用して、nの素因数分解を求める関数primeFactorsを定義してみましょう。 nの素因数分解とは、積がnであるような素数の配列のことです。 手掛かり：1より大きい整数について、問題を2つの部分問題に分解してください。最初の因数を探し、それから残りの因数を探すのです。

畳み込み

配列における左右の畳み込みは、再帰を用いて実装できる別の興味深い一揃いの関数を提供します。

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

> import Data.Foldable

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

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

これらの型は、現在興味があるものよりも一般化されています。この章では単純化して以下の（より具体的な）型シグネチャと見て構いません。

-- foldl
forall a b. (b -> a -> b) -> b -> Array a -> b

-- foldr
forall a b. (a -> b -> b) -> b -> Array a -> b

どちらの場合でも、型aは配列の要素の型に対応しています。型bは「累算器」の型として考えることができます。累算器とは配列を走査しつつ結果を累算するものです。

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

実際にこれらの関数の動きを見てみましょう。 foldlを使用して数の配列の和を求めてみます。型aはIntになり、結果の型bもIntとして選択できます。ここでは3つの引数を与える必要があります。 1つ目は次の要素を累算器に加算するInt -> Int -> Intという型の関数です。 2つ目は累算器のInt型の初期値です。 3つ目は和を求めたいIntの配列です。最初の引数としては、加算演算子を使用できますし、累算器の初期値はゼロになります。

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

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

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

違いを説明するために、畳み込み関数の選択が大事になってくる例も書きましょう。加算関数の代わりに、文字列連結を使用して文字列を構築しましょう。

> 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)

末尾再帰

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

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

> :paste
… f n =
…   if n == 0
…     then 0
…     else 1 + f (n - 1)
… ^D

> f 10
10

> f 100000
RangeError: Maximum call stack size exceeded

これは問題です。関数型プログラミングの標準的な手法として再帰を採用しようとするなら、境界がない再帰がありうるときでも扱える方法が必要です。

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

補足：この問題へのより完全な解決策としては、いわゆるトランポリンを使用するライブラリで実装できますが、それはこの章で扱う範囲を超えています。興味のある読者はfreeやtailrecパッケージのドキュメントをあたると良いでしょう。

末尾再帰最適化を可能にする上で鍵となる観点は以下となります。 末尾位置にある関数の再帰的な呼び出しはジャンプに置き換えられます。このジャンプではスタックフレームが確保されません。関数が戻るより前の最後の呼び出しであるとき、呼び出しが末尾位置にあるといいます。先の例でスタックオーバーフローが見られたのはこれが理由です。 fの再帰呼び出しが末尾位置でなかったからです。

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

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

factorialTailRec :: Int -> Int -> Int
factorialTailRec 0 acc = acc
factorialTailRec n acc = factorialTailRec (n - 1) (acc * n)

factorialTailRecへの再帰呼び出しがこの関数の最後にある点に注目してください。つまり末尾位置にあるのです。

累算器

末尾再帰ではない関数を末尾再帰関数に変える一般的な方法は、累算器引数を使用することです。累算器引数は関数に追加される余剰の引数で、返り値を累算するものです。これは結果を累算するために返り値を使うのとは対照的です。

例えば章の初めに示したlength関数を再考しましょう。

length :: forall a. Array a -> Int
length [] = 0
length arr = 1 + (length $ fromMaybe [] $ tail arr)

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

lengthTailRec :: forall a. Array a -> Int
lengthTailRec arr = length' arr 0
  where
  length' :: Array a -> Int -> Int
  length' [] acc = acc
  length' arr' acc = length' (fromMaybe [] $ tail arr') (acc + 1)

ここでは補助関数length'に委譲しています。この関数は末尾再帰です。その唯一の再帰呼び出しは、最後の場合の末尾位置にあります。つまり、生成されるコードはwhileループとなり、大きな入力でもスタックが溢れません。

lengthTailRecの実装を理解する上では、補助関数length'が基本的に累算器引数を使って追加の状態を保持していることに注目してください。追加の状態とは、部分的な結果です。 0から始まり、入力の配列中の全ての各要素について1ずつ足されて大きくなっていきます。

なお、累算器を「状態」と考えることもできますが、直接には変更されていません。

明示的な再帰より畳み込みを選ぼう

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

例えばfoldrを使って配列を反転できます。

> import Data.Foldable

> :paste
… reverse :: forall a. Array a -> Array a
… reverse = foldr (\x xs -> xs <> [x]) []
… ^D

> reverse [1, 2, 3]
[3,2,1]

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

演習

（簡単）foldlを使って真偽値配列の値が全て真か検査する関数allTrueを書いてください。
（普通。テストなし）関数foldl (==) false xsが真を返すような配列xsとはどのようなものか説明してください。言い換えると、「関数はxsが……を含むときにtrueを返す」という文を完成させることになります。
（普通）末尾再帰の形式を取っていること以外はfibと同じような関数fibTailRecを書いてください。 手掛かり：累算器引数を使ってください。
（普通）foldlを使ってreverseを書いてみましょう。

仮想ファイルシステム

この節ではこれまで学んだことを応用してファイルシステムのモデルを扱う関数を書きます。事前に定義されたAPIを扱う上でマップ、畳み込み、及びフィルタを使用します。

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

ファイルシステム内のパスを表す型Pathがあります。
ルートディレクトリを表すパスrootがあります。
ls関数はディレクトリ内のファイルを列挙します。
filename関数はPathのファイル名を返します。
size関数はファイルを表すPathのファイルの大きさを返します。
isDirectory関数はファイルかディレクトリかを調べます。

型について言うと、次のような型定義があります。

root :: Path

ls :: Path -> Array Path

filename :: Path -> String

size :: Path -> Maybe Int

isDirectory :: Path -> Boolean

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

$ spago repl

> import Data.Path

> root
/

> isDirectory root
true

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

Test.ExamplesモジュールではData.Path APIを使用する関数を定義しています。 Data.Pathモジュールを変更したり定義を理解したりする必要はありません。全てTest.Examplesモジュールだけで作業します。

全てのファイルの一覧

それでは、ディレクトリの中身を含めた全てのファイルを深く列挙する関数を書いてみましょう。この関数は以下のような型を持つでしょう。

allFiles :: Path -> Array Path

再帰を使ってこの関数を定義できます。 lsを使うとディレクトリ直下の子が列挙されます。それぞれの子について再帰的にallFilesを適用すると、それぞれパスの配列が返ります。 concatMapを使うと、allFilesを適用して平坦化するまでを一度にできます。

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

allFiles file = file : concatMap allFiles (ls file)

補足：実はcons演算子:は、不変な配列に対して効率性が悪いので、一般的には推奨されません。連結リストやシーケンスなどの他のデータ構造を使用すると、効率性を向上させられます。

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

> import Test.Examples
> import Data.Path

> allFiles root

[/,/bin/,/bin/cp,/bin/ls,/bin/mv,/etc/,/etc/hosts, ...]

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

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

新しいバージョンは次のようになります。

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

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

演習

（簡単）ディレクトリの全てのサブディレクトリの中にある（ディレクトリを除く）全てのファイルを返すような関数onlyFilesを書いてみてください。
（普通）ファイルを名前で検索する関数whereIsを書いてください。この関数は型Maybe Pathの値を返すものとします。この値が存在するなら、そのファイルがそのディレクトリに含まれているということを表します。この関数は次のように振る舞う必要があります。
```
> whereIs root "ls"
Just (/bin/)

> whereIs root "cat"
Nothing
```
手掛かり：この関数をdo記法を使った配列内包表記で書いてみましょう。
（難しい）Path中の最大のファイルと最小のファイルを1つずつ含む配列を返す関数largestSmallestを書いてください。補足：空配列や1要素の配列を返すことで、Pathにそれぞれゼロか1個のファイルがある場合についても考慮してください。

まとめ

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

実例によるPureScript