[Haskell-cafe] What is this applicative functor?

[Joachim Breitner]

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 at joachim-breitner.de • https://www.joachim-breitner.de/
  XMPP: nomeata at joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170131/93a7ddd0/attachment.sig>