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
220
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
320
ソフトウェアエンジニアとしてモナドを完全に理解する / make-perfect-sense-of-monad
jooohn
14
7.6k
ScalaのコンパイラにFizzBuzzを解いてもらう(Dottyもあるよ)
jooohn
1
1k
Write stack safe non-tailrec recursive functions
jooohn
4
910
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
780
Other Decks in Technology
See All in Technology
ワールドカフェI /チューターを改良する / World Café I and Improving the Tutors
ks91
PRO
0
120
ここはMCPの夜明けまえ
nwiizo
8
4.7k
AI AgentOps LT大会(2025/04/16) Algomatic伊藤発表資料
kosukeito
0
140
ElixirがHW化され、最新CPU/GPU/NWを過去のものとする数万倍、高速+超省電力化されたWeb/動画配信/AIが動く日
piacerex
0
140
更新系と状態
uhyo
7
1.5k
低レイヤを知りたいPHPerのためのCコンパイラ作成入門 / Building a C Compiler for PHPers Who Want to Dive into Low-Level Programming
tomzoh
1
230
Classmethod AI Talks(CATs) #21 司会進行スライド(2025.04.17) / classmethod-ai-talks-aka-cats_moderator-slides_vol21_2025-04-17
shinyaa31
0
580
AWSLambdaMCPServerを使ってツールとMCPサーバを分離する
tkikuchi
1
3k
AI Agentを「期待通り」に動かすために:設計アプローチの模索と現在地
kworkdev
PRO
2
450
アジャイル脅威モデリング#1(脅威モデリングナイト#8)
masakane55
3
200
SnowflakeとDatabricks両方でRAGを構築してみた
kameitomohiro
1
350
Porting PicoRuby to Another Microcontroller: ESP32
yuuu
4
410
Featured
See All Featured
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.5k
It's Worth the Effort
3n
184
28k
Side Projects
sachag
452
42k
Automating Front-end Workflow
addyosmani
1369
200k
Building Applications with DynamoDB
mza
94
6.3k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
19
1.1k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
Product Roadmaps are Hard
iamctodd
PRO
52
11k
Gamification - CAS2011
davidbonilla
81
5.2k
Documentation Writing (for coders)
carmenintech
69
4.7k
Raft: Consensus for Rubyists
vanstee
137
6.9k
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!