Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Why foldRight is beautiful
Search
Jun Tomioka
July 18, 2018
Technology
0
240
Why foldRight is beautiful
Explains why "foldRight" is beautiful.
Jun Tomioka
July 18, 2018
Tweet
Share
More Decks by Jun Tomioka
See All by Jun Tomioka
Dotty で軽量な DI ライブラリをかいてみた
jooohn
1
340
ソフトウェアエンジニアとしてモナドを完全に理解する / make-perfect-sense-of-monad
jooohn
14
7.8k
ScalaのコンパイラにFizzBuzzを解いてもらう(Dottyもあるよ)
jooohn
1
1.1k
Write stack safe non-tailrec recursive functions
jooohn
4
950
Introduction to Clean Architecture
jooohn
1
560
人類には早すぎる、謎の計算ロジックに立ち向かう / Strugle with the most complicated logic ever
jooohn
1
1.7k
Work at M3 USA
jooohn
0
1.3k
クラウド電子カルテを支えるテクノロジーの光と闇
jooohn
0
1.3k
怖くないCats
jooohn
0
840
Other Decks in Technology
See All in Technology
Autonomous Database - Dedicated 技術詳細 / adb-d_technical_detail_jp
oracle4engineer
PRO
4
10k
新アイテムをどう使っていくか?みんなであーだこーだ言ってみよう / 20250911-rpi-jam-tokyo
akkiesoft
0
140
ガチな登山用デバイスからこんにちは
halka
1
230
AWSを利用する上で知っておきたい名前解決のはなし(10分版)
nagisa53
10
3k
生成AI時代のデータ基盤設計〜ペースレイヤリングで実現する高速開発と持続性〜 / Levtech Meetup_Session_2
sansan_randd
1
150
5年目から始める Vue3 サイト改善 #frontendo
tacck
PRO
3
210
会社紹介資料 / Sansan Company Profile
sansan33
PRO
6
380k
バイブスに「型」を!Kent Beckに学ぶ、AI時代のテスト駆動開発
amixedcolor
2
520
機械学習を扱うプラットフォーム開発と運用事例
lycorptech_jp
PRO
0
230
Skrub: machine-learning with dataframes
gaelvaroquaux
0
120
現場で効くClaude Code ─ 最新動向と企業導入
takaakikakei
1
210
Terraformで構築する セルフサービス型データプラットフォーム / terraform-self-service-data-platform
pei0804
1
150
Featured
See All Featured
The Art of Programming - Codeland 2020
erikaheidi
55
13k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
840
Balancing Empowerment & Direction
lara
3
620
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
187
55k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
StorybookのUI Testing Handbookを読んだ
zakiyama
31
6.1k
Raft: Consensus for Rubyists
vanstee
140
7.1k
A better future with KSS
kneath
239
17k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
8
520
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
Why You Should Never Use an ORM
jnunemaker
PRO
59
9.5k
Transcript
Why foldRight is beautiful Jun Tomioka (M3, inc.)
M3, Inc. Jun Tomioka Twitter: @jooohn1234 Github: jooohn Love: Our
very first baby Had great paternity leave!
None
foldLeft / foldRight
trait List[+A]
foldLeft[B](z: B)(op: (B, A) => B): B A A A
A A B A A A A B B OP ...
foldRight[B](z: B)(op: (A, B) => B): B A A A
A A B A A A A B B OP ...
So what’s the difference between them?
Suppose you define your own Linked List
foldLeft would be like this
foldRight would be like this
This naive foldRight can cause stack overflow
If so, why can foldRight be beautiful?
Let’s implement “map” with foldLeft
A A A A A List[B] A A A A
OP ... List[B] List[B]
Let’s implement “map” with foldLeft
foldRight
Let’s implement “map” with foldRight
A A A A A List[B] A A A A
List[B] List[B] OP ...
Why is it that natural to write “map” with foldRight?
Immutable recursive data structure
Bigger part holds smaller part
We must create them from smaller part to bigger part
This is the folding order of foldRight
foldRight folds items by its creation order
Why foldRight is beautiful • Immutable recursive data structure is
built from smaller part to bigger part • In this sense, foldRight folds items from smaller part to bigger part rather than from right to left ◦ Is quite natural to treat immutable recursive data structure
Thanks!