develooper Front page | perl.perl6.language | Postings from September 2005

Junctions, patterns, and fmap again

Thread Next
From:
Luke Palmer
Date:
September 18, 2005 21:36
Subject:
Junctions, patterns, and fmap again
Message ID:
7ca3f016050918213647d97125@mail.gmail.com
Okay, due to some discussion on #perl6, I'll assume that the reason my
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].

Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About