Scala の foldLeft ってなんだっけ


Scala は 3 年くらい書いてるけど foldLeft, foldRight をめったに使わなかった。Sangria のチュートリアル[1]をやってたら遭遇して何やってるんだか思い出せなかったので改めて調べた。

問題のコード。

  def getVotesByRelationIds(rel: RelationIds[Vote]): Future[Seq[Vote]] = db.run(
    Votes.filter { vote =>
      rel.rawIds
        .collect({
          case (SimpleRelation("byUser"), ids: Seq[Int]) => vote.userId inSet ids
          case (SimpleRelation("byLink"), ids: Seq[Int]) => vote.linkId inSet ids
        })
        .foldLeft(true: Rep[Boolean])(_ || _) // ← なにやってんだっけ…
    }.result
  )

結果から書くと、foldLeft の中身は丁寧に書くとこういうことになる

      .foldLeft(true: Rep[Boolean]) { (acc, rep) => acc || rep }

思い出し

シグネチャーを見るとこう。左から右に走査する。z は初期値で op の第一引数が accumulator。

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

具体的な例で感覚を取り戻す。左から順に、1 :: Nil → 2 :: List(1) → 3 :: List(2, 1) とやっていることになる

Seq(1, 2, 3).foldLeft(Nil: List[Int])((acc, x) => x :: acc)
// List(3, 2, 1)

アンダースコアを使って省略して書く場合について。上の丁寧な書き方は下のように書ける。(_ :+ _) は要するに ((_: List[Int]), (_: Int)) ということになる。お尻に要素を付け足していくのは要素数に応じて線形に時間かかるのでよくないけど例なので気にしないでおく。

Seq(1, 2, 3).foldLeft(Nil: List[Int])((acc, x) => acc :+ x)
Seq(1, 2, 3).foldLeft(0)(_ :+ _)

アンダースコアを使う場合は、acc, x の順を守ってないとだめなので、以下のように入れ替わってると怒られる((acc :: x) で解釈されてるから)。

Seq(1, 2, 3).foldLeft(Nil: List[Int])((acc, x) => x :: acc)
Seq(1, 2, 3).foldLeft(Nil: List[Int])(_ :: _) // error: value :: is not a member of Int

ちなみに、value :: is not a member of Int って言われてるのはこういう感じでひっくり返ってるから

1 :: 2 :: Nil
Nil.::(2).::(1)

その他

foldRight についてはこの記事も参考になりそう

https://dev.classmethod.jp/articles/scala-foldright-foldleft/

脚注
  1. https://www.howtographql.com/graphql-scala/7-relations/ ↩︎