質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.83%

  • Scala

    170questions

    ScalaはJava仮想マシンで動作を行うオブジェクト指向型プログラミング言語の1つです。静的型付けの関数型言語で、コンパイルエラーの検出に強みがあります。

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 206

yuji38kwmt

score 416

 背景

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

 分からなかった練習問題

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

コレクションライブラリ

 練習問題

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

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

 解答

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

 質問

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

  • {(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メソッドをfoldLeftreverseで実現するイメージが想像できません。
以下のツリー構造のような、分かりやすい表現がありましたら、そちらも教えていただきたいです。

       +
      / \
     +   3
    / \
   +   2
  / \
 0   1

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

 補足

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

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

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

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

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

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

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

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

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

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


となっており、

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

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

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

 参考にしたサイト

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+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/13 16:22

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

    キャンセル

  • 2018/01/13 16:34

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.83%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Scala

    170questions

    ScalaはJava仮想マシンで動作を行うオブジェクト指向型プログラミング言語の1つです。静的型付けの関数型言語で、コンパイルエラーの検出に強みがあります。

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