10000 SIP for adding co-monadic comprehensions · lashchenko/scala.github.com@dd1b86e · GitHub
[go: up one dir, main page]
Skip to content

Commit dd1b86e

Browse files
shimibshimib
committed
SIP for adding co-monadic comprehensions
1 parent bcef8df commit dd1b86e

File tree

1 file changed

+219
-0
lines changed

1 file changed

+219
-0
lines changed

‎sips/pending/_posts/2017-02-22-comonadic-comprehensions.md

Lines changed: 219 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,219 @@
1+
---
2+
layout: sip
3+
disqus: true
4+
title: SIP-NN - comonadic-comprehensions
5+
---
6+
7+
**By: Shimi Bandiel**
8+
9+
## History
10+
11+
| Date | Version |
12+
|---------------|---------------|
13+
| Feb 22nd 2017 | Initial Draft |
14+
15+
## Motivation
16+
17+
Scala provides a concise syntax for working with Monads(map & flatMap):
18+
the <b>for comprehension</b>.
19+
20+
Following is a proposal for a concise syntax for working with Comonads(map, extract & coflatMap):
21+
the <b>cofor comprehension</b>.
22+
23+
## Motivating Examples
24+
25+
### Examples
26+
27+
Consider the following class:
28+
29+
{% highlight scala %}
30+
31+
case class StreamZipper[A](left: Stream[A], focus: A, right: Stream[A]) {
32+
def map[B](f: A => B): StreamZipper[B] =
33+
StreamZipper(left.map(f), f(focus), right.map(f))
34+
def extract: A =
35+
focus
36+
def coflatMap(f: StreamZipper[A] => B): StreamZipper[B] =
37+
???
38+
}
39+
40+
{% endhighlight %}
41+
42+
<i>StreamZipper[A]</i> represents a <b>non-empty</b> Stream of <i>A</i>s with a cursor (focus).
43+
44+
<ul>
45+
<li>The <i>map</i> method invokes <i>f</i> on every element and produces a StreamZipper of
46+
the results.</li>
47+
<li>The <i>extract</i> method returns the value at the cursor</li>
48+
<li>The <i>coflatMap</i> method invokes <i>f</i> on every cursor (all possible zippers) providing a contextual global operation.
49+
The result is a StreamZipper[B] of the results with a cursor pointing at the same location as <i>this</i>.
50+
</li>
51+
</ul>
52+
53+
The above implementation for `coflatMap` was left out for brevity. See [3].
54+
55+
Now, consider the following methods:
56+
{% highlight scala %}
57+
58+
// returns whether the current cursor in a zipper of ints is between the previous
59+
// and the next numbers.
60+
def isInTheMiddle(z : StreamZipper[Int]): Boolean =
61+
z match {
62+
case StreamZipper(pi +: _, i, ni +: _) if (pi < i && i < ni) => true
63+
case _ => false
64+
}
65+
66+
// counts how many consecutive values of <i>true</i> starting from the cursor
67+
def numberOfTrues(z: StreamZipper[Boolean]) : Int =
68+
if (z.focus) 1 + z.right.takeWhile(true ==).size else 0
69+
70+
{% endhighlight %}
71+
72+
And, let's say we have a StreamZipper[Person]:
73+
{% highlight scala %}
74+
case class Person(name: String, age: Int)
75+
76+
// a given stream with cursor at some position
77+
val people: StreamZipper[Person] = ???
78+
{% endhighlight %}
79+
80+
We would like to get the following:
81+
{% highlight scala %}
82+
83+
/*
84+
* A StreamZipper of triplets containing:
85+
* _1 -- the original Person value.
86+
* _2 -- whether this Person's age is higher than the previous and lower than the next.
87+
* We'll call this boolean TAG.
88+
* _3 -- how many consecutive TAGs with value "true" starting from current cursor.
89+
*/
90+
val goal: StreamZipper[(Person, Boolean, Int)] = ???
91+
92+
{% endhighlight %}
93+
94+
It seems we can re-use the <i>isInTheMiddle</i> and <i>numberOfTrues</i> methods.
95+
However, <b>without the proposed cofor</b> syntax we'll probably end with:
96+
{% highlight scala %}
97+
val goal = people.map(p => (p, p.age)).coflatMap { zipperOfTuple =>
98+
val ages = zipperOfTuple.map(_._2)
99+
(zipperOfTuple.extract._1, isInTheMiddle(ages))
100+
}.coflatMap { zipperOfTuple =>
101+
val tags = zipperOfTuple.map(_._2)
102+
val persons = zipperOfTuple.map(_._1)
103+
val trues = numberOfTrues(tags)
104+
persons.extract, tags.extract, trues)
105+
}
106+
{% endhighlight %}
107+
From the code above, you can see that it is quite cumbersome to handle the passing of
108+
the <i>context</i> between the invocations of <i>coflatMap</i>.
109+
110+
The proposed syntax allows for the following usage:
111+
{% highlight scala %}
112+
val flow : StreamZipper[Person] => (Person, Boolean, Int) =
113+
cofor (p @ Person(_, age)) {
114+
tag <- isInTheMiddle(age)
115+
count <- numberOfTrues(tag)
116+
} yield (p.extract, tag.extract, count.extract)
117+
118+
val goal = people.coflatMap(flow)
119+
{% endhighlight %}
120+
121+
122+
## Syntax
123+
124+
The proposed syntax is based on the paper by Dominic Orchard and Alan Mycroft [1].
125+
126+
The syntax for `cofor` is defined as:
127+
{% highlight scala %}
128+
cofor (pattern0) {
129+
pattern1 <- generator1
130+
pattern2 <- generator2
131+
...
132+
} yield body
133+
134+
patternN = regular case patterns
135+
generatorN = expr
136+
body = expr
137+
138+
{% endhighlight %}
139+
140+
The result type of a `cofor` expression is a function from the comonad type to
141+
a result (`T[A] => B`).
142+
This means that the return type must be available at call-site!
143+
Note that unlike `for`, guards and assignments are not supported.
144+
145+
## Desugaring
146+
147+
A `cofor` desugaring is much more complex than the respective `for`.
148+
149+
Desugaring example:
150+
151+
{% highlight scala %}
152+
val flow : StreamZipper[Person] => (Person, Boolean, Int) =
153+
cofor (p @ Person(_, age)) {
154+
tag <- isInTheMiddle(age)
155+
count <- numberOfTrues(tag)
156+
} yield (p.extract, tag.extract, count.extract)
157+
158+
val goal = people.coflatMap(flow)
159+
{% endhighlight %}
160+
161+
The above `cofor` expression will be desugared into the following function:
162+
{% highlight scala %}
163+
input => {
164+
// desugaring the generators
165+
val enums =
166+
// assign values to input variables
167+
// actual assignment is done through pattern matching
168+
input.map(p => (
169+
p match {
170+
case p @ Person(_, age) => p
171+
}
172+
, (p match {
173+
case p @ Person(_, age) => age
174+
}, ()))).
175+
coflatMap(env => {
176+
// extracting collected values from the context
177+
val p = env.map(env => env._1)
178+
val age = env.map(env => env._2._1)
179+
// now we pass the current context and the generator result
180+
(isInTheMiddle(age), env.extract)
181+
}).coflatMap(env => {
182+
// extracting collected values from the context
183+
val tag = env.map(env => env._1)
184+
val p = env.map(env => env._2._1)
185+
val age = env.map(env => env._2._2._1)
186+
// now we pass the current context and the generator result
187+
(numberOfTrues(tag), env.extract)
188+
})
189+
// the body phase (yield)
190+
{
191+
// deconstructing the collected context
192+
val count = enums.map(env => env._1)
193+
val tag = enums.map(env => env._2._1)
194+
val p = enums.map(env => env._2._2._1)
195+
val age = enums.map(env => env._2._2._2._1)
196+
(p.extract, tag.extract, count.extract)
197+
}
198+
}
199+
{% endhighlight %}
200+
201+
## Drawbacks
202+
203+
<ol>
204+
<li>Adding a new keyword to the language makes it more complex</li>
205+
<li>Understanding the desugaring and concept behind <i>cofor</i> is not
206+
trivial and it's much more complex than <i>for</i> (which many developers still
207+
don't feel at ease with).</li>
208+
</ol>
209+
210+
211+
## References
212+
213+
1. [A Notation for Comonads][1]
214+
2. [Implementation Pull-Request][2]
215+
3. [StreamZipper Example][3]
216+
217+
[1]: https://www.cl.cam.ac.uk/~dao29/publ/codo-notation-orchard-ifl12.pdf "codo-notation"
218+
[2]: https://github.com/scala/scala/pull/5725
219+
[3]: https://github.com/shimib/scala/blob/5e257cd4b371769deafba2be1ae3932d772ca67d/test/files/neg/cofor.scala

0 commit comments

Comments
 (0)
0