CODEWITHSUNDEEP
listmonadscomonad
user442920
user442920

Reputation: 847

Is list a monad and comonad?

The list monad is given here. Also see Spivak's paper here. So list is a monad. Is it a comonad? How would you prove that?

Upvotes: 0

Views: 441

Answers (1)

Cactus
Cactus

Reputation: 27626

The list type constructor a ↦ μ L. 1 + a * L doesn't admit a comonad structure. Recall that if it were a comonad, we'd have (using the names from Haskell's Functor and Comonad typeclasses)

fmap :: ∀  a b. (a → b) → [a] → [b]
extract :: ∀  a. [a] → a
duplicate :: ∀  a. [a] → [[a]]

However, even without going into any required laws, extract cannot be implemented, since its input could be the empty list, giving no way to come up with an a.

The nonempty list type constructor a ↦ μ NE. a + a * NE does admit a comonad structure, with extract returning the first element, and duplicate mapping [x, y, ..., z] to [[x], [x, y], ..., [x, y, ..., z]] (note that each of them are non-empty by construction).

Upvotes: 1

Related Questions