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
組織を巻き込む大規模プラットフォーム移行戦略 〜50+サービスのマルチリージョン・マルチプロダクト化で学んだステークホルダー協働の実践〜 / Platform migration strategy engaging all stakeholders
toshi0607
2
220
人工衛星のファームウェアをRustで書く理由
koba789
15
8.3k
[ JAWS-UG 東京 CommunityBuilders Night #2 ]SlackとAmazon Q Developerで 運用効率化を模索する
sh_fk2
3
460
Webアプリケーションにオブザーバビリティを実装するRust入門ガイド
nwiizo
7
890
TS-S205_昨年対比2倍以上の機能追加を実現するデータ基盤プロジェクトでのAI活用について
kaz3284
1
230
「その開発、認知負荷高すぎませんか?」Platform Engineeringで始める開発者体験カイゼン術
sansantech
PRO
2
1k
Unlocking the Power of AI Agents with LINE Bot MCP Server
linedevth
0
120
測りにくい成果を測る — BtoB SaaSにおける効果検証への挑戦 / Shirokane Kougyou vol 20
sansan_randd
1
110
JTCにおける内製×スクラム開発への挑戦〜内製化率95%達成の舞台裏/JTC's challenge of in-house development with Scrum
aeonpeople
0
270
株式会社ログラス - 会社説明資料【エンジニア】/ Loglass Engineer
loglass2019
4
65k
使いやすいプラットフォームの作り方 ー LINEヤフーのKubernetes基盤に学ぶ理論と実践
lycorptech_jp
PRO
1
160
AWSを利用する上で知っておきたい名前解決のはなし(10分版)
nagisa53
10
3.2k
Featured
See All Featured
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
113
20k
Context Engineering - Making Every Token Count
addyosmani
3
63
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
18
1.1k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Statistics for Hackers
jakevdp
799
220k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
285
14k
Bash Introduction
62gerente
615
210k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
Thoughts on Productivity
jonyablonski
70
4.8k
Making Projects Easy
brettharned
117
6.4k
Code Review Best Practice
trishagee
71
19k
Mobile First: as difficult as doing things right
swwweet
224
9.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!