[Haskell-cafe] What is this applicative functor?

[Li-yao Xia]

Hello everyone,

For those interested in exploring the twisted functor approach,
the relevant product seems to be called "two-sided semidirect
product" in some circles.

This paper refers to some applications of the product in the
introduction (to study semigroups and monoids, with further
applications in formal language theory).
https://arxiv.org/abs/0709.2962

This paper introduced it.
At the bottom of page 39: (u, v)*(u', t') = (vt'+tv', tt').
http://www.sciencedirect.com/science/article/pii/0022404989901370

I haven't looked further.

Another idea: this product behaves like the product of
combinatorial species truncated at size 1 (and less).

Looking at generating functions, compare the first two coefficients
to the formula of the product above:

(t + vx)*(t' + v'x) = tt' + (vt' + tv') x + vv' x^2

For example, the shrinkings associated with a pair are obtained
by shrinking either component, but what about shrinking both?
By analogy with combinatorial species, we could say instead that
shrinking one component gives a "shrinking of order 1", and
shrinking both gives a "shrinking of order 2". More generally
the "shrinking order" of both components can be added together;
this indeed corresponds to the size of a combinatorial object.

IIRC the feat-testing package implements this structure.

What do you think?

Li-yao

On 02/01/2017 01:50 PM, Gershom B wrote:
> Indeed a very interesting type!
>
> In the spirit of the “twisting pointers” paper’s construction of applicative structure from semi-direct products [1], I would speculate that this is a form of applicative created from the _direct product_ of two underlying applicatives that share some sort of mutually distributive relationship… (in this case, identity and list), with one of the actions being trivial.
>
> Somethign that might be enlightening, again following twisted pointers, is to reformulate the Applicative Functor instance as a Monoidal Functor instance...
>
> [1] http://ozark.hendrix.edu/~yorgey/pub/twisted.pdf
>
> Cheers,
> Gershom
>
> On February 1, 2017 at 1:16:08 PM, Simon Jakobi via Haskell-Cafe (haskell-cafe at haskell.org) wrote:
>> Hi Joachim,
>>   
>> that's a very interesting type, thanks for sharing it!
>>   
>> Please note that in the rendering of the package description at
>> http://hackage.haskell.org/package/successors, the <*> is slightly
>> mangled.
>>   
>> Cheers,
>> Simon
>>   
>> 2017-02-01 18:39 GMT+01:00 Joachim Breitner :
>>> Hi,
>>>
>>> Am Mittwoch, den 01.02.2017, 10:33 -0500 schrieb Joachim Breitner:
>>>> Hi,
>>>>
>>>> David wrote:
>>>>> How about this?
>>>>>
>>>>> hd (OneStep x xs) = x
>>>>>
>>>>> instance Monad OneStep where
>>>>> OneStep x xs >>= f = OneStep y (map (hd . f) xs ++ ys)
>>>>> where
>>>>> OneStep y ys = f x
>>>>>
>>>>> Not sure if it’s good for anything, but it seems valid and consistent
>>>>> based on a preliminary investigation.
>>>>
>>>> Yes, this looks reasonable. Did you happen to already work through the
>>>> monad laws?
>>> Just did, all looks fine:
>>> https://github.com/nomeata/haskell-successors/blob/c1fd614cb0fc3e3b5dbf0338f835a91ea78e0b63/src/Control/Applicative/Successors.hs#L82
>>>
>>> Uploaded to http://hackage.haskell.org/package/successors in case
>>> someone wants to play with it.
>>>
>>> Greetings,
>>> Joachim
>>> --
>>> Joachim “nomeata” Breitner
>>> mail at joachim-breitner.de • https://www.joachim-breitner.de/
>>> XMPP: nomeata at joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F
>>> Debian Developer: nomeata at debian.org
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> To (un)subscribe, modify options or view archives go to:
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>> Only members subscribed via the mailman list are allowed to post.
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.