目次に戻る

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

4.1 この章の目標

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

また、PureScriptの標準ライブラリから標準的な関数をいくつか取り扱います。mapやfoldのようなよく知られた関数だけでなく、filterやconcatMapといった珍しいけれど便利なものについても見ていきます。

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

4.2 プロジェクトの準備

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

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

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

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

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

4.3 はじめに

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

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

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

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

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

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

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

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

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

4.4 配列上での再帰

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

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

import Prelude

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

length :: forall a. Array a -> Int
length arr =
  if null arr
    then 0
    else 1 + length (unsafePartial tail arr)

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

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

4.5 マップ

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

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

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

$ pulp repl

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

[2, 3, 4, 5, 6]

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

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の型を見てみましょう。

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

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

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

この型では、map関数に適用するときにはaとbという２つの型を自由に選ぶことができる、ということも示されています。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を使います。

4.7 配列のフィルタリング

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

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

import Data.Array

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

4.8 配列の平坦化

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

import Data.Array
:type concat 
forall a. 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 b. (a -> Array b) -> Array a -> Array b

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

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

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

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

4.9 配列内包表記

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

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

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]

これは求めているものとはぜんぜん違います。単にそれぞれの組み合わせの２つ目の要素を返すのではなく、ペア全体を保持することができるように、内側の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の範囲に限定することで、２つ目の場合を取り除くことができます。

: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]]

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

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

4.10 do記法

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

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

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記法を使うコードのブロックを導入します。このブロックは幾つかの型の式で構成されています。

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

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

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

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

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

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

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

4.11 ガード

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

import Control.MonadZero (guard)

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

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

import Control.MonadZero

:type guard
forall m. MonadZero m => Boolean -> m Unit

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

Boolean -> Array Unit

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

import Data.Array

length $ guard true
1

length $ guard false
0

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

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

4.12 畳み込み

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

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

import Data.Foldable

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

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

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

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

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

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

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

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

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

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

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

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

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で次のコードを入力すると、この問題を簡単に検証できます。

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)を使用したライブラリで実装する方法がありますが、それはこの章で扱う範囲を超えています。この内容に興味のある読者はpurescript-freeやpurescript-tailrecパッケージのドキュメントを参照してみてください。

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

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

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

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

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

4.14 累積器

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

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

reverse :: forall a. Array a -> Array a
reverse [] = []
reverse xs = snoc (reverse (unsafePartial tail xs))
                  (unsafePartial head xs)

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

reverse :: forall a. Array a -> Array a
reverse = reverse' []
  where
    reverse' acc [] = acc
    reverse' acc xs = reverse' (unsafePartial head xs : acc)
                               (unsafePartial tail xs)

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

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

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

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

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

例えば、 先ほどのreverseの例は、畳み込みとして少なくとも2つの方法で書くことができます。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を書くことは、読者への課題として残しておきます。

4.16 仮想ファイルシステム

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

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

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

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

root :: Path

ls :: Path -> Array Path

filename :: Path -> String

size :: Path -> Maybe Number

isDirectory :: Path -> Boolean

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

$ pulp repl
import Data.Path

root
/

isDirectory root
true

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

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

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

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

allFiles :: Path -> Array Path

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

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

allFiles file = file : concatMap allFiles (ls file)

注意：cons演算子：は、実際には不変な配列に対してパフォーマンスが悪いので、一般的には推奨されません。 リンクリストやシーケンスなどの他のデータ構造を使用すると、パフォーマンスを向上させることができます。

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

import FileOperations
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で新しいコードを試してみてください。同じ結果が返ってくるはずです。どちらのほうがわかりやすいかの選択はお任せします。

まとめ

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

目次に戻る