【ドワンゴのScala研修資料】mapメソッドをfoldLeftとreverseを使って実装する練習問題の解答が分かりません。

背景

Scala初心者です。
ドワンゴのScala研修資料で、1個ずつ練習問題を解きながらScalaを勉強しています。

分からなかった練習問題

次の練習問題の解答が分かりませんでした。

練習問題

次のシグニチャを持つmapメソッドをfoldLeftとreverseを使って実装してみましょう：

scala
1def map[T, U](list: List[T])(f: T => U): List[U] = ???

解答

scala
1def map[T, U](list: List[T])(f: T => U): List[U] = {
2  list.foldLeft(Nil:List[U]){(x, y) => f(y) :: x}.reverse
3}

質問

解答の以下の項目について、教えていただきたいです。

{(x, y) => f(y) :: x}のx,yの型は？たとえばmap(List(1,2,3))(x=>x*x)を実行したときの場合など。
f(y) :: xと、Listの連結を行っている理由は？
{(x, y) => f(y) :: x}で、波括弧を使っている理由は？foldLeftの使用箇所では、丸括弧を使っている。

また、mapメソッドをfoldLeftとreverseで実現するイメージが想像できません。
以下のツリー構造のような、分かりやすい表現がありましたら、そちらも教えていただきたいです。

txt
1       +
2      / ＼
3     +   3
4    / ＼
5   +   2
6  / ＼
7 0   1

※ドワンゴ研修資料から引用

補足

「変数xとyの型は？」の質問内容が不十分だったため、補足いたします。

ドワンゴ研修資料には、foldLeftのサンプルとして、以下のコードが載っていました。

scala
1List(1, 2, 3).foldLeft(0)((x, y) => x + y)
2//⇒ 6

上記のサンプルプログムから、私は以下のように判断しました。

上記のプログラムの、初期値、変数x, yの型はInt
したがって、foldLeftで使う初期値、変数x, yの型は、Listの型パラメータ

このような理解で、「mapメソッドをfoldLeftとreverseで実装する問題」の解答を見たとき、
以下の項目が疑問に思いました。

初期値の型はList？
変数yの型はIntだけど、xの型はList？
変数xと変数yの型は同じでなくてよい？

以上が、「変数xとyの型は何？」と質問した経緯です。

Scala APIドキュメント
では、foldLeftの宣言は、

scala
1def foldLeft[B](z: B)(op: (B, A) ⇒ B): B

となっており、

初期値、変数xに対応する型パラメータはB
変数yに対応する型パラメータはA

でした。

変数xとyの型は異なっていて、いいんですね。

以上、foldLeftの理解不足による質問でした。

参考にしたサイト

行動規範の内容に同意します

回答1件

ベストアンサー

x,yの型

式の左から順番に定義された型引数と実引数の照合により型が推論されるという点がポイントだと思います。

mapの第一引数はlist: List[T]で、そこにList(1,2,3)を渡すと1,2,3を表す最も特化された型としてIntと推論され、

List(1,2,3)の型 => List[Int]
T => Int

と推論され、次に・・・といった具合に決まっていきます。

f(y) :: xと、Listの連結を行っている理由は？

連結しないと結果が残らないから・・・という答えしか思いつけませんでした。質問意図が自分にはよくわかりませんでした。

波括弧を使っている理由は？

このあたりは自分もあまり自信ないですが・・・
愚直に書くと次のようにかけますよね？

list.foldLeft {Nil:List[U]} ({(x, y) => f(y) :: x}).reverse

()と{}ですが、()の中に単一のブロック（この場合はラムダ式の範囲を明示するためのブロック・・・でいいのかな）しかない場合は()を省略できるようになっていると思います。逆に{}を省略して

list.foldLeft {Nil:List[U]} ((x, y) => f(y) :: x).reverse

とも書けます。ちゃんとした理由を知らないのですが、自分の印象では、高階関数に対し、関数を引数に渡す場合、{}を用いる習慣があるような気がします。foldLeftには第一引数に初期値、第二引数に簡約用の関数を渡しますが、第一引数は関数ではないので()を用い、第二引数は関数なので{}を使う習慣があるのかなぁと思っています（曖昧なコメントでスミマセン）。

foldLeftとreverseのイメージ

mapは列の先頭から関数を適用した結果を要素に持つ新たな列を返すわけですが、Listはimmutableな構造(linked listのイメージ)なので、末尾に追加するとしたら新たな要素がくっついたような新たなList構造を元のリストをそっくりコピーして生成しなければならないため遅くなるのだろうと思います。このためListを用いて値を蓄積する際には先頭にくっつけるのが常とう手段ではないかと思います。

そうすると処理の順番とは逆の順番のリストができあがるので、最後にreverseして元の順番に戻すわけです。reverseもオリジナルのリストをコピーしますが計算量は要素数Nのオーダーなので、毎回末尾に追加してNの二乗のオーダーの計算量になるよりかはましということだと思います。JavaなどだとこういうことをせずにArrayListなどのmutableなコレクションを用いて末尾にくっつけてしまいますが、Scalaとか関数型言語のプログラミングではmutableなものはその副作用のために嫌われる傾向があるようで、こういう定型パターンになっているのではないでしょうか。

投稿2018/01/04 12:10

KSwordOfHaste

総合スコア18394

yuji38kwmt

2018/01/13 07:22

詳しい解答ありがとうございます！「なんでreverseするんだろう。javaのArrayListみたいにaddすればいいのに」と思っていましたが、疑問解決です。 immutableや計算量が関係してくるんですね。

KSwordOfHaste

2018/01/13 07:34

そうですね。ただ、自分の場合なんでもかんでもimmutableがよいとは考えない方でしてあらかじめ要素数が予想できて他の箇所からそのリストが参照されないようなケースではmutable.Bufferを使ってお尻に要素をくっつけるといった方法を採ることもあります。ただ、出題者は「mapが先頭から末尾へ順番に処理するようなイメージ」であっても実装面から考えると「先頭にくっつけて反転させる手法もある」という点を気付いてほしいといった意図があったのではないでしょうか。

行動規範の内容に同意します