配列操作

説明

基本的なリスト操作を実装しましょう。

関数型言語では、lengthやmap、reduceのようなリスト操作がよく使われます。既存の関数を使わずに、一連の基本的なリスト操作を実装してみましょう。

実装する操作の正確な数や名前は、既存の名前との衝突を避けるため、トラックによって異なります。ただし、一般的には次のような操作を実装します。

• append（2つのリストが与えられたとき、2つ目のリストのすべての要素を1つ目のリストの末尾に追加します）。
• concatenate（一連のリストが与えられたとき、すべてのリストの要素を1つの平坦なリストにまとめます）。
• filter（述語とリストが与えられたとき、predicate(item)がTrueになるすべての要素のリストを返します）。
• length（リストが与えられたとき、その中にある要素の総数を返します）。
• map（関数とリストが与えられたとき、すべての要素にfunction(item)を適用した結果のリストを返します）。
• foldl（関数・リスト・初期アキュムレーターが与えられたとき、各要素を左からアキュムレーターに畳み込みます（reduce））。
• foldr（関数・リスト・初期アキュムレーターが与えられたとき、各要素を右からアキュムレーターに畳み込みます（reduce））。
• reverse（リストが与えられたとき、元の要素をすべて逆順に並べたリストを返します）。

なお、畳み込み関数（foldl、foldr）に引数を渡す順序は重要です。

待って、そんなの無理です！

Rocで、これらの配列の操作を組み込み関数を_一切_使わずに実装するのは、ほぼ不可能です。配列に要素を追加したり、先頭に要素を差し込んだりする方法が必要になるからです。 Haskellの:やPythonの+=のような演算子を使える言語もありますが、RocではListの関数を使う必要があります。

ですから、この演習ではList.appendを使ってもかまいません（ただし、それ以外の組み込み関数は使わないようにしましょう）。

多くの関数型プログラミング言語では、連結リストが主要なコレクション型として使われています。 連結リストでは、要素を先頭に追加したり、先頭の要素を取り出したりするのが効率的なので、そうした言語では配列の操作をList.prependで実装することになります。 一方Rocでは、Listは配列（連続したバイトのまとまり）です。 配列は、インデックスで要素に効率よくアクセスできる、新しい要素を効率よく追加できるなど、連結リストとは異なる性質を持っています。 そのため、RocではList.appendをよく使い、List.prependはほとんど使いません。

名前について

Rocでは、一般的な指示に挙げられているものとは少し違う名前を使います。

• appendの代わりにconcat
• concatenateの代わりにjoin
• lengthの代わりにlen
• foldlの代わりにfold
• foldrの代わりにfold_rev

ただし、次の関数名はRocでも標準的です。

• filter
• map
• reverse

ヒント

次のように書いてみましょう。

match list {
    [] => ...
    [first, .. as rest] => ...
}

または

match list {
    [] => ...
    [.. as rest, last] => ...
}