What is this applicative functor?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

What is this applicative functor?

Joachim Breitner-2
Hi,

I recently wrote this applicative functor:

    data OneStep a = OneStep a [a]

    instance Functor OneStep where
        fmap f (OneStep o s) = OneStep (f o) (map f s)

    instance Applicative OneStep where
        pure x = OneStep x []
        OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs ++ map f xs)

    takeOneStep :: OneStep t -> [t]
    takeOneStep (OneStep _ xs) = xs

This was useful in the context of writing a shrink for QuickCheck, as
discussed at http://stackoverflow.com/a/41944525/946226.

Now I wonder: Does this functor have a proper name? Does it already
exist in the libraries somewhere? Should it?

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Christopher Allen
NonEmpty?

On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner
<[hidden email]> wrote:

> Hi,
>
> I recently wrote this applicative functor:
>
>     data OneStep a = OneStep a [a]
>
>     instance Functor OneStep where
>         fmap f (OneStep o s) = OneStep (f o) (map f s)
>
>     instance Applicative OneStep where
>         pure x = OneStep x []
>         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs ++ map f xs)
>
>     takeOneStep :: OneStep t -> [t]
>     takeOneStep (OneStep _ xs) = xs
>
> This was useful in the context of writing a shrink for QuickCheck, as
> discussed at http://stackoverflow.com/a/41944525/946226.
>
> Now I wonder: Does this functor have a proper name? Does it already
> exist in the libraries somewhere? Should it?
>
> Greetings,
> Joachim
>
> --
> Joachim “nomeata” Breitner
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
> _______________________________________________
> 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.



--
Chris Allen
Currently working on http://haskellbook.com
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Joachim Breitner-2
Hi,

good idea, but no. The datatypes are superficially equivalent, but the
Applicative instance differs:

With NonEmpty’s instance:

> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
(0,3) :| [(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]

with my instance:

> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
(0,3) :| [(1,3),(2,3),(0,4),(0,5)]

Greetings,
Joachim

Am Dienstag, den 31.01.2017, 14:24 -0600 schrieb Christopher Allen:

> NonEmpty?
>
> On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner
> <[hidden email]> wrote:
> > Hi,
> >
> > I recently wrote this applicative functor:
> >
> >     data OneStep a = OneStep a [a]
> >
> >     instance Functor OneStep where
> >         fmap f (OneStep o s) = OneStep (f o) (map f s)
> >
> >     instance Applicative OneStep where
> >         pure x = OneStep x []
> >         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs
> > ++ map f xs)
> >
> >     takeOneStep :: OneStep t -> [t]
> >     takeOneStep (OneStep _ xs) = xs
> >
> > This was useful in the context of writing a shrink for QuickCheck,
> > as
> > discussed at http://stackoverflow.com/a/41944525/946226.
> >
> > Now I wonder: Does this functor have a proper name? Does it already
> > exist in the libraries somewhere? Should it?
> >
> > Greetings,
> > Joachim
> >
> > --
> > Joachim “nomeata” Breitner
> >   [hidden email]https://www.joachim-breitner.de/
> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
> >   Debian Developer: [hidden email]
> > _______________________________________________
> > 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.
>
>
>
--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Christopher Allen
Ah right, I didn't stare hard enough at the Applicative.

If I squint a bit at the results of your Applicative instance it seems
similar to the difference between []'s Applicative and the ZipList
Applicative, except a little crossed up. Sure you already identified
that, sorry I don't have more to offer here.

On Tue, Jan 31, 2017 at 2:36 PM, Joachim Breitner
<[hidden email]> wrote:

> Hi,
>
> good idea, but no. The datatypes are superficially equivalent, but the
> Applicative instance differs:
>
> With NonEmpty’s instance:
>
>> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
> (0,3) :| [(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]
>
> with my instance:
>
>> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
> (0,3) :| [(1,3),(2,3),(0,4),(0,5)]
>
> Greetings,
> Joachim
>
> Am Dienstag, den 31.01.2017, 14:24 -0600 schrieb Christopher Allen:
>> NonEmpty?
>>
>> On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner
>> <[hidden email]> wrote:
>> > Hi,
>> >
>> > I recently wrote this applicative functor:
>> >
>> >     data OneStep a = OneStep a [a]
>> >
>> >     instance Functor OneStep where
>> >         fmap f (OneStep o s) = OneStep (f o) (map f s)
>> >
>> >     instance Applicative OneStep where
>> >         pure x = OneStep x []
>> >         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs
>> > ++ map f xs)
>> >
>> >     takeOneStep :: OneStep t -> [t]
>> >     takeOneStep (OneStep _ xs) = xs
>> >
>> > This was useful in the context of writing a shrink for QuickCheck,
>> > as
>> > discussed at http://stackoverflow.com/a/41944525/946226.
>> >
>> > Now I wonder: Does this functor have a proper name? Does it already
>> > exist in the libraries somewhere? Should it?
>> >
>> > Greetings,
>> > Joachim
>> >
>> > --
>> > Joachim “nomeata” Breitner
>> >   [hidden email]https://www.joachim-breitner.de/
>> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>> >   Debian Developer: [hidden email]
>> > _______________________________________________
>> > 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.
>>
>>
>>
> --
> Joachim “nomeata” Breitner
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
>
> _______________________________________________
> 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.



--
Chris Allen
Currently working on http://haskellbook.com
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Matt
Interestingly, neither NEL nor OneStep behave the same as `Product Identity []`:

λ> let a = Pair (Identity 0) [1,2]
λ> let b = Pair (Identity 3) [4,5]
λ> (,) <$> a <*> b
Pair (Identity (0,3)) [(1,4),(1,5),(2,4),(2,5)]

So many applicatives!

Matt Parsons

On Tue, Jan 31, 2017 at 3:41 PM, Christopher Allen <[hidden email]> wrote:
Ah right, I didn't stare hard enough at the Applicative.

If I squint a bit at the results of your Applicative instance it seems
similar to the difference between []'s Applicative and the ZipList
Applicative, except a little crossed up. Sure you already identified
that, sorry I don't have more to offer here.

On Tue, Jan 31, 2017 at 2:36 PM, Joachim Breitner
<[hidden email]> wrote:
> Hi,
>
> good idea, but no. The datatypes are superficially equivalent, but the
> Applicative instance differs:
>
> With NonEmpty’s instance:
>
>> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
> (0,3) :| [(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]
>
> with my instance:
>
>> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
> (0,3) :| [(1,3),(2,3),(0,4),(0,5)]
>
> Greetings,
> Joachim
>
> Am Dienstag, den 31.01.2017, 14:24 -0600 schrieb Christopher Allen:
>> NonEmpty?
>>
>> On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner
>> <[hidden email]> wrote:
>> > Hi,
>> >
>> > I recently wrote this applicative functor:
>> >
>> >     data OneStep a = OneStep a [a]
>> >
>> >     instance Functor OneStep where
>> >         fmap f (OneStep o s) = OneStep (f o) (map f s)
>> >
>> >     instance Applicative OneStep where
>> >         pure x = OneStep x []
>> >         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs
>> > ++ map f xs)
>> >
>> >     takeOneStep :: OneStep t -> [t]
>> >     takeOneStep (OneStep _ xs) = xs
>> >
>> > This was useful in the context of writing a shrink for QuickCheck,
>> > as
>> > discussed at http://stackoverflow.com/a/41944525/946226.
>> >
>> > Now I wonder: Does this functor have a proper name? Does it already
>> > exist in the libraries somewhere? Should it?
>> >
>> > Greetings,
>> > Joachim
>> >
>> > --
>> > Joachim “nomeata” Breitner
>> >   [hidden email]https://www.joachim-breitner.de/
>> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>> >   Debian Developer: [hidden email]
>> > _______________________________________________
>> > 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.
>>
>>
>>
> --
> Joachim “nomeata” Breitner
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
>
> _______________________________________________
> 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.



--
Chris Allen
Currently working on http://haskellbook.com
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Christopher Allen
I must confess, this one's behavior makes more sense to me. It's the
product of the guaranteed values and the cartesian product.

On Tue, Jan 31, 2017 at 3:25 PM, Matt <[hidden email]> wrote:

> Interestingly, neither NEL nor OneStep behave the same as `Product Identity
> []`:
>
> λ> let a = Pair (Identity 0) [1,2]
> λ> let b = Pair (Identity 3) [4,5]
> λ> (,) <$> a <*> b
> Pair (Identity (0,3)) [(1,4),(1,5),(2,4),(2,5)]
>
> So many applicatives!
>
> Matt Parsons
>
> On Tue, Jan 31, 2017 at 3:41 PM, Christopher Allen <[hidden email]>
> wrote:
>>
>> Ah right, I didn't stare hard enough at the Applicative.
>>
>> If I squint a bit at the results of your Applicative instance it seems
>> similar to the difference between []'s Applicative and the ZipList
>> Applicative, except a little crossed up. Sure you already identified
>> that, sorry I don't have more to offer here.
>>
>> On Tue, Jan 31, 2017 at 2:36 PM, Joachim Breitner
>> <[hidden email]> wrote:
>> > Hi,
>> >
>> > good idea, but no. The datatypes are superficially equivalent, but the
>> > Applicative instance differs:
>> >
>> > With NonEmpty’s instance:
>> >
>> >> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
>> > (0,3) :| [(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]
>> >
>> > with my instance:
>> >
>> >> (,) <$> 0 :| [1,2] <*> 3 :| [4,5]
>> > (0,3) :| [(1,3),(2,3),(0,4),(0,5)]
>> >
>> > Greetings,
>> > Joachim
>> >
>> > Am Dienstag, den 31.01.2017, 14:24 -0600 schrieb Christopher Allen:
>> >> NonEmpty?
>> >>
>> >> On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner
>> >> <[hidden email]> wrote:
>> >> > Hi,
>> >> >
>> >> > I recently wrote this applicative functor:
>> >> >
>> >> >     data OneStep a = OneStep a [a]
>> >> >
>> >> >     instance Functor OneStep where
>> >> >         fmap f (OneStep o s) = OneStep (f o) (map f s)
>> >> >
>> >> >     instance Applicative OneStep where
>> >> >         pure x = OneStep x []
>> >> >         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs
>> >> > ++ map f xs)
>> >> >
>> >> >     takeOneStep :: OneStep t -> [t]
>> >> >     takeOneStep (OneStep _ xs) = xs
>> >> >
>> >> > This was useful in the context of writing a shrink for QuickCheck,
>> >> > as
>> >> > discussed at http://stackoverflow.com/a/41944525/946226.
>> >> >
>> >> > Now I wonder: Does this functor have a proper name? Does it already
>> >> > exist in the libraries somewhere? Should it?
>> >> >
>> >> > Greetings,
>> >> > Joachim
>> >> >
>> >> > --
>> >> > Joachim “nomeata” Breitner
>> >> >   [hidden email]https://www.joachim-breitner.de/
>> >> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>> >> >   Debian Developer: [hidden email]
>> >> > _______________________________________________
>> >> > 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.
>> >>
>> >>
>> >>
>> > --
>> > Joachim “nomeata” Breitner
>> >   [hidden email]https://www.joachim-breitner.de/
>> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>> >   Debian Developer: [hidden email]
>> >
>> > _______________________________________________
>> > 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.
>>
>>
>>
>> --
>> Chris Allen
>> Currently working on http://haskellbook.com
>> _______________________________________________
>> 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.
>
>



--
Chris Allen
Currently working on http://haskellbook.com
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Joachim Breitner-2
In reply to this post by Joachim Breitner-2
Hi,

Am Dienstag, den 31.01.2017, 15:22 -0500 schrieb Joachim Breitner:

> I recently wrote this applicative functor:
>
>     data OneStep a = OneStep a [a]
>
>     instance Functor OneStep where
>         fmap f (OneStep o s) = OneStep (f o) (map f s)
>
>     instance Applicative OneStep where
>         pure x = OneStep x []
>         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs ++
> map f xs)
>
>     takeOneStep :: OneStep t -> [t]
>     takeOneStep (OneStep _ xs) = xs
>
> This was useful in the context of writing a shrink for QuickCheck, as
> discussed at http://stackoverflow.com/a/41944525/946226.
>
> Now I wonder: Does this functor have a proper name? Does it already
> exist in the libraries somewhere? Should it?
I guess it does not exist, so I am preparing a package for it here:
https://github.com/nomeata/haskell-successors

The source code contains (in comments) a proof of the Applicative laws.

My gut feeling says that this does not have a Monad instance that is
compatible with the given Applicative instance, but it is too late
today to substantiate this feeling. If anyone feels like puzzling: Can
you come up with a Monad instance, or (more likely) give good reasons
why there cannot be one?

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

David Menendez-2
On Tue, Jan 31, 2017 at 11:55 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Dienstag, den 31.01.2017, 15:22 -0500 schrieb Joachim Breitner:
> I recently wrote this applicative functor:
>
>     data OneStep a = OneStep a [a]
>
>     instance Functor OneStep where
>         fmap f (OneStep o s) = OneStep (f o) (map f s)
>
>     instance Applicative OneStep where
>         pure x = OneStep x []
>         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x) fs ++
> map f xs)
>
>     takeOneStep :: OneStep t -> [t]
>     takeOneStep (OneStep _ xs) = xs
>
> This was useful in the context of writing a shrink for QuickCheck, as
> discussed at http://stackoverflow.com/a/41944525/946226.
>
> Now I wonder: Does this functor have a proper name? Does it already
> exist in the libraries somewhere? Should it?

I guess it does not exist, so I am preparing a package for it here:
https://github.com/nomeata/haskell-successors

The source code contains (in comments) a proof of the Applicative laws.

My gut feeling says that this does not have a Monad instance that is
compatible with the given Applicative instance, but it is too late
today to substantiate this feeling. If anyone feels like puzzling: Can
you come up with a Monad instance, or (more likely) give good reasons
why there cannot be one?

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.

--

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Oleg Grenrus
These instances are quite similar to

https://github.com/ambiata/disorder.hs/blob/ce9ffc1139e32eaa9b82a1a6e2cfeb914d3f705c/disorder-jack/src/Disorder/Jack/Tree.hs#L62-L82

(I wish `disorder-jack` were already on Hackage!)

- Oleg


On 01.02.2017 07:28, David Menendez wrote:

> On Tue, Jan 31, 2017 at 11:55 PM, Joachim Breitner
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     Hi,
>
>     Am Dienstag, den 31.01.2017, 15:22 -0500 schrieb Joachim Breitner:
>     > I recently wrote this applicative functor:
>     >
>     >     data OneStep a = OneStep a [a]
>     >
>     >     instance Functor OneStep where
>     >         fmap f (OneStep o s) = OneStep (f o) (map f s)
>     >
>     >     instance Applicative OneStep where
>     >         pure x = OneStep x []
>     >         OneStep f fs <*> OneStep x xs = OneStep (f x) (map ($x)
>     fs ++
>     > map f xs)
>     >
>     >     takeOneStep :: OneStep t -> [t]
>     >     takeOneStep (OneStep _ xs) = xs
>     >
>     > This was useful in the context of writing a shrink for
>     QuickCheck, as
>     > discussed at http://stackoverflow.com/a/41944525/946226
>     <http://stackoverflow.com/a/41944525/946226>.
>     >
>     > Now I wonder: Does this functor have a proper name? Does it already
>     > exist in the libraries somewhere? Should it?
>
>     I guess it does not exist, so I am preparing a package for it here:
>     https://github.com/nomeata/haskell-successors
>     <https://github.com/nomeata/haskell-successors>
>
>     The source code contains (in comments) a proof of the Applicative
>     laws.
>
>     My gut feeling says that this does not have a Monad instance that is
>     compatible with the given Applicative instance, but it is too late
>     today to substantiate this feeling. If anyone feels like puzzling: Can
>     you come up with a Monad instance, or (more likely) give good reasons
>     why there cannot be one?
>
>
> 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.
>
> --
> Dave Menendez <[hidden email] <mailto:[hidden email]>>
> <http://www.eyrie.org/~zednenem/ <http://www.eyrie.org/%7Ezednenem/>>
>
>
> _______________________________________________
> 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.

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Joachim Breitner-2
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?

Am Mittwoch, den 01.02.2017, 09:34 +0200 schrieb Oleg Grenrus:
> These instances are quite similar to
>
> https://github.com/ambiata/disorder.hs/blob/ce9ffc1139e32eaa9b82a1a6e
> 2cfeb914d3f705c/disorder-jack/src/Disorder/Jack/Tree.hs#L62-L82
>

well spotted. It is indeed the same idea, with my Succs (or OneStep or
whatever name is most appropriate) modeling only one step, and the tree
modeling, well, a whole tree.

Also thanks for pointing out disorder-jack, that looks like a nice
approach!

Greetings,
Joachim


--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Joachim Breitner-2
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
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Haskell - Haskell-Cafe mailing list
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 <[hidden email]>:

> 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
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
>
> _______________________________________________
> 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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Gershom Bazerman
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 ([hidden email]) 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
> > [hidden email]https://www.joachim-breitner.de/
> > XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
> > Debian Developer: [hidden email]
> >
> > _______________________________________________
> > 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.
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Joachim Breitner-2
In reply to this post by Haskell - Haskell-Cafe mailing list
Hi,

already fixed in the repo, but not worth an upload.

Thanks!
Joachim

Am Mittwoch, den 01.02.2017, 19:13 +0100 schrieb Simon Jakobi via
Haskell-Cafe:

> 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 <[hidden email]
> >:
> > 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/c1fd614cb0fc3e3b
> > 5dbf0338f835a91ea78e0b63/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
> >   [hidden email]https://www.joachim-breitner.de/
> >   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
> >   Debian Developer: [hidden email]
> >
> > _______________________________________________
> > 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.
--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
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.

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is this applicative functor?

Li-yao Xia-2
In reply to this post by Gershom Bazerman
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 ([hidden email]) 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
>>> [hidden email]https://www.joachim-breitner.de/
>>> XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>>> Debian Developer: [hidden email]
>>>
>>> _______________________________________________
>>> 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.

_______________________________________________
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.