On Aug 31, 2006, at 11:11 PM, skaller wrote:
> A list of categorical combinators requires knowing
> some universal algebra .. not Felix.
>
> I want Felix to model category theory as is possible,
> since I have faith in it to deliver good stuff:
> it is, after all, the mathematics of the extremely trival
> designed for pedants and programmers.
>
> I have a book with some common constructions in it,
> but there are a lot of them, and programmers need a
> different set to that required by mathematicians,
> even category theorists: there won't be
> a special notation for something not used a lot,
> but programmer use things frequently that mathematicians
> do not.
>
> Composition, for all its merits, is rarely used in practice.
Composition? Really? I use composition all the time: composition is
very simply the ability to take several simple programmatic
definitions (operations) and put them together to define something
more complex. Syntactic sugar it may be, but it does help operate
with functions at a higher level. <,> is useful but not used nearly
as much as the more general Composition because <,> only has real
meaning over certain types (those that are essentially distributable
operations).
By the way, I had been following your description of the operation
mindlessly and only now realised that:
<f,g> . <h,j> = <f . h, g . j>
is distributive, not commutative. So from now on I am going to call
it the Distribution operator.
This might be a commutative operator (it flips the application of two
functions, although I don't think it would be very useful except as
syntactic sugar--the "flip" function that reverses the order of
arguments to a function *is* useful):
(f <-> g) = g . f
where the normal order of composition is:
f . g = (f (g x))
so
a <-> b <-> c = c . b . a
--The big difference here is, since the _definition_ of the (<->)
operator is stated in terms of the normal-order (.) operator the
functions commuted would have to be commutative! To be commutative
the functions must all have the same input and output types:
fun commute[T] (f:T->T, g:T->T) => f . g ;
>>> The HARD part is every such 'executable' expression has a
>>> corresponding typing .. the type terms ALSO have to be
>>> combined.
>>
>> Even after reading the rest of your message, I still don't understand
>> the problem. The operator is executable, so it has the type:
>>
>> <,>:( a -> b) -> (c -> d) -> (b, d)
>
> It's only a binary operator. Show me a definition that
> works for n arguments .. without knowing n in advance.
>
> For composition
>
> a . b . c . d
>
> works because composition is associative. But tuples are not.
> So you don't have
>
> <a,b,c> = <<a,b>,c>
>
> but you DO have
>
> a . b . c = (a.b).c = a.(b.c)
>
> Remember most category theory, the theory of total pedantry,
> actually says 'up to isomorphism' a lot. Tuple formation and
> hence <..> operator isn't associative: that requires equality,
> not just isomorphism.
Composition is associative not as a property of the composition
operator but as a property of function application. Since function
application is generally outermost first (in Felix and most
functional languages this is typically leftmost first), as:
f a b c d = ((((f a) b) c) d). <--(f a) executes first
So it is not the composition operator but the function application
operator () that is creating the associativity. (I am not sure
(a . b) . c
would be meaningfully different from
a . b . c
in Felix unless you enclosed
a . b
in curly braces { }, creating a lazy evaluation, and *that* would
only be meaningful if the lazy evaluation operated in a different
order than normal function application, as in:
a . { b . c } . d
so b . c would execute out of the normal order:
(a ((b) c) d)
so you could obtain the result of b . c separately from the other
composed functions.
Anyway, here is the problem with the Distribution operator as I
understand it (not to be pedantic but because I am probably too
stupid to grasp what you mean). The Distribution operator may
operate differently over different numbers of arguments:
<a, b, c> . <x, y, z> =
(1) < (a . x), (b . y), (c . z) >
OR
(2) < ((a . x),(b . y)), (c . z) > ??
(I hope these diagrams are readable). This seems to be the problem
you are describing, correct?
There are two possible solutions:
(a) in general, since this <,> operator is a function that performs
an operation with a particular _property_, just as operator= in C++
has one of the related properties of copying or assigning values, the
"Commutation" operator should have a default operation of (1) above
(simple distribution);
(b) the programmer should be required to define the operation of the
Commutation operator over a new type
As a practical note, how are you implementing these operators? Are
you laboriously going through and building them into the parser or
are you able to define them at a higher level somehow?
> METATYPE
>
> so we can always reduce things to a uniform state by
> going high enough up in the kinding system :)
Amazing! Thanks for the great explanation! You might partly
understand why I was concerned about a new operator, however. Since
the operator <,> has a new property (really, the distributive
property), shouldn't it have a completely new METATYPE, I mean,
beyond a type function?
Incidentally, to force the operator itself to be distributive, its
definition over a function should probably be:
<,> (f,g) = <,> . <f,g> . <,>
following the simple definition of distribution:
<f,g> . <h,i> = <<f . h>,<g . i>>
and the law that:
f . = f . id = f
You may already see how this operation unfolds:
<,> . <f,g> . <,> = <,> . <<f . >,<g . >> = <,> . <f,g> = << . f>,< .
g>> = <f,g>
<,> . <f,g> . <,> (h,i) = <,> . <f,g> . <,> . <,> . <h,i> . <,> =
[after reduction] <f . h, g . i>
-Pete
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
