Are there examples of functors in Haskell which fails to be monads because we cannot implement `return`?

Question

Are there any examples of functors in Haskell which fail to be monads because we cannot implement return?

I have seen this answer and am inspired by it.

Intuitively it seems that we can always implement return by using the type constructor. But I must be missing something.

@luqui This is unfair though as `Writer` is a _bi_-functor. By parametricity, it is impossible to define a value of its left type out of nowhere. For instance, see [how `Applicative` is done for tuples](https://stackoverflow.com/questions/38415374) _(which are also bifunctors)_. So, if `Writer` is an example, then `(x, y)` is also. — Ignat Insarov, Oct 20 '19 at 08:02
@IgnatInsarov, i agree with everything you said except "this is unfair". Seems like it answers the question adequately. What's the problem? — luqui, Oct 20 '19 at 08:43
@luqui I did not mean to be offensive. If we agree with unconstrained `(x, y)` being an example, then there is no problem. But it is then a boring question. Possibly there are better examples — such that, no matter the constraints, there is not a way to define `return` compatible with `ap`, for some fundamental reason. I am thinking even for `IntMap` we could have `pure`, just a very slow one. So, if we exclude unrestricted bifunctors, we get an interesting question back. — Ignat Insarov, Oct 20 '19 at 09:00
@IgnatInsarov You basically have two choices for `pure :: a -> IntMap a`. Either `pure _ = Nil` or `pure x = Tip y x` for some fixed `y :: Int`. Try to prove the [applicative laws](https://en.wikibooks.org/wiki/Haskell/Applicative_functors#Applicative_functor_laws) hold for either. (We can ignore `Bin`, since choosing such a value ultimately requires either a `Nil` or a `Key` value to be constructed.) — chepner, Oct 20 '19 at 14:03
Sorry, I should have said functor laws, since we do have `bind` already. — chepner, Oct 20 '19 at 14:22
@chepner what if `pure x` created an `IntMap` where every possible `Int` was present and they all mapped to `x`? — Joseph Sible-Reinstate Monica, Oct 20 '19 at 14:52
@JosephSible True, though looking at that one specifically, it would violate the right identity, no? — chepner, Oct 20 '19 at 19:06
@chepner My idea was the same as Joseph Sible's — to have a very large regular map for `pure`. I am thinking the laws to hold are those connecting `pure` and `ap`. I do not have a detailed proof, and, truth be told, I am not intellectually equipped to research further. Hand waving goes in the direction of a map being a [container](https://www.cs.nott.ac.uk/~psztxa/publ/fossacs03.pdf) with a shape defined by its keys, and then by analogy with a `ZipList` or some other simple container that has a `zip` applicative. — Ignat Insarov, Oct 20 '19 at 19:33
@IgnatInsarov The right identity law says that `m >>= return == m`. If `return` creates a "full" `IntMap`, then *some* value in the original `m` will get overwritten by `>>=`. — chepner, Oct 20 '19 at 19:40
@chepner True. I also see [there is no `instance Monad ZipList`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#t:ZipList) — with `pure` being `repeat`, [the usual monad definition](https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Base.html#line-984) would hang. On the other hand, I tried to make a _"cartesian"_ definition of `instance Monoid k => Applicative (Map k)` earlier today and I discovered that it is impossible to align it with the composition law unless the monoid is the free one. Trouble all around. — Ignat Insarov, Oct 20 '19 at 20:56
@chepner, I don't think so. `IntMap a` can be thought of as a different representation for `Int -> Maybe a` ~= `MaybeT (Int ->) a`. So if we just follow that guide, we will get law-abiding instances. In particular, `join` is diagonal, so each value in `m` gets mapped to a full constant intmap with that value, which is then diagonalized to get back to the original `m`. — luqui, Oct 20 '19 at 21:32

Joseph Sible-Reinstate Monica · Accepted Answer · 2022-02-10T05:45:50.490

8

This is exactly what the Bind typeclass represents: things that have a bind operation, but not necessarily return. Here's some types that are instances of Bind, but aren't instances of Monad because they don't have return:

(,) w,WriterT w m, and RWST r w s m, whenever w is a Semigroup but not a Monoid
Map k, HashMap k, and IntMap
V1 (note: this is isomorphic to Daniel Wagner's Whoops and pigworker's Dead)

edited Feb 10 '22 at 05:45

answered Oct 19 '19 at 21:08

Joseph Sible-Reinstate Monica

45,431
5
48
98

This is unfair though as a map is a _bi_-functor. By parametricity, it is impossible to define a value of its left type out of nowhere. For instance, see [how `Applicative` is done for tuples](https://stackoverflow.com/questions/38415374) _(which are also bifunctors)_. So, if a map is an example, then `(x, y)` is also. – Ignat Insarov Oct 20 '19 at 08:00
3

@IgnatInsarov I don't think it's unfair at all. All bifunctors are trivially also functors. And yes, both maps and tuples are examples. – Daniel Wagner Oct 20 '19 at 12:58
Are these maps functors? – Eli Rose Oct 20 '19 at 15:16
@EliRose Yes, over their values. – Joseph Sible-Reinstate Monica Oct 20 '19 at 16:13
@JosephSible I understand you to mean that `HashMap Int` is a functor, but HashMap by itself is not (it is a bifunctor) — is that correct? – Eli Rose Oct 20 '19 at 17:04
1

@EliRose `HashMap Int` is a functor, but `HashMap` is not a bifunctor for the same reason that sets aren't functors. – Joseph Sible-Reinstate Monica Oct 20 '19 at 17:59
@EliRose, what you'd particularly want to do, I think, is consider `HashMap` a (constrained) profunctor. A `HashMap` represents a partial function from keys to values, so it's reasonable to think about composing it with functions on either side. On one side, you get `fmap`. On the other, you get nothing ... unless you have a way to calculate a (partial) inverse of the function. The partial inverse concept leads to the bifunctor idea, which itself needs to be constrained. But I see it as a pretty awkward hack from the start. – dfeuer Oct 21 '19 at 02:12

score 6 · Answer 2 · answered Oct 19 '19 at 21:04

I guess if there's no constructor, we can't call one:

{-# LANGUAGE EmptyCase #-}
data Whoops a
instance Functor Whoops where fmap f v = case v of

EDIT In fact, this is mentioned at the linked question: have a search for the Dead type that pigworker uses to show how something can be a functor but not applicative.

Are there examples of functors in Haskell which fails to be monads because we cannot implement `return`?

2 Answers2