高效Haskell Functional Reactive Programming 实现探析
5星 · 超过95%的资源 需积分: 9 8 浏览量
更新于2024-09-16
1
收藏 285KB PDF 举报 "本文探讨了Haskell中的函数式反应编程（FRP）以及如何改进其实现。作者Conal Elliott提出了结合数据驱动和需求驱动评估的新方法，以解决传统FRP实现中值的无效重新计算和高反应延迟问题。"
在函数式反应编程（Functional Reactive Programming, FRP）中，其核心概念是将时间变化视为连续的，使得程序员能够以声明式的方式处理实时或响应式系统。Haskell作为纯函数式语言，非常适合表达这种抽象。然而，以往的FRP实现通常采用需求驱动的采样策略，虽然适应了连续时间语义，但存在两个主要问题：一是即使输入没有改变，值也会被不必要的重新计算，导致资源浪费；二是由于采样周期，反应延迟可能很高。
论文中，Conal Elliott提出了一种新的FRP形式化方法，它结合了数据驱动和需求驱动的评估策略。在这种方法中，值只在必要时进行重新计算，从而减少了无谓的工作，并且能够近乎即时地做出反应。这一改进的关键在于找到了一种平衡，既保持了FRP的时间连续性，又避免了不必要计算的开销。
为了实现这一新策略，作者引入了一些既有和新的概念：
1. **Monoids**：这是函数式编程中的基本构造，用于定义可组合的运算。在FRP中，monoids可以用来合并或累加事件。
2. **Functors, Applicative Functors, Monads**：这些是Haskell中的类型类，提供了操作和组合函数的抽象。它们在FRP中用于封装和操纵计算过程，确保了纯函数式的性质。
3. **Morphisms**：函数或映射，它们在不同结构之间转换数据，保持了FRP的数学一致性。
4. **Improving Values**：随着时间推移不断改善的值，反映了FRP中时间的连续性。
5. **Functional Future Values**：这是论文中提出的一个新概念，可能指的是与未来事件相关的值，可以提前计算而不会过早触发反应。
6. **Reactive Normal Form**：这可能是FRP表达式的规范化形式，旨在简化计算并优化性能。
7. **Concurrent “Unambiguous Choice”**：在并发环境中，无歧义选择可能指的是一种能清晰、确定地处理多个并发事件的机制，避免了冲突和不确定性。
通过这些工具和概念，新的FRP实现提高了效率和响应性，为开发者提供了更强大的工具来构建实时和响应式应用。这种方法不仅降低了计算的开销，而且提高了系统的实时性能，使得Haskell作为FRP平台的吸引力进一步增强。对于那些对函数式编程和反应式系统感兴趣的开发者来说，这篇论文提供了深入理解和改进FRP实现的重要洞察。
liftA
3
:: Applicative f ⇒ (a → b → c → d)
→ f a → f b → f c → f d
liftA
3
f a b c = liftA
2
f a b <∗> c
...
The left-associative (<$>) is just a synonym for fmap—a stylistic
preference—while liftA
2
, liftA
3
, etc. are generalizations of the
monadic combinators liftM
2
, liftM
3
, etc.
CFRP’s lift
0
corresponds to pure, while lift
2
, lift
3
, etc corre-
spond to liftA
2
, liftA
3
, etc., so the Applicative instance replaces
all of the lift
n
.
4
Functions, and hence B, form an applicative functor, where
pure and (<∗>) correspond to the classic K and S combinators:
instance Applicative ((→) t) where
pure = const
f <∗> g = λt → (f t) (g t )
The Applicative instance for functions leads to the semantics
of the Behavior instance of Applicative. As with Functor above,
the semantic function distributes over the class methods, i.e., at is
an applicative functor morphism:
instance
sem
Applicative Behavior where
at (pure a) = pure a
= const a
at (b
f
<∗> b
x
) = at b
f
<∗> at b
x
= λt → (b
f
‘at‘ t) (b
x
‘at‘ t)
So, given a function-valued behavior b
f
and an argument-valued
behavior b
x
, to sample b
f
<∗> b
x
at time t, sample b
f
and b
x
at t
and apply one result to the other.
This (<∗>) operator is the heart of FRP’s concurrency model,
which is semantically determinate, synchronous, and continuous.
2.1.3 Monad
Although Behavior is a semantic Monad as well, the implemen-
tation developed in Section 5 does not implement Monad .
2.2 Events
Like behaviors, much of the event functionality can be packaged
via standard type classes.
2.2.1 Monoid
Classic FRP had a never-occurring event and an operator to merge
two events. Together, these combinators form a monoid, so ∅ and
(⊕) (Haskell’s mempty and mappend) replace the CFRP names
neverE and (.|.).
The event monoid differs from the list monoid in that (⊕) must
preserve temporal monotonicity.
instance
sem
Monoid (Event a) where
occs ∅ = [ ]
occs (e ⊕ e
0
) = occs e ‘merge‘ occs e
0
Temporal merging ensures a time-ordered result and has a left-bias
in the case of simultaneity:
merge :: E
a
→ E
a
→ E
a
[ ] ‘merge‘ vs = vs
us ‘merge‘ [ ] = us
((
ˆ
t
a
, a) : ps) ‘merge‘ ((
ˆ
t
b
, b) : qs)
|
ˆ
t
a
6
ˆ
t
b
= (
ˆ
t
a
, a) : (ps ‘merge‘ ((
ˆ
t
b
, b) : qs))
| otherwise = (
ˆ
t
b
, b) : (((
ˆ
t
a
, a) : ps) ‘merge‘ qs)
Note that occurrence lists may be infinitely long.
4
The formulation of the lift
n
in terms of operators corresponding to pure
and (<∗>) was noted in (Elliott 1998a, Section 2.1).
2.2.2 Functor
Mapping a function over an event affects just the occurrence values,
leaving the times unchanged.
instance
sem
Functor Event where
occs (fmap f e) = map (λ(
ˆ
t
a
, a) → (
ˆ
t
a
, f a)) (occs e)
2.2.3 Monad
Previous FRP definitions and implementations did not have a
monad instance for events. Such an instance, however, is very
useful for dynamically-generated events. For example, consider
playing Asteroids and tracking collisions. Each collision can break
an asteroid into more of them (or none), each of which has to be
tracked for more collisions. Another example is a chat room hav-
ing an enter event whose occurrences contain new events like speak
(for the newly entered user).
A unit event has one occurrence, which is always available:
occs (return a) = [(−∞, a)]
The join operation collapses an event-valued event ee:
join
E
:: Event (Event a) → Event a
Each occurrence of ee delivers a new event, all of which get merged
together into a single event.
occs (join
E
ee) =
foldr merge [ ] ◦ map delayOccs ◦ occs ee
delayOccs :: (
b
T , Event a) → E
a
delayOccs (
ˆ
t
e
, e) = [(
ˆ
t
e
‘max ‘
ˆ
t
a
, a) | (
ˆ
t
a
, a) ← occs e ]
Here, delayOccs ensures that inner events cannot occur before they
are generated.
This definition of occs hides a subtle problem. If ee has in-
finitely many non-empty occurrences, then the foldr , if taken as
an implementation, would have to compare the first occurrences of
infinitely many events to see which is the earliest. However, none
of the occurrences in delayOccs (
ˆ
t
e
, e) can occur before time
ˆ
t
e
, and the delayOccs applications are given monotonically non-
decreasing times. So, only a finite prefix of the events generated
from ee need be compared at a time.
2.2.4 Applicative functor
Any monad can be made into an applicative functor, by defining
pure = return and (<∗>) = ap. However, this Applicative
instance is unlikely to be very useful for Event. Consider function-
and argument-valued events e
f
and e
x
. The event e
f
<∗> e
x
would
be equivalent to e
f
‘ap‘ e
x
and hence to
e
f
>>= λf → e
x
>>= λx → return (f x )
or more simply
e
f
>>= λf → fmap f e
x
The resulting event contains occurrences for every pair of occur-
rences of e
f
and e
x
, i.e., (
ˆ
t
f
‘max ‘
ˆ
t
x
, f x ) for each (
ˆ
t
f
, f ) ∈
occs e
f
and (
ˆ
t
x
, x ) ∈ occs e
x
. If there are m occurrences of e
f
and n occurrences of e
x
, then there will m × n occurrences of
e
f
<∗> e
x
. Since the maximum of two values is one value or the
other, there are at most m +n distinct values of
ˆ
t
f
‘max ‘
ˆ
t
x
. Hence
the m × n occurrences must all occur in at most m + n tempo-
rally distinct clusters. Alternatively, one could give a relative time
semantics by using (+) in place of max .
2.3 Combining behaviors and events
FRP’s basic tool for introducing reactivity combines a behavior and
and an event.
剩余11页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2018-06-28 上传
2021-06-08 上传
201 浏览量
2021-05-22 上传
2021-05-07 上传
fiberbundle
- 粉丝: 0
我的内容管理
展开
最新资源
- 支付宝订单监控免签工具：实时监控与信息通知
- 一键永久删除QQ空间说说的绿色软件
- Appleseeds训练营第4周JavaScript练习
- 免费HTML转CHM工具：将网页文档化简成章
- 奇热剧集站SEO优化模板下载
- Python xlrd库：实用指南与Excel文件读取
- Genegraph：通过GraphQL API使用Apache Jena展示RDF基因数据
- CRRedist2008与CRRedist2005压缩包文件对比分析
- SDB交流伺服驱动系统选型指南与性能解析
- Android平台简易PDF阅读器的实现与应用
- Mybatis实现数据库物理分页的插件源码解析
- Docker Swarm实例解析与操作指南
- iOS平台GTMBase64文件的使用及解密
- 实现jQuery自定义右键菜单的代码示例
- PDF处理必备：掌握pdfbox与fontbox jar包
- Java推箱子游戏完整源代码分享
