-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
288 lines (260 loc) · 61.6 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
<!doctype html>
<html lang="zh"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"><meta><title>Trivializer</title><link rel="manifest" href="/manifest.json"><meta name="application-name" content="Trivializer"><meta name="msapplication-TileImage" content="/img/favicon.svg"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-title" content="Trivializer"><meta name="apple-mobile-web-app-status-bar-style" content="default"><meta property="og:type" content="blog"><meta property="og:title" content="Trivializer"><meta property="og:url" content="https://blog.tt314.xyz/"><meta property="og:site_name" content="Trivializer"><meta property="og:locale" content="zh_CN"><meta property="og:image" content="https://blog.tt314.xyz/img/og_image.png"><meta property="article:author" content="timetraveler314"><meta property="twitter:card" content="summary"><meta property="twitter:image:src" content="https://blog.tt314.xyz/img/og_image.png"><script type="application/ld+json">{"@context":"https://schema.org","@type":"BlogPosting","mainEntityOfPage":{"@type":"WebPage","@id":"https://blog.tt314.xyz"},"headline":"Trivializer","image":["https://blog.tt314.xyz/img/og_image.png"],"author":{"@type":"Person","name":"timetraveler314"},"publisher":{"@type":"Organization","name":"Trivializer","logo":{"@type":"ImageObject","url":{"text":"Trivializer"}}},"description":""}</script><link rel="icon" href="/img/favicon.svg"><link rel="stylesheet" href="https://use.fontawesome.com/releases/v6.0.0/css/all.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/styles/tokyo-night-dark.css"><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Ubuntu:wght@400;600&family=Source+Code+Pro"><link rel="stylesheet" href="/css/default.css"><style>body>.footer,body>.navbar,body>.section{opacity:0}</style><!--!--><!--!--><!--!--><!--!--><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/build/cookieconsent.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/css/lightgallery.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/css/justifiedGallery.min.css"><!--!--><!--!--><!--!--><style>.pace{-webkit-pointer-events:none;pointer-events:none;-webkit-user-select:none;-moz-user-select:none;user-select:none}.pace-inactive{display:none}.pace .pace-progress{background:#3273dc;position:fixed;z-index:2000;top:0;right:100%;width:100%;height:2px}</style><script src="https://cdn.jsdelivr.net/npm/[email protected]/pace.min.js"></script><!--!--><!--!--><!-- hexo injector head_end start --><script>
(function () {
function switchTab() {
if (!location.hash) {
return;
}
const id = '#' + CSS.escape(location.hash.substring(1));
const $tabMenu = document.querySelector(`.tabs a[href="${id}"]`);
if (!$tabMenu) {
return;
}
const $tabMenuContainer = $tabMenu.parentElement.parentElement;
Array.from($tabMenuContainer.children).forEach($menu => $menu.classList.remove('is-active'));
Array.from($tabMenuContainer.querySelectorAll('a'))
.map($menu => document.getElementById($menu.getAttribute("href").substring(1)))
.forEach($content => $content.classList.add('is-hidden'));
if ($tabMenu) {
$tabMenu.parentElement.classList.add('is-active');
}
const $activeTab = document.querySelector(id);
if ($activeTab) {
$activeTab.classList.remove('is-hidden');
}
}
switchTab();
window.addEventListener('hashchange', switchTab, false);
})();
</script><!-- hexo injector head_end end --><meta name="generator" content="Hexo 7.0.0"></head><body class="is-2-column"><nav class="navbar navbar-main"><div class="container navbar-container"><div class="navbar-brand justify-content-center"><a class="navbar-item navbar-logo" href="/">Trivializer</a></div><div class="navbar-menu"><div class="navbar-start"><a class="navbar-item is-active" href="/">Home</a><a class="navbar-item" href="/archives">Archives</a><a class="navbar-item" href="/categories">Categories</a><a class="navbar-item" href="/tags">Tags</a><a class="navbar-item" href="/about">About</a><a class="navbar-item" href="/links">Links</a></div><div class="navbar-end"><a class="navbar-item" target="_blank" rel="noopener" title="Download on GitHub" href="https://github.com/ppoffice/hexo-theme-icarus"><i class="fab fa-github"></i></a><a class="navbar-item search" title="搜索" href="javascript:;"><i class="fas fa-search"></i></a></div></div></div></nav><section class="section"><div class="container"><div class="columns"><div class="column order-2 column-main is-8-tablet is-8-desktop is-8-widescreen"><div class="card"><article class="card-content article" role="article"><div class="article-meta is-size-7 is-uppercase level is-mobile"><div class="level-left"><span class="level-item"><time dateTime="2023-12-29T06:04:21.000Z" title="12/29/2023, 2:04:21 PM">2023-12-29</time>发表</span><span class="level-item"><time dateTime="2023-12-30T14:47:28.686Z" title="12/30/2023, 10:47:28 PM">2023-12-30</time>更新</span><span class="level-item"><a class="link-muted" href="/categories/Program-Calculation/">Program Calculation</a></span><span class="level-item">8 分钟读完 (大约1143个字)</span></div></div><p class="title is-3 is-size-4-mobile"><a class="link-muted" href="/2023/12/29/Program-Calculation-Fusion-and-Tupling/">Program Calculation: Fusion and Tupling</a></p><div class="content"><h1 id="fusion">Fusion</h1>
<p>考虑计算List最大值的 <code>max</code> 函数. 利用
<code>sort</code>，我们可以给出一个简单的规约：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">max</span> = head . sort</span><br><span class="line"> <span class="keyword">where</span> sort = foldr insert []</span><br><span class="line"> insert x [] = [x]</span><br><span class="line"> insert x (y:ys) | x >= y = x : y : ys</span><br><span class="line"> | otherwise = y : insert x ys</span><br></pre></td></tr></table></figure>
<p>但是大家都知道这样太慢了，因为 <code>sort</code>
会对整个List进行排序，而我们只需要最大值.
这个问题归结到直接利用<code>sort</code>会带来太多不需要的中间结果.
为了解决这个问题，我们考虑把<code>head</code>整合进<code>sort</code>中.
这样我们引入一个新的概念：<strong>Fusion</strong>.</p>
<h2 id="fusion-law-for-foldr">Fusion Law for <code>foldr</code></h2>
<p>在处理List上的问题时经常会用到<code>foldr</code>.
在这里，我们考虑把一个外围的函数<code>f</code>整合入<code>foldr</code>中，给出如下的Lemma:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">f</span> (a ⊕ r) = a ⊗ f r</span><br><span class="line"><span class="comment">------------------------------------</span></span><br><span class="line"><span class="title">f</span> · foldr (⊕) e = foldr (⊗) (f e)</span><br></pre></td></tr></table></figure>
<p>在这里和以后的一些表示中，<span
class="math inline">\(r\)</span>意味着“recursive”，即<code>foldr</code>的递归部分.</p>
<p>因此我们需要的是通过程序演算找到合适的运算符⊗.
以<code>max</code>为例，可以对<code>head (insert a r)</code>做如下的演算：</p>
<ul>
<li>对于 <span class="math inline">\(r = []\)</span>,</li>
</ul>
<p><span class="math display">\[
\begin{align*}
\text{head} \space ( \text{insert} \space a \space r) &= \text{head}
\space ( \text{insert} \space a \space []) \\
&= \text{head} \space [a] \\
&= a \\
\end{align*}
\]</span></p>
<ul>
<li>对于 <span class="math inline">\(r = y:ys\)</span>,</li>
</ul>
<p><span class="math display">\[
\begin{align*}
& \text{head} \space (\text{insert} \space a \space (y : ys)) \\
=& \space \{ \space \text{def. of insert} \space \} \\
& \text{head} \space (\text{if} \space a \geqslant y \space
\text{then} \space a : y : ys \space \text{else} \space y :
\text{insert} \space a \space ys) \\
=& \space \{ \space \text{distribute head over if} \space \} \\
& \text{if} \space a \geqslant y \space \text{then} \space
\text{head} \space (a : y : ys) \space \text{else} \space \text{head}
\space (y : \text{insert} \space a \space ys) \\
=& \space \{ \space \text{def. of head} \space \} \\
& \text{if} \space a \geqslant y \space \text{then} \space a \space
\text{else} \space y \\
=& \space \{ \space \text{assumption: } r=y:ys \space \} \\
& \text{if} \space a \geqslant \text{head} \space r \space
\text{then} \space a \space \text{else} \space \text{head} \space r \\
\end{align*}
\]</span></p>
<p>（以后的演算会适当省略一些推理依据，并按照Haskell的语法来书写）</p>
<p>最后我们得到了一个合适的运算符 <span class="math inline">\(\otimes =
\text{if} \space a \geqslant \text{head} \space r \space \text{then}
\space a \space \text{else} \space \text{head} \space
r\)</span>，因此我们可以得到：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">head</span> (insert a r) = a ⊗ (head r)</span><br></pre></td></tr></table></figure>
<p>因此按照Fusion Law，我们可以得到：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">max</span> = head . foldr insert [] = foldr ⊗ (head []) = foldr ⊗ (-∞)</span><br></pre></td></tr></table></figure>
<p>现在通过Fusion,我们的<code>max</code>已经是一个线性时间的算法了.</p>
<h2 id="more-examples">More Examples</h2>
<p>以上关于<code>max</code>的推演还是比较显然的，但是仍然能展示出Fusion在消除中间结果、将两个函数合并成一个函数上的作用.
现在我们考虑一个更复杂的例子：在List上的<code>reverse</code>.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">reverse</span> = foldr snoc []</span><br><span class="line"> <span class="keyword">where</span> snoc x xs = xs ++ [x]</span><br></pre></td></tr></table></figure>
<p>现在我们引入一个数组作为辅助，定义一个我们希望变得更快的函数<code>fastrev</code>.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">helper</span> xs ys = reverse xs ++ ys</span><br><span class="line"><span class="comment">-- 等价于</span></span><br><span class="line"><span class="title">helper</span> xs = (++) (reverse xs)</span><br><span class="line"> = (++) (foldr snoc [] xs)</span><br><span class="line"></span><br><span class="line"><span class="title">fastrev</span> = helper xs []</span><br></pre></td></tr></table></figure>
<p>考虑提升<code>helper</code>的效率，这可以通过将<code>++</code> 和
<code>snoc</code> 合并成一个函数来实现.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"> (++) (snoc a r)</span><br><span class="line">= { η expansion }</span><br><span class="line"> λ y -> ((r ++ [a]) ++ y)</span><br><span class="line">= { associativity <span class="keyword">of</span> ++ }</span><br><span class="line"> λ y -> (r ++ ([a] ++ y))</span><br><span class="line">= { }</span><br><span class="line"> r ++ (λ y -> [a] ++ y)</span><br></pre></td></tr></table></figure>
<p>在Fusion Law中取 <code>f= λ x -> (++) x</code>我们可以得到：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">(++) (r ++ [a]) = a ⊗ ((++) r)</span><br><span class="line"> <span class="keyword">where</span> a ⊗ r' = λ y r' -> r' ([a] ++ y)</span><br></pre></td></tr></table></figure>
<p>因此，<code>helper</code>可以被重写为：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">helper</span> xs = λ ys -> (++ ys) (foldr snoc [] xs)</span><br><span class="line"> = foldr (⊗) (++ []) xs</span><br><span class="line"> = foldr (⊗) id xs</span><br><span class="line"> <span class="keyword">where</span> a ⊗ r' = λ y r' -> r' ([a] ++ y)</span><br></pre></td></tr></table></figure>
<p>我们通过Fusion的推理得到了一个线性时间的算法！</p>
<p>展开<code>foldr</code>,则<code>fastrev</code>可以被重写为：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">fastrev</span> xs = helper xs []</span><br><span class="line"> <span class="keyword">where</span> helper [] y = y</span><br><span class="line"> helper (x:xs) y = helper xs (x:y)</span><br></pre></td></tr></table></figure>
<p>这是我们常见的<code>fastrev</code>的样子.
通过以上的例子，我们可以看到Fusion Law的作用.</p>
<h3 id="exercises">Exercises</h3>
<p>利用Fusion Law证明以下等式：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">1</span>. foldr (⊕) e . map f = foldr (⊗) e</span><br><span class="line"> <span class="keyword">where</span> a ⊗ r = f a ⊕ r</span><br><span class="line"><span class="number">2</span>. map f . map g = map (f . g)</span><br><span class="line"><span class="number">3</span>. foldr (⊕) e . filter p = foldr (⊗) e</span><br><span class="line"> <span class="keyword">where</span> a ⊗ r = <span class="keyword">if</span> p a <span class="keyword">then</span> a ⊕ r <span class="keyword">else</span> r</span><br></pre></td></tr></table></figure>
<h3 id="solution">Solution</h3>
<p>考虑<code>map</code>也可以利用<code>foldr</code>来实现：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">map</span> f = foldr ((:) . f) []</span><br></pre></td></tr></table></figure>
<p>因此，我们便可以利用Fusion
Law，将外围原有的<code>foldr</code>整合进<code>map</code>中.
记<code>u = foldr (⊕) e</code>，则：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">u</span> (((:) . f) a r) = u (f a : r)</span><br><span class="line"> = f a ⊕ u r</span><br><span class="line"> = a ⊗ u r</span><br><span class="line"> <span class="keyword">where</span> a ⊗ r = f a ⊕ r</span><br></pre></td></tr></table></figure>
<p>由Fusion Law, 1是显然的.</p>
<p>考虑 2
中<code>map f</code>也可以写成<code>foldr</code>,这就回到了第一个问题，也是显然的.</p>
<p>类似地，3
中<code>filter</code>也可以利用<code>foldr</code>来实现：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">filter</span> p = foldr (λ a r -> <span class="keyword">if</span> p a <span class="keyword">then</span> a : r <span class="keyword">else</span> r) []</span><br></pre></td></tr></table></figure>
<p>至此，我们利用Fusion Law证明了以上三个等式.</p>
<p>To Be Continued...</p>
</div></article></div><div class="card"><article class="card-content article" role="article"><div class="article-meta is-size-7 is-uppercase level is-mobile"><div class="level-left"><span class="level-item"><time dateTime="2023-11-04T13:36:22.000Z" title="11/4/2023, 9:36:22 PM">2023-11-04</time>发表</span><span class="level-item"><time dateTime="2023-12-29T05:29:37.927Z" title="12/29/2023, 1:29:37 PM">2023-12-29</time>更新</span><span class="level-item"><a class="link-muted" href="/categories/Calculus/">Calculus</a></span><span class="level-item">2 分钟读完 (大约320个字)</span></div></div><p class="title is-3 is-size-4-mobile"><a class="link-muted" href="/2023/11/04/Problems-on-Contiunity/">连续函数的几个问题！</a></p><div class="content"><p><strong>Q</strong> $g(x)$ 是定义在 $ [0,1] $ 上的函数，满足 $ g(0)=1,g(1)=0 $，如果函数 $ g(x)+ \tan x $ 单调上升，证明：$ g(x) $可以取到 $ [0,1] $ 内任意的值. </p>
<hr>
<p><strong>Proof</strong> 考虑更一般的问题：</p>
<p>$ f(x) $ 是 $ [0,1] $ 上的连续函数， $g(x)$ 是定义在 $ [0,1] $ 上的函数，满足 $ g(0)>0,g(1)<0 $，如果函数 $ f(x) + g(x) $ 单调上升，证明：$ g(x) $ 有零点. </p>
<p>这类问题的一般解决方法：Lebesgue方法.</p>
<p>考虑构造集合 $ A={x \mid g(x) \geqslant 0} $，我们取 $ c=\sup A $ 并证明 $ c $ 就是 $ g(x) $ 的零点. </p>
<ul>
<li>$ t>c $ 时，<br>$$ f(t)\geqslant f(t)+g(t)\geqslant f(c)+g(c) $$</li>
</ul>
<p>这说明 $ g(c)\leqslant f(t)-f(c) $，</p>
<p>两边取 $ t\to c $ 的极限，由于 $ f(x) $ 连续， $ g(c)\leqslant 0 $. </p>
<ul>
<li>$ t<c $ 时，类似得到<br>$$ f(t)\leqslant f(t)+g(t)\leqslant f(c)+g(c)$$</li>
</ul>
<p>这说明 $ g(c)\geqslant f(t)-f(c) $，</p>
<p>两边取 $ t\to c $ 的极限，由于 $ f(x) $ 连续， $ g(c)\geqslant 0 $.</p>
<p>综上， $ g(c)=0 $，即 $ c $ 是 $ g(x) $ 的零点.</p>
<p>回到原问题，对于任意的 $\eta \in [0,1] $ 取 $ f(x)=\tan x $，$ h(x)=g(x)-\eta $，对于 $ f(x) $ 和 $ h(x) $ 应用上面的结论，我们知道 $ h(x) $ 有零点，即 $ g(x) $ 可以取到 $ [0,1] $ 内任意的值.</p>
</div></article></div><div class="card"><article class="card-content article" role="article"><div class="article-meta is-size-7 is-uppercase level is-mobile"><div class="level-left"><span class="level-item"><time dateTime="2023-11-04T05:31:45.000Z" title="11/4/2023, 1:31:45 PM">2023-11-04</time>发表</span><span class="level-item"><time dateTime="2023-11-04T13:02:01.795Z" title="11/4/2023, 9:02:01 PM">2023-11-04</time>更新</span><span class="level-item"><a class="link-muted" href="/categories/Functional-Programming/">Functional Programming</a></span><span class="level-item">6 分钟读完 (大约851个字)</span></div></div><p class="title is-3 is-size-4-mobile"><a class="link-muted" href="/2023/11/04/Monadic-Parser/">Monadic Parser</a></p><div class="content"><h2 id="Monadic-Parser"><a href="#Monadic-Parser" class="headerlink" title="Monadic Parser"></a>Monadic Parser</h2><h3 id="Parser"><a href="#Parser" class="headerlink" title="Parser"></a>Parser</h3><p>A parser is a function that takes a string as input, then parses the string, and gives back an output.</p>
<p>However, the process may fail as the input string may not be a valid input for the parser. To describe the result, here we use a list <code>[a]</code> to represent the result, where <code>a</code> is the type of the output, and when parsing fails, we get an empty list.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">newtype</span> <span class="type">Parser</span> a = <span class="type">Parser</span> { <span class="title">parse</span> :: <span class="type">String</span> -> [(<span class="title">a</span>, <span class="type">String</span>)] }</span></span><br></pre></td></tr></table></figure>
<p>Now we begin with “atoms” of parser, which consumes the smallest possible input, i.e. a char:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">item</span> :: <span class="type">Parser</span> <span class="type">Char</span></span><br><span class="line"><span class="title">item</span> = <span class="type">Parser</span> $ \s -> <span class="keyword">case</span> s <span class="keyword">of</span></span><br><span class="line"> [] -> []</span><br><span class="line"> (x:xs) -> [(x, xs)]</span><br></pre></td></tr></table></figure>
<p>Here we want to compose parsers, so declaring <code>Parser</code> as a <code>Functor</code>, <code>Applicative</code>, and even <code>Monad</code> is necessary:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Functor</span> <span class="type">Parser</span> <span class="keyword">where</span></span></span><br><span class="line"> <span class="comment">-- fmap :: (a -> b) -> Parser a -> Parser b</span></span><br><span class="line"> fmap f (<span class="type">Parser</span> p) = <span class="type">Parser</span> $ \s -> [(f a, s') | (a, s') <- p s]</span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Applicative</span> <span class="type">Parser</span> <span class="keyword">where</span></span></span><br><span class="line"> pure a = <span class="type">Parser</span> $ \s -> [(a, s)] <span class="comment">-- keep the input string unchanged</span></span><br><span class="line"> <span class="comment">-- (<*>) :: Parser (a -> b) -> Parser a -> Parser b</span></span><br><span class="line"> pg <*> px = <span class="type">Parser</span> $ \s -> [(g x, s'') | (g, s') <- parse pg s, (x, s'') <- parse px s']</span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Monad</span> <span class="type">Parser</span> <span class="keyword">where</span></span></span><br><span class="line"> return = pure</span><br><span class="line"> <span class="comment">-- (>>=) :: Parser a -> (a -> Parser b) -> Parser b</span></span><br><span class="line"> px >>= f = <span class="type">Parser</span> $ \s -> concat [parse (f x) s' | (x, s') <- parse px s]</span><br></pre></td></tr></table></figure>
<p>By virtue of the <code>do</code> notation, we can now compose parsers easily:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">three</span> = <span class="keyword">do</span> </span><br><span class="line"> x <- item</span><br><span class="line"> item</span><br><span class="line"> z <- item</span><br><span class="line"> return (x, z)</span><br><span class="line"></span><br><span class="line">> parse three <span class="string">"abcdef"</span></span><br><span class="line">[((<span class="string">'a'</span>,<span class="string">'c'</span>),<span class="string">"def"</span>)]</span><br></pre></td></tr></table></figure>
<p>The remarkable thing is that the <code>Monad</code> instance of <code>Parser</code> allows what ,In contract, when a computation is lifted by <code>Applicative</code>, the type can’t be changed, so any middle operation cannot change the type of the computation.</p>
<h3 id="Alternative"><a href="#Alternative" class="headerlink" title="Alternative"></a>Alternative</h3><p>You may notice that we were just doing some linear parsing in the previous section. Now we want to make choices in parsing, so we need to define <code>Alternative</code>:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">-- import Control.Applicative</span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Applicative</span> <span class="type">Alternative</span> <span class="keyword">where</span></span></span><br><span class="line"> empty :: f a</span><br><span class="line"> (<|>) :: f a -> f a -> f a</span><br></pre></td></tr></table></figure>
<p>The class <code>Alternative</code> is a subclass of <code>Applicative</code>, and it is used to represent choice, by the operand <code><|></code>. To ensure what we implement really stands for making choices, we need to obey the following laws, which shows the essence of choice:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">Associativity</span>: x <|> (y <|> z) = (x <|> y) <|> z</span><br><span class="line"><span class="type">Left</span> <span class="type">Identity</span>: empty <|> x = x</span><br><span class="line"><span class="type">Right</span> <span class="type">Identity</span>: x <|> empty = x</span><br></pre></td></tr></table></figure>
<h4 id="Making-many-some-choices"><a href="#Making-many-some-choices" class="headerlink" title="Making many & some choices"></a>Making <code>many</code> & <code>some</code> choices</h4><p>The concept is a bit like <code>while</code> and <code>do-while</code>, we repeat the computation until it fails, and we get the result.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">-- many : Zero or more.</span></span><br><span class="line"><span class="title">many</span> :: <span class="type">Alternative</span> f => f a -> f [a]</span><br><span class="line"><span class="title">many</span> v = some v <|> pure []</span><br><span class="line"></span><br><span class="line"><span class="comment">-- some : One or more.</span></span><br><span class="line"><span class="title">some</span> :: <span class="type">Alternative</span> f => f a -> f [a]</span><br><span class="line"><span class="title">some</span> v = (:) <$> v <*> many v</span><br></pre></td></tr></table></figure>
<p>Their diffecence is that <code>some</code> must succeed at least once, while <code>many</code> may fail at the beginning. We use examples to clarify the difference:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">> many <span class="type">Nothing</span></span><br><span class="line"><span class="type">Just</span> []</span><br><span class="line"></span><br><span class="line">> some <span class="type">Nothing</span></span><br><span class="line"><span class="type">Nothing</span></span><br></pre></td></tr></table></figure>
<hr>
<p>Then the <code>Parser</code> instance serves as a perfect example of <code>Alternative</code>:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Alternative</span> <span class="type">Parser</span> <span class="keyword">where</span></span></span><br><span class="line"> empty = <span class="type">Parser</span> $ \s -> []</span><br><span class="line"> <span class="comment">-- (<|>) :: Parser a -> Parser a -> Parser a</span></span><br><span class="line"> p <|> q = <span class="type">Parser</span> $ \s -> <span class="keyword">case</span> parse p s <span class="keyword">of</span></span><br><span class="line"> [] -> parse q s</span><br><span class="line"> [(x, s')] -> [(x, s')]</span><br></pre></td></tr></table></figure>
<p>Now we can use <code><|></code> to make choices in parsing:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">> parse (item <|> return <span class="string">'d'</span>) <span class="string">"abc"</span></span><br><span class="line">[(<span class="string">'a'</span>,<span class="string">"bc"</span>)]</span><br><span class="line">> parse (empty <|> return <span class="string">'d'</span>) <span class="string">"abc"</span> <span class="comment">-- fails</span></span><br><span class="line">[(<span class="string">'d'</span>,<span class="string">"abc"</span>)]</span><br></pre></td></tr></table></figure>
<h3 id="Get-down-to-Parsers"><a href="#Get-down-to-Parsers" class="headerlink" title="Get down to Parsers!"></a>Get down to Parsers!</h3><p>We often want to make judgments on the input string, so we need to define some predicates:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">-- Whether the next chat satisfies the predicate.</span></span><br><span class="line"><span class="title">sat</span> :: (<span class="type">Char</span> -> <span class="type">Bool</span>) -> <span class="type">Parser</span> <span class="type">Char</span></span><br><span class="line"><span class="title">sat</span> p = <span class="keyword">do</span> t <- item</span><br><span class="line"> <span class="keyword">if</span> p t <span class="keyword">then</span> return t <span class="keyword">else</span> empty</span><br></pre></td></tr></table></figure>
<p>Then we can define some parsers that consume specific chars and strings:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">char</span> :: <span class="type">Char</span> -> <span class="type">Parser</span> <span class="type">Char</span></span><br><span class="line"><span class="title">char</span> c = sat (== c)</span><br><span class="line"></span><br><span class="line"><span class="title">string</span> :: <span class="type">String</span> -> <span class="type">Parser</span> <span class="type">String</span></span><br><span class="line"><span class="title">string</span> (x:xs) = <span class="keyword">do</span> char x</span><br><span class="line"> string xs</span><br><span class="line"> return (x:xs)</span><br></pre></td></tr></table></figure>
<p>Using <code>many</code>, we also have something that consumes multiple spaces, processes natural numbers:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">space</span> :: <span class="type">Parser</span> ()</span><br><span class="line"><span class="title">space</span> = <span class="keyword">do</span> many (sat isSpace)</span><br><span class="line"> return ()</span><br><span class="line"></span><br><span class="line"><span class="title">nat</span> :: <span class="type">Parser</span> <span class="type">Int</span></span><br><span class="line"><span class="title">nat</span> = <span class="keyword">do</span> xs <- some digit</span><br><span class="line"> return (read xs)</span><br></pre></td></tr></table></figure>
<p>When using spaces to separate different parts of the string, we can use <code>token</code> to consume the spaces:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">token</span> :: <span class="type">Parser</span> a -> <span class="type">Parser</span> a</span><br><span class="line"><span class="title">token</span> p = <span class="keyword">do</span> space</span><br><span class="line"> v <- p</span><br><span class="line"> space</span><br><span class="line"> return v</span><br><span class="line"></span><br><span class="line"><span class="comment">-- Tokenized parsers</span></span><br><span class="line"><span class="title">symbol</span> :: <span class="type">String</span> -> <span class="type">Parser</span> <span class="type">String</span></span><br><span class="line"><span class="title">symbol</span> xs = token $ string xs</span><br><span class="line"></span><br><span class="line"><span class="title">natural</span> :: <span class="type">Parser</span> <span class="type">Int</span></span><br><span class="line"><span class="title">natural</span> = token nat</span><br></pre></td></tr></table></figure>
<h3 id="Arithmetic-Expressions"><a href="#Arithmetic-Expressions" class="headerlink" title="Arithmetic Expressions"></a>Arithmetic Expressions</h3><p>Now we can define a parser for arithmetic expressions. Given the properties of the operators, we can describe the wanted syntax as the following context free grammar:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">expr</span> ::= term <span class="string">'+'</span> expr | term</span><br><span class="line"><span class="title">term</span> ::= factor <span class="string">'*'</span> term | factor</span><br><span class="line"><span class="title">factor</span> ::= digit | <span class="string">'('</span> expr <span class="string">')'</span></span><br><span class="line"><span class="title">digit</span> ::= <span class="string">'0'</span> | <span class="string">'1'</span> | ... | <span class="string">'9'</span></span><br></pre></td></tr></table></figure>
<p>Once we have the grammar, we can easily translate it into Haskell code:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">expr</span> :: <span class="type">Parser</span> <span class="type">Int</span></span><br><span class="line"><span class="title">expr</span> = <span class="keyword">do</span></span><br><span class="line"> t <- term</span><br><span class="line"> <span class="keyword">do</span></span><br><span class="line"> symbol <span class="string">"+"</span></span><br><span class="line"> e <- expr</span><br><span class="line"> return (t + e)</span><br><span class="line"> <|> <span class="keyword">do</span></span><br><span class="line"> symbol <span class="string">"-"</span></span><br><span class="line"> e <- expr</span><br><span class="line"> return (t - e)</span><br><span class="line"> <|> return t</span><br><span class="line"></span><br><span class="line"><span class="title">term</span> :: <span class="type">Parser</span> <span class="type">Int</span></span><br><span class="line"><span class="title">term</span> = <span class="keyword">do</span> </span><br><span class="line"> f <- factor</span><br><span class="line"> <span class="keyword">do</span></span><br><span class="line"> symbol <span class="string">"*"</span></span><br><span class="line"> t <- term</span><br><span class="line"> return (f * t)</span><br><span class="line"> <|> <span class="keyword">do</span></span><br><span class="line"> symbol <span class="string">"/"</span></span><br><span class="line"> t <- term</span><br><span class="line"> return (f `div` t)</span><br><span class="line"> <|> return f</span><br><span class="line"></span><br><span class="line"><span class="title">factor</span> :: <span class="type">Parser</span> <span class="type">Int</span></span><br><span class="line"><span class="title">factor</span> = <span class="keyword">do</span></span><br><span class="line"> symbol <span class="string">"("</span></span><br><span class="line"> e <- expr</span><br><span class="line"> symbol <span class="string">")"</span></span><br><span class="line"> return e</span><br><span class="line"> <|> natural</span><br></pre></td></tr></table></figure>
<p>Finally it’s time to parse and evaluate the final value!</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">eval</span> :: <span class="type">String</span> -> <span class="type">Int</span></span><br><span class="line"><span class="title">eval</span> = fst . head . parse expr</span><br></pre></td></tr></table></figure></div></article></div><div class="card"><article class="card-content article" role="article"><div class="article-meta is-size-7 is-uppercase level is-mobile"><div class="level-left"><span class="level-item"><time dateTime="2023-11-03T06:15:08.000Z" title="11/3/2023, 2:15:08 PM">2023-11-03</time>发表</span><span class="level-item"><time dateTime="2023-11-03T13:36:42.542Z" title="11/3/2023, 9:36:42 PM">2023-11-03</time>更新</span><span class="level-item"><a class="link-muted" href="/categories/Functional-Programming/">Functional Programming</a></span><span class="level-item">3 分钟读完 (大约482个字)</span></div></div><p class="title is-3 is-size-4-mobile"><a class="link-muted" href="/2023/11/03/Foldable-and/">Foldable and ...</a></p><div class="content"><h2 id="Foldable-and-Friends"><a href="#Foldable-and-Friends" class="headerlink" title="Foldable and Friends"></a>Foldable and Friends</h2><h3 id="Foldable"><a href="#Foldable" class="headerlink" title="Foldable"></a>Foldable</h3><p>The type class <code>Foldable</code> generally relies on <code>Monoid</code>, and it describes data structures that can be folded to a summary value, so the <code>mappend(<>)</code> defined on <code>Monoid</code> is needed to show that the containing data in <code>Foldable</code> can be combined:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="type">Foldable</span> t <span class="keyword">where</span></span></span><br><span class="line"> fold :: <span class="type">Monoid</span> a => t a -> a</span><br><span class="line"> foldMap :: <span class="type">Monoid</span> b => (a -> b) -> t a -> b</span><br><span class="line"> foldr :: (a -> b -> b) -> b -> t a -> b</span><br><span class="line"> foldl :: (b -> a -> b) -> b -> t a -> b</span><br></pre></td></tr></table></figure>
<p>Here is a <code>foldMap</code> example on lists:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">foldMapList</span> :: <span class="type">Monoid</span> m => (a -> m) -> [a] -> m</span><br><span class="line"><span class="title">foldMapList</span> f [] = mempty</span><br><span class="line"><span class="title">foldMapList</span> f (x:xs) = f x <> foldMapList f xs</span><br></pre></td></tr></table></figure>
<p>The minimal definition is <code>foldMap</code> or <code>foldr</code>, and using one of these two we can define them all:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">fold</span> = foldMap id</span><br><span class="line"><span class="title">foldMap</span> f = foldr (mappend . f) mempty</span><br><span class="line"><span class="title">toList</span> = foldMap (\x -> [x]) <span class="comment">-- Here, we use the monoid of lists, which is concatenation</span></span><br></pre></td></tr></table></figure>
<p>However, the folding directions are not absolute. For example, we can define <code>foldl</code> in terms of <code>foldr</code> (even though it is not efficient enough, it still shows some type of homomorphism):</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">foldl</span> :: <span class="type">Foldable</span> t => (b -> a -> b) -> b -> t a -> b</span><br><span class="line"><span class="title">foldl</span> f z ys = foldr (\x g -> g . f x) id ys z</span><br></pre></td></tr></table></figure>
<p>To understand the entire process, we first notice that if we want to reverse the computation order, we may leave the computation “undone”, and gradually fold other elements into the process.</p>
<p>So in this implementation of <code>foldl</code>, the type <code>b</code> is used as the “undone” computation, i.e. function <code>a -> a</code> (like <code>(+) 1</code>), and the initial value is the identity map. After iterations, we shall get:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">id</span> <span class="comment">-- \x -> x</span></span><br><span class="line">\x -> f x y0</span><br><span class="line">\x -> f (f x y0) y1</span><br><span class="line">...</span><br><span class="line">\x -> f (... f (f (f x y0) y1) ... yN)</span><br></pre></td></tr></table></figure>
<p>When the folding process ends, we apply the “undone” computation to the initial value <code>z</code>, and we get the final result, in a reversed order.</p>
<hr>
<p>In conclusion, “Folding” is the abstraction of sequential operations (or sequential recursion) on a data structure. Example:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">map</span> f = foldr ((:) . f) [] <span class="comment">-- or foldMap (pure . f)</span></span><br></pre></td></tr></table></figure>
<h3 id="Traversable"><a href="#Traversable" class="headerlink" title="Traversable"></a>Traversable</h3><p>Now let’s take a look at <code>map</code>.</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">map</span> :: (a -> b) -> [a] -> [b]</span><br><span class="line"><span class="title">map</span> g [] = []</span><br><span class="line"><span class="title">map</span> g (x:xs) = g x : map g xs</span><br></pre></td></tr></table></figure>
<p>We get the motivation of <code>Traversable</code> from the need of generalizing <code>map</code> to deal with effects brought by various functors. </p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> (<span class="type">Functor</span> <span class="title">t</span>, <span class="type">Foldable</span> <span class="title">t</span>) => <span class="type">Traversable</span> t <span class="keyword">where</span></span></span><br><span class="line"> traverse :: <span class="type">Applicative</span> f => (a -> f b) -> t a -> f (t b)</span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Traversable</span> [] <span class="keyword">where</span></span></span><br><span class="line"> traverse g [] = pure []</span><br><span class="line"> traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs</span><br></pre></td></tr></table></figure>
<p>In the default definition of <code>Traversable</code>, another function <code>sequenceA</code> is introduced. It folds a series of effects into a single effect:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">sequenceA</span> :: <span class="type">Applicative</span> f => t (f a) -> f (t a)</span><br><span class="line"><span class="title">sequenceA</span> = traverse id</span><br><span class="line"></span><br><span class="line"><span class="comment">--- Examples:</span></span><br><span class="line">> sequenceA [<span class="type">Just</span> <span class="number">1</span>, <span class="type">Just</span> <span class="number">2</span>, <span class="type">Just</span> <span class="number">3</span>]</span><br><span class="line"><span class="type">Just</span> [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]</span><br><span class="line"></span><br><span class="line">> sequenceA [<span class="type">Just</span> <span class="number">1</span>, <span class="type">Nothing</span>, <span class="type">Just</span> <span class="number">3</span>]</span><br><span class="line"><span class="type">Nothing</span></span><br></pre></td></tr></table></figure>
<p>We can also define <code>traverse</code> in turn:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="title">traverse</span> g = sequenceA . fmap g</span><br></pre></td></tr></table></figure></div></article></div><div class="card"><article class="card-content article" role="article"><div class="article-meta is-size-7 is-uppercase level is-mobile"><div class="level-left"><span class="level-item"><time dateTime="2023-11-03T03:36:20.694Z" title="11/3/2023, 11:36:20 AM">2023-11-03</time>发表</span><span class="level-item"><time dateTime="2023-11-03T10:43:22.468Z" title="11/3/2023, 6:43:22 PM">2023-11-03</time>更新</span><span class="level-item">几秒读完 (大约0个字)</span></div></div><p class="title is-3 is-size-4-mobile"><a class="link-muted" href="/2023/11/03/hello-world/">Hello World</a></p><div class="content"></div></article></div></div><div class="column column-left is-4-tablet is-4-desktop is-4-widescreen order-1"><div class="card widget" data-type="profile"><div class="card-content"><nav class="level"><div class="level-item has-text-centered flex-shrink-1"><div><figure class="image is-128x128 mx-auto mb-2"><img class="avatar is-rounded" src="https://s2.loli.net/2023/11/03/JxOZhzY1e6LbWcr.gif" alt="timetraveler314"></figure><p class="title is-size-4 is-block" style="line-height:inherit;">timetraveler314</p><p class="is-size-6 is-block">Ad astra.</p><p class="is-size-6 is-flex justify-content-center"><i class="fas fa-map-marker-alt mr-1"></i><span>Overworld</span></p></div></div></nav><nav class="level is-mobile"><div class="level-item has-text-centered is-marginless"><div><p class="heading">文章</p><a href="/archives"><p class="title">5</p></a></div></div><div class="level-item has-text-centered is-marginless"><div><p class="heading">分类</p><a href="/categories"><p class="title">3</p></a></div></div><div class="level-item has-text-centered is-marginless"><div><p class="heading">标签</p><a href="/tags"><p class="title">2</p></a></div></div></nav><div class="level"><a class="level-item button is-primary is-rounded" href="https://github.com/timetraveler314" target="_blank" rel="noopener">关注我</a></div><div class="level is-mobile is-multiline"><a class="level-item button is-transparent is-marginless" target="_blank" rel="noopener" title="Github" href="https://github.com/timetraveler314"><i class="fab fa-github"></i></a><a class="level-item button is-transparent is-marginless" target="_blank" rel="noopener" title="Twitter" href="https://twitter.com"><i class="fab fa-twitter"></i></a></div></div></div><!--!--><div class="card widget" data-type="links"><div class="card-content"><div class="menu"><h3 class="menu-label">链接</h3><ul class="menu-list"><li><a class="level is-mobile" href="https://hexo.io" target="_blank" rel="noopener"><span class="level-left"><span class="level-item">Hexo</span></span><span class="level-right"><span class="level-item tag">hexo.io</span></span></a></li></ul></div></div></div><div class="card widget" data-type="categories"><div class="card-content"><div class="menu"><h3 class="menu-label">分类</h3><ul class="menu-list"><li><a class="level is-mobile" href="/categories/Calculus/"><span class="level-start"><span class="level-item">Calculus</span></span><span class="level-end"><span class="level-item tag">1</span></span></a></li><li><a class="level is-mobile" href="/categories/Functional-Programming/"><span class="level-start"><span class="level-item">Functional Programming</span></span><span class="level-end"><span class="level-item tag">2</span></span></a></li><li><a class="level is-mobile" href="/categories/Program-Calculation/"><span class="level-start"><span class="level-item">Program Calculation</span></span><span class="level-end"><span class="level-item tag">1</span></span></a></li></ul></div></div></div><div class="card widget" data-type="recent-posts"><div class="card-content"><h3 class="menu-label">最新文章</h3><article class="media"><div class="media-content"><p class="date"><time dateTime="2023-12-29T06:04:21.000Z">2023-12-29</time></p><p class="title"><a href="/2023/12/29/Program-Calculation-Fusion-and-Tupling/">Program Calculation: Fusion and Tupling</a></p><p class="categories"><a href="/categories/Program-Calculation/">Program Calculation</a></p></div></article><article class="media"><div class="media-content"><p class="date"><time dateTime="2023-11-04T13:36:22.000Z">2023-11-04</time></p><p class="title"><a href="/2023/11/04/Problems-on-Contiunity/">连续函数的几个问题！</a></p><p class="categories"><a href="/categories/Calculus/">Calculus</a></p></div></article><article class="media"><div class="media-content"><p class="date"><time dateTime="2023-11-04T05:31:45.000Z">2023-11-04</time></p><p class="title"><a href="/2023/11/04/Monadic-Parser/">Monadic Parser</a></p><p class="categories"><a href="/categories/Functional-Programming/">Functional Programming</a></p></div></article><article class="media"><div class="media-content"><p class="date"><time dateTime="2023-11-03T06:15:08.000Z">2023-11-03</time></p><p class="title"><a href="/2023/11/03/Foldable-and/">Foldable and ...</a></p><p class="categories"><a href="/categories/Functional-Programming/">Functional Programming</a></p></div></article><article class="media"><div class="media-content"><p class="date"><time dateTime="2023-11-03T03:36:20.694Z">2023-11-03</time></p><p class="title"><a href="/2023/11/03/hello-world/">Hello World</a></p></div></article></div></div><div class="card widget" data-type="archives"><div class="card-content"><div class="menu"><h3 class="menu-label">归档</h3><ul class="menu-list"><li><a class="level is-mobile" href="/archives/2023/"><span class="level-start"><span class="level-item">2023</span></span><span class="level-end"><span class="level-item tag">5</span></span></a></li></ul></div></div></div><div class="card widget" data-type="tags"><div class="card-content"><div class="menu"><h3 class="menu-label">标签</h3><div class="field is-grouped is-grouped-multiline"><div class="control"><a class="tags has-addons" href="/tags/Haskell/"><span class="tag">Haskell</span><span class="tag">2</span></a></div><div class="control"><a class="tags has-addons" href="/tags/Program-Calculation/"><span class="tag">Program Calculation</span><span class="tag">1</span></a></div></div></div></div></div></div><!--!--></div></div></section><footer class="footer"><div class="container"><div class="level"><div class="level-start"><a class="footer-logo is-block mb-2" href="/">Trivializer</a><p class="is-size-7"><span>© 2024 timetraveler314</span> Powered by <a href="https://hexo.io/" target="_blank" rel="noopener">Hexo</a> & <a href="https://github.com/ppoffice/hexo-theme-icarus" target="_blank" rel="noopener">Icarus</a></p><p class="is-size-7">© 2019</p></div><div class="level-end"><div class="field has-addons"><p class="control"><a class="button is-transparent is-large" target="_blank" rel="noopener" title="Creative Commons" href="https://creativecommons.org/"><i class="fab fa-creative-commons"></i></a></p><p class="control"><a class="button is-transparent is-large" target="_blank" rel="noopener" title="Attribution 4.0 International" href="https://creativecommons.org/licenses/by/4.0/"><i class="fab fa-creative-commons-by"></i></a></p><p class="control"><a class="button is-transparent is-large" target="_blank" rel="noopener" title="Download on GitHub" href="https://github.com/ppoffice/hexo-theme-icarus"><i class="fab fa-github"></i></a></p></div></div></div></div></footer><script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/jquery.min.js"></script><script src="https://cdn.jsdelivr.net/npm/[email protected]/min/moment-with-locales.min.js"></script><script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/clipboard.min.js" defer></script><script>moment.locale("zh-cn");</script><script>var IcarusThemeSettings = {
article: {
highlight: {
clipboard: true,
fold: 'unfolded'
}
}
};</script><script src="/js/column.js"></script><script src="/js/animation.js"></script><a id="back-to-top" title="回到顶端" href="javascript:;"><i class="fas fa-chevron-up"></i></a><script src="/js/back_to_top.js" defer></script><!--!--><!--!--><!--!--><script src="https://cdn.jsdelivr.net/npm/[email protected]/build/cookieconsent.min.js" defer></script><script>window.addEventListener("load", () => {
window.cookieconsent.initialise({
type: "info",
theme: "edgeless",
static: false,
position: "bottom-left",
content: {
message: "此网站使用Cookie来改善您的体验。",
dismiss: "知道了！",
allow: "允许使用Cookie",
deny: "拒绝",
link: "了解更多",
policy: "Cookie政策",
href: "https://www.cookiesandyou.com/",
},
palette: {
popup: {
background: "#edeff5",
text: "#838391"
},
button: {
background: "#4b81e8"
},
},
});
});</script><script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/js/lightgallery.min.js" defer></script><script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/js/jquery.justifiedGallery.min.js" defer></script><script>window.addEventListener("load", () => {
if (typeof $.fn.lightGallery === 'function') {
$('.article').lightGallery({ selector: '.gallery-item' });
}
if (typeof $.fn.justifiedGallery === 'function') {
if ($('.justified-gallery > p > .gallery-item').length) {
$('.justified-gallery > p > .gallery-item').unwrap();
}
$('.justified-gallery').justifiedGallery();
}
});</script><!--!--><!--!--><script type="text/x-mathjax-config">MathJax.Hub.Config({
'HTML-CSS': {
matchFontHeight: false
},
SVG: {
matchFontHeight: false
},
CommonHTML: {
matchFontHeight: false
},
tex2jax: {
inlineMath: [
['$','$'],
['\\(','\\)']
]
}
});</script><script src="https://cdn.jsdelivr.net/npm/[email protected]/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script><!--!--><!--!--><!--!--><script src="/js/main.js" defer></script><div class="searchbox"><div class="searchbox-container"><div class="searchbox-header"><div class="searchbox-input-container"><input class="searchbox-input" type="text" placeholder="想要查找什么..."></div><a class="searchbox-close" href="javascript:;">×</a></div><div class="searchbox-body"></div></div></div><script src="/js/insight.js" defer></script><script>document.addEventListener('DOMContentLoaded', function () {
loadInsight({"contentUrl":"/content.json"}, {"hint":"想要查找什么...","untitled":"(无标题)","posts":"文章","pages":"页面","categories":"分类","tags":"标签"});
});</script></body></html>