Junctions, patterns, and fmap again
Luke Palmer
fmap proposal was Warnocked is because a fair number of people didn't
understand it. Also, for the people who did understand, this message
includes a complete proposal for the workings of Junctions that will
fluster Damian again. :-)
Part 1: fmap
De-symmetricalize hyper. So, what used to be @foo »+« 1 is now @foo
»+ 1; the hyper marker is only on the side of the operator that is
being hypered over. Of course, we still have @foo »+« @bar.
An object may do the role[1] Functor, in which case it defines a
method 'fmap' which is a generalization of map. For instance, let's
try it with a tree.
class Tree does Functor {
method fmap (&code) {...}
}
class Branch is Tree {
has Tree $.left;
has Tree $.right;
method fmap (&code) {
# Return an identical tree with the leaves mapped with &code
return Branch.new(
left => $.left.fmap(&code),
right => $.right.fmap(&code),
);
}
}
class Leaf is Tree {
has $.data;
method fmap (&code) {
# Just apply &code to the value in the leaf
return Leaf.new( data => &code($.data) )
}
}
Now if we have a $tree that looks like:
+---+---3
| +---4
+---5
$tree.fmap:{ $_ * 2 } returns:
+---+---6
| +---8
+---10
The formal signature of fmap is, if T is a Functor:
multi fmap (T[::U], &code:(::U --> ::V) --> T[::V])
That is, it takes a T of some type, and a code that maps some type to
some other type, and returns a T of that other type.
Now, hypers are just syntactic sugar for various forms of fmap:
$x »+ $y # $x.fmap:{ $_ + $y }
$x +« $y # $y.fmap:{ $x + $_ }
foo(»$x«) # $x.fmap:{ foo($_) }
I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
but I don't want to go into that right now. It basically involves
zipping the structures up into tuples and applying the function to the
tuples.
Part 2: Junctions
A Junction is a set of values together with a logical operation to be
applied when the Junction is in boolean context. When you add to a
Junction, you add to each of its values. When you pass a Junction to
a function, you call the function for each of its values and
reconstruct based on the return values. All in all, a Junction sounds
like a perfect candidate to be a Functor. Except all the fmapping is
implicit, which is what makes Junctions break the transitivity of <,
the orthogonality of the patterns "1" and "2", and all that other
stuff that people like me covet so.
So my proposal is to make a Junction into a plain old Functor. So
what used to be:
if any(@values) == 4 {...}
Is now:
if any(@values) »== 4 {...}
And the only thing that makes junctions different from Sets (which are
also Functors) is their behavior in boolean context (and their ability
to be Patterns; see below).
Yeah, it's a little teeny bit longer, but I think it is pretty easy to
get used to. And now junctinve threading looks like threading (just
like with hypers). The best part is that now it is okay to pass
Junctions to functions since they don't screw with your logical
assumptions, and the signature (Junction $x) is no longer semantically
special; it is a type check just like any other typed signature (and
optional just like any other typed signature :-).
Part 3: Patterns
Like I've said before, a Pattern is a thing that can be on the right
side of a ~~ operator. Most builtin things are Patterns: numbers,
strings, regexes, lists (maybe), booleans, closures, classes, and
junctions. Pattern is really a role[2] that requires a match(Any -->
Bool). So then $x ~~ $y is equivalent to $y.match($x).
Here is a table of standard Patterns:
numbers, strings: eqv
regexes: match (note this gives us /foo/.match($str) for free)
lists: dunno
booleans: boolean truth (ignores left side)
closures: apply closure and test truth
classes: .does
junctions: see below
A Junction of Patterns does Pattern under its logical operation. So
$x ~~ any($y,$z) is equivalent to $x ~~ $y || $x ~~ $z. This is the
only autothreading operation. And that is so you can say:
given $value {
when 1 | 2 | 3 {...}
when /^foo/ | /^bar/ {...}
}
The signature of grep is:
sub grep (Pattern $pat, *@values) {...}
So then these all make sense:
grep /foo/, @values;
grep 1|2, @values;
grep Node, @objects
And the regular closure form of grep is only for straight boolean
tests against the argument:
grep { lc eq 'foo' } @strings;
This really doesn't give us anything new. But in my opinion, it
solidifies what we already have greatly, and makes it much easier to
think about and work with (no more guessing :-). It also trivializes
the smart match table in S04.
Luke
[1] Really a theory. For more about the incomplete theory proposal,
read http://svn.openfoundry.org/pugs/docs/notes/model_theory.
[2] Really a role. As a note that I haven't documented yet: the
definition of a role in Theory theory is:
A theory R is a role if for all types T and U, R[U] and T does U implies R[T].
Stuart Cook
> Part 1: fmap
>
> I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
> but I don't want to go into that right now. It basically involves
> zipping the structures up into tuples and applying the function to the
> tuples.
Does this mean that 'unary' (one-side) hyper would be
structure-preserving, but 'binary' (two-side) hyper would not? Or
would you take the final list of tuples and re-build a structure?
I guess it comes down to whether you want to allow binary-hyper on
values that aren't structurally equivalent. Either you flatten both
structures to lists (which might be semantically dubious), or you
disallow binary-hyper on structurally distinct arguments (which might
prohibit some useful operations). Or you do something inconsistent.
(Have you written any of these deep details up somewhere? I'd love to
read them.)
> Part 2: Junctions
>
> So my proposal is to make a Junction into a plain old Functor. So
> what used to be:
>
> if any(@values) == 4 {...}
>
> Is now:
>
> if any(@values) »== 4 {...}
>
> And the only thing that makes junctions different from Sets (which are
> also Functors) is their behavior in boolean context (and their ability
> to be Patterns; see below).
I think this is really nice: we get rid of invisible junction magic,
yet accessing that magic explicitly is only one or two characters
away. Being able to pass junctions around as values (safely) is a nice
bonus too.
Stuart
Luke Palmer
> On 19/09/05, Luke Palmer <lrpa...@gmail.com> wrote:
> > Part 1: fmap
> >
> > I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
> > but I don't want to go into that right now. It basically involves
> > zipping the structures up into tuples and applying the function to the
> > tuples.
>
> Does this mean that 'unary' (one-side) hyper would be
> structure-preserving, but 'binary' (two-side) hyper would not? Or
> would you take the final list of tuples and re-build a structure?
Well, I've written up the details in a 40 line Haskell program to make
sure it worked. I think I deleted the program, though.
The basic idea is that, alongside Functor, you have a Zippable theory
which defines:
theory Zippable[::T] {
multi zip (T[::A], T[::B] --> T[:(::A, ::B)]) {...}
}
Where that last coloney madness is a yet-to-be-proposed tuple type
(but tuples can be emulated if they are not in the core language, so
it's no biggie). That is, zip takes two structures and figures out
how to combine them in a reasonable way into pairs of values. So:
zip([1,2,[3,4]], [["a","b"], "c", "d"])
Gives:
[[:(1,"a"), :(1,"b")], :(2,"c"), [:(3,"d"), :(4,"d")]]
In order to be consistent with the specced semantics. In order to
keep with the specced semantics of junctions, you'll probably see:
zip(1|2, 3&4)
Give:
(:(1,3) & :(1,4)) | (:(2,3) & :(2,4))
So it's really up to the zippable functor itself to figure out the
best way to zip. After the structures are zipped up, you fmap the
binary function on each of the tuples, resulting in a reasonable
functor structure again.
Hmmm, that should probably be fzip or something.
Luke
Luke Palmer
> Well, I've written up the details in a 40 line Haskell program to make
> sure it worked. I think I deleted the program, though.
Nope. Here it is. And it was 22 lines. :-)
http://svn.luqui.org/svn/misc/luke/work/code/haskell/hyper.hs
Luke
Stuart Cook
> The basic idea is that, alongside Functor, you have a Zippable theory
> which defines:
>
> theory Zippable[::T] {
> multi zip (T[::A], T[::B] --> T[:(::A, ::B)]) {...}
> }
>
> Where that last coloney madness is a yet-to-be-proposed tuple type
> (but tuples can be emulated if they are not in the core language, so
> it's no biggie). That is, zip takes two structures and figures out
> how to combine them in a reasonable way into pairs of values. So:
>
> zip([1,2,[3,4]], [["a","b"], "c", "d"])
>
> Gives:
>
> [[:(1,"a"), :(1,"b")], :(2,"c"), [:(3,"d"), :(4,"d")]]
Oh, looks like I was way off. So in this particular scenario, when one
side 'runs out' of structure, that part degenerates to a one-side fmap
using the leaf value as the non-hyper arg.
Of course, this is the behaviour for /built-in/ arrays--it's up to the
person defining &fzip to determine how to handle their own Zippable
types. So, if they want &fzip to fail() on incompatible structures, or
do some other crazy thing, they can just put that in their version of
&fzip.
> So it's really up to the zippable functor itself to figure out the
> best way to zip. After the structures are zipped up, you fmap the
> binary function on each of the tuples, resulting in a reasonable
> functor structure again.
Bottom line: user-defined &fzip turns two structures into one
structure of pairs (in whatever way the user deems reasonable), and
then &fmap transforms the tuples of that one structure.
For things like `foo(»$x«, »$y«, »$z«)` (assuming it ends up being
supported), you would either extend &fzip over n-tuples, or just use
pair-fzip repeatedly and reduce the nested pairs into a single
n-tuple.
> Nope. Here it is. And it was 22 lines. :-)
>
> http://svn.luqui.org/svn/misc/luke/work/code/haskell/hyper.hs
Thanks, that made it a lot clearer. Haskell++ :)
I just hope you and I aren't the only ones who think this is a great idea...
Stuart