ようこそ! Function Questへ! このゲームはプレイヤーをコマンドで動かしてゴールまで導くのが目的です。画面右側のエディタにコマンドを返す関数を書いてください。 ```scala [Command] getCommands((Int, Int) player, (Int, Int) goal) { [Go(Up())] } ``` 上のコードをエディタに貼り付けてRun!を押してみてください。プレイヤーが1マス上に動くはずです。 この`getCommands`関数はコマンド列を返す関数で、上のコードは`Go(Up())`という上に動くというコマンドを1回実行しなさいという意味です。 コマンド列とはコマンドのリストのことです。リストは配列みたいなもの、と覚えておけばいいでしょう。 ```scala [1, 2, 3] ``` という感じでかけます。あとは足りないコマンドを追加してプレイヤーをゴールに導きましょう!

`getCommands`内の配列の要素である、`Go(Up())`の数を増やしてみましょう。プレイヤーはその数だけ上に動きます。また、多すぎてもクリアにならないので注意してください。

階乗(fact)関数を作ってみましょう。関数を定義するには以下のように書きます。 ```scala Int fact(Int n) { // 関数の中身 } ``` ここで`fun`の前の`Int`は返り値の型、`fun`の後ろの`Int n`は入力の型と名前です。この形はC言語と似ているので覚えやすいでしょう。 例えば引数`n`を2倍して出力する関数は以下のようにかけます ```scala Int double(Int n) { n * 2 } ``` C言語における`return`は書かないことに注意してください。 階乗関数は ``` n >= 0 fact(n) = n * (n - 1) * (n - 2) * ... * 1 fact(0) = 1 example: fact(5) = 5 * 4 * 3 * 2 * 1 = 120 ``` と定義される関数です。この関数を作成したらロックされた壁を解除するために関数を`AddItem`コマンドに渡しましょう。このコマンドは引数をプレイヤーのアイテム(エディタの下にリストがあります)に追加します。この後に`Unlock`コマンドでロックを解除します。ロックがかかっている壁には条件が書いてあって(マウスポインタを重ねると表示されます)、ランダムな自然数nに対してnの階乗を返す関数を渡せというものです。 ```scala Int fact(Int n) { ... } [Command] getCommands((Int, Int) player, (Int, Int) goal) { [AddItem(fact), Unlock(Up()), Go(Up()), Go(Up())] } ``` ここでデバッグのコツを説明します。 * `print!`で値を出力できるので、デバッグに役立ててください。 * エディタの上にある「REPL」に切り替えて、ソースコード(例えば`fact`関数)をコピーして貼り付け、好きな数値を渡してデバッグすることもできます(詳しくは上のバーの「説明」を見てください)

まず、`n = 0`のときは`fact(0)`は`1`となります。これはif文で判定できます。 それ以外の時は再帰をつかいます。なぜループではなくて再帰を用いる必要があるかというと、aoscriptでは値の上書きやジャンプができないからです。再帰では`fact(n - 1)`の結果を用いて`fact(n)`の結果を導きます。

次はパターンマッチを使ってみましょう。パターンマッチはaoscriptで構造の内部の値をとる唯一の方法です。構造とは例えばListやTupleのことです。ここではTupleの内容をとってみましょう。パターンマッチは以下のように使えます。 ```scala (Int, Int) pair = (0, 1) match(pair) { (a, b) -> a + b } ``` matchの後にマッチ(match)の対象となる値を書いて、そのあとにパターンとそれとマッチした時の値を書いていきます。たとえばこの例では2つ組のTupleである`pair`を`(a, b)`とマッチさせて`->`以降でpairの中身である`a`と`b`を使えるようにしています。この処理は`pair`の中身を加算して返しているということです。 また、`match`は式なので全体で値となります。つまり以下のように使うこともできます。 ```scala val x = match(pair) { (a, b) -> a } ``` この例を踏まえて3つ組のTuple(型は`(Int, Int, Int)`)を加算して返す関数を作ってみましょう。作った関数は先ほどと同じように`AddItem`して`Unlock`すれば壁が消えるはずです! 関数の定義は例えば以下のようになります ```scala Int sum((Int, Int, Int) tri) { // 中身... } ```

```scala match(tri) { (a, b, c) -> ... } ``` あとは...

このステージではゴールのy座標の位置がランダムなので少し工夫をする必要があります。 まず、プレイヤーとゴールの距離を求めるためにそれぞれのy座標を取得しましょう。与えられている座標は2つ組のTupleなので先ほどの方法でy座標が取れるはずです。このための関数を定義してもいいですね。 ここでこのゲームの座標系について説明すると、左上が(0, 0)で右方向にxの正の方向、下方向にyの正の方向となっています。`getCommands`の引数`player`と`goal`は2つ組のTupleになっていますが1つ目がx,2つ目がy座標を表しています。 距離が取れたら例えば、指定の`n`(`Int`型)だけ`value`(`Command`型)を繰り返したリスト(`[Command]`型)を返す関数`repeat`を定義してそれを用いてコマンドを生成するといいでしょう。`repeat`の定義は例えば以下のようになります。 ```scala [Command] repeat(Int n, Command value){ // 中身... } ``` aoscriptにはfor文に相当するものがないので先ほどの階乗関数と同様に再帰を使って実装することになります。 Listについて1つ付け加えると、`list`の先頭に要素`v`を追加するには ``` Cons(v, list) ``` とすればできます。`list`の中身の型と`v`の型が一致していないとエラーになるので注意してください。 このステージでは2回連続で命令が実行されるので単に`Go(Up())`するだけではクリアできないので注意してください。

`repeat`関数について、これはStage2の階乗関数と同じようにまず`n = 0`の時の出力を考えます。`repeat(0, Go(Up()))`の時出力は何であって欲しいですか? それ以外の時、例えば`repeat(n, Go(Up())`の時は`repeat(n - 1, Go(Up()))`の結果を使います。具体的には`n - 1`の時の結果に`Cons`を用いて`value`をつなげます。 ``` repeat(2, Go(Up()) = Cons(Go(Up()), repeat(1, Go(Up()))) = Cons(Go(Up()), Cons(Go(Up(), repeat(0, Go(Up()))))) = Cons(Go(Up()), Cons(Go(Up(), []))) # 空のリストにGo(Up())を2つつなげる = [Go(Up()), Go(Up())] ```

次はListのパターンマッチを扱ってみましょう。これができるとできることの幅が広がります。 Listは配列のようなものだと説明しましたが、実際は下図のように(限定された)2分木となっています。`Cons`の左側(car)が値、右側(cdr)が次の要素の`Cons`となっています。終端は`Cons`ではなく`Null`となっています。空のListはNullです。 `[1, 2, ... 3]`  Listのパターンマッチは先ほどと同じように書けますが、パターンが複数になるということに注意してください。なぜそうなるかというとConsとNullのパターンを用意しないと、どのパターンもマッチしないときにエラーになるからです。 パターンが複数の時は上からチェックされます。 例えばリストの先頭要素を返す(空のリストだったら0)処理は ```scala match(list) { [] -> 0 Cons(x, xs) -> x } ``` と書けます。このパターンマッチを使って壁のロックを解除してみましょう。 実装すべき関数の定義は例えば以下のようになります。`Int`を`[]`で囲むことで`Int`のリストという意味になります。 ```scala [Int] doubleList([Int] list) { // 中身... } ```

まず、Null(空のリスト)の場合を考えてみます。空のリストの要素はないわけですから結果も空のリストになります。 それ以外の時は、`match`によって分解した`x`(先頭の要素)と`xs`(先頭以外の要素が入ったリスト)を用います。具体的には`x`, `xs`にある処理をして再び`Cons`でくっつけます。 ```scala match(list) { [] -> [] Cons(x, xs) -> Cons(xにとある処理, xsに対して今いる関数と同じ処理) } ```

Stage4の地形に似ていますが、右に2つ移動しなければいけない点が少し異なります。 これは例えば、Stage4のソース(`stage4`でソースが保存されているはずなのでそれでロードできます)に以下に示すような`append`関数を実装して先ほどの`repeat`の結果に`Go(Right())`を2つ追加すればできそうです。 ```scala // listの末尾にvalueを追加したものを出力する関数 [Command] append([Command] list, Command value) { // 中身... } [Command] getCommands((Int, Int) player, (Int, Int) goal) { repeat(...).append(Go(Right())).append(Go(Right())) } ```

`append`関数についてまず、Null(空のリスト)の場合を考えてみます。空のリストに`value`を追加した時の結果は何になりますか? それ以外の時は、`match`によって分解した`x`(先頭の要素)と`xs`(先頭以外の要素が入ったリスト)を用います。具体的には`xs`にある処理をして再び`Cons`でくっつけます。 ```scala match(list) { [] -> ... Cons(x, xs) -> Cons(x, xsに対して今いる関数と同じ処理) } ```

このステージではゴールのy座標がランダムだけではなくx座標もランダムとなっています。 y座標に関する移動コマンドのリストとx座標に関する移動コマンドのリストをつなげる関数が必要になってきます。例えばリスト`a`と`b`をつなげたリストを返す関数`concat`を実装してx, y座標両方の移動をつなげればできそうです。 ```scala [Command] concat([Command] a, [Command] b) { // 中身... } ``` 実装上のヒントを書くと`b`をmatchにより分解してから(`b`が空のリストの時も考える)、その先頭要素と`a`とを先ほど実装した`append`を用いてつなげたものと`b`の先頭要素以外をまた`concat`でつなぎます。 模式図(ソースコードではありません) ``` a = [1, 2, 3] b = [4, 5, 6] concat(a, b) = concat([1, 2, 3, 4], [5, 6]) = concat([1, 2, 3, 4, 5], [6]) = concat([1, 2, 3, 4, 5, 6], []) = [1, 2, 3, 4, 5, 6] ```

最後のステージなのでヒント無しで頑張ってください!