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
230
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
330
ソフトウェアエンジニアとしてモナドを完全に理解する / make-perfect-sense-of-monad
jooohn
14
7.7k
ScalaのコンパイラにFizzBuzzを解いてもらう(Dottyもあるよ)
jooohn
1
1k
Write stack safe non-tailrec recursive functions
jooohn
4
930
Introduction to Clean Architecture
jooohn
1
550
人類には早すぎる、謎の計算ロジックに立ち向かう / 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
810
Other Decks in Technology
See All in Technology
NW運用の工夫と発明
recuraki
1
780
人とAIとの共創を夢見た2か月 #共創AIミートアップ / Co-Creation with Keito-chan
kondoyuko
1
700
面接を通過するためにやってて良かったこと3選
sansantech
PRO
0
130
それでもぼくらは貢献をつづけるのだ(たぶん) @FOSS4GLT会#002
furukawayasuto
1
280
KMP導⼊において、マネジャーとして考えた事
sansantech
PRO
1
210
令和トラベルQAのAI活用
seigaitakahiro
0
520
ソフトウェアテストのAI活用_ver1.10
fumisuke
0
230
大手企業のAIツール導入の壁を越えて:サイバーエージェントのCursor活用戦略
gunta
14
2.5k
ゴリラ.vim #36 ~ Vim x SNS ~ スポンサーセッション
yasunori0418
1
350
Rebase エンジニアリング組織の現状とこれから
rebase_engineering
0
140
やさしいClaude Code入門
minorun365
PRO
31
24k
MCP で繋ぐ Figma とデザインシステム〜LLM を使った UI 実装のリアル〜
kimuson
2
1.3k
Featured
See All Featured
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
52
2.8k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
The Language of Interfaces
destraynor
158
25k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
180
53k
Practical Orchestrator
shlominoach
188
11k
Automating Front-end Workflow
addyosmani
1370
200k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Code Reviewing Like a Champion
maltzj
523
40k
Being A Developer After 40
akosma
91
590k
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!