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
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
830
Other Decks in Technology
See All in Technology
Claude Codeは仕様駆動の夢を見ない
gotalab555
23
7.2k
2025新卒研修・Webアプリケーションセキュリティ #弁護士ドットコム
bengo4com
3
9.6k
AIが住民向けコンシェルジュに?Amazon Connectと生成AIで実現する自治体AIエージェント!
yuyeah
0
220
AIエージェントを現場で使う / 2025.08.07 著者陣に聞く!現場で活用するためのAIエージェント実践入門(Findyランチセッション)
smiyawaki0820
7
1.3k
自治体職員がガバクラの AWS 閉域ネットワークを理解するのにやって良かった個人検証環境
takeda_h
2
330
サービスロボット最前線:ugoが挑むPhysical AI活用
kmatsuiugo
0
140
はじめての転職講座/The Guide of First Career Change
kwappa
5
4.5k
信頼できる開発プラットフォームをどう作るか?-Governance as Codeと継続的監視/フィードバックが導くPlatform Engineeringの進め方
yuriemori
1
210
九州の人に知ってもらいたいGISスポット / gis spot in kyushu 2025
sakaik
0
200
Amazon S3 Vectorsは大規模ベクトル検索を低コスト化するサーバーレスなベクトルデータベースだ #jawsugsaga / S3 Vectors As A Serverless Vector Database
quiver
2
1k
工業高校で学習したとあるエンジニアのキャリアの話
shirayanagiryuji
0
120
家族の思い出を形にする 〜 1秒動画の生成を支えるインフラアーキテクチャ
ojima_h
3
1.4k
Featured
See All Featured
Designing for Performance
lara
610
69k
Making the Leap to Tech Lead
cromwellryan
134
9.5k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Raft: Consensus for Rubyists
vanstee
140
7.1k
Making Projects Easy
brettharned
117
6.3k
Building a Modern Day E-commerce SEO Strategy
aleyda
43
7.4k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
8
470
Speed Design
sergeychernyshev
32
1.1k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
31
2.2k
Automating Front-end Workflow
addyosmani
1370
200k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.9k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
33
2.4k
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!