What is this applicative functor?

newer
A question about GHC test coverage

Joachim Breitner

31 Jan 2017 31 Jan '17

3:22 p.m.

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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Attachments:

signature.asc (application/pgp-signature — 833 bytes)

Show replies by date

Christopher Allen

31 Jan 31 Jan

3:24 p.m.

NonEmpty? On Tue, Jan 31, 2017 at 2:22 PM, Joachim Breitner 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

-- Chris Allen Currently working on http://haskellbook.com

Joachim Breitner

3:36 p.m.

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 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Christopher Allen

3:41 p.m.

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 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 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

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

-- Chris Allen Currently working on http://haskellbook.com

Matt

4:25 p.m.

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 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 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 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

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

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

Christopher Allen

4:32 p.m.

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 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 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 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 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

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

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

Joachim Breitner

11:55 p.m.

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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

David Menendez

1 Feb 1 Feb

12:28 a.m.

On Tue, Jan 31, 2017 at 11:55 PM, Joachim Breitner

...

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. -- Dave Menendez http://www.eyrie.org/~zednenem/

Oleg Grenrus

2:34 a.m.

These instances are quite similar to https://github.com/ambiata/disorder.hs/blob/ce9ffc1139e32eaa9b82a1a6e2cfeb91... (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 mailto:mail@joachim-breitner.de> 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 mailto:dave@zednenem.com> <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.

Joachim Breitner

10:33 a.m.

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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Joachim Breitner

12:39 p.m.

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/c1fd614cb0fc3e3b5dbf0338f... Uploaded to http://hackage.haskell.org/package/successors in case someone wants to play with it. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Simon Jakobi

1:13 p.m.

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/c1fd614cb0fc3e3b5dbf0338f...

Uploaded to http://hackage.haskell.org/package/successors in case someone wants to play with it.

Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

Gershom B

1:50 p.m.

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@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/c1fd614cb0fc3e3b5dbf0338f...

Uploaded to http://hackage.haskell.org/package/successors in case someone wants to play with it.

Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

Li-yao Xia

20 Feb 20 Feb

4:51 p.m.

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@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/c1fd614cb0fc3e3b5dbf0338f...

Uploaded to http://hackage.haskell.org/package/successors in case someone wants to play with it.

Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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.

Joachim Breitner

1 Feb 1 Feb

2:03 p.m.

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
...
: 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 mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@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. -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

3011

Age (days ago)

3031

Last active (days ago)

List overview

Download

14 comments

8 participants

participants (8)

Christopher Allen
David Menendez
Gershom B
Joachim Breitner
Li-yao Xia
Matt
Oleg Grenrus
Simon Jakobi