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
180
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
270
ソフトウェアエンジニアとしてモナドを完全に理解する / make-perfect-sense-of-monad
jooohn
14
7.4k
ScalaのコンパイラにFizzBuzzを解いてもらう(Dottyもあるよ)
jooohn
1
900
Write stack safe non-tailrec recursive functions
jooohn
4
830
Introduction to Clean Architecture
jooohn
1
530
人類には早すぎる、謎の計算ロジックに立ち向かう / Strugle with the most complicated logic ever
jooohn
1
1.6k
Work at M3 USA
jooohn
0
1.2k
クラウド電子カルテを支えるテクノロジーの光と闇
jooohn
0
1.1k
怖くないCats
jooohn
0
700
Other Decks in Technology
See All in Technology
PdMはどのように全てのスピードを上げられるか ~ 非連続進化のための具体的な取り組み ~
sansantech
PRO
2
510
音声AIエージェントの世界とRetell AI入門 / Introduction to the World of Voice AI Agents and Retell AI
rkaga
5
920
ロリポップ! for Gamersを支えるインフラ/lolipop for gamers infrastructure
takumakume
0
120
四国クラウドお遍路 2024 in 高知 エンディング
yukataoka
0
190
App Router を実プロダクトで採用して見えてきた勘所をちょっとだけ紹介
marokanatani
1
890
Mocking in Rust Applications
taiki45
1
380
忙しい人のためのLangGraph概要まとめ
__ymgc__
1
150
Swift Testingのconfirmationを コードリーディング/Dive into Swift Testing confirmation
laprasdrum
1
230
四国のあのイベントの〇〇システムを45日間で構築した話 / cloudohenro2024_tachibana
biatunky
0
310
技術ブログや登壇資料を秒で作るコツ伝授します
minorun365
PRO
23
5.5k
Functional TypeScript
naoya
11
4.6k
Javaにおける関数型プログラミンへの取り組み
skrb
7
310
Featured
See All Featured
Designing for Performance
lara
604
68k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
157
15k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
225
22k
The Invisible Side of Design
smashingmag
295
50k
Writing Fast Ruby
sferik
623
60k
Visualization
eitanlees
142
15k
It's Worth the Effort
3n
182
27k
The Invisible Customer
myddelton
119
13k
Debugging Ruby Performance
tmm1
72
12k
Building a Modern Day E-commerce SEO Strategy
aleyda
36
6.8k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
36
2k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
38
9.2k
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!