Thank you Gesh. Your reply is very helpful. I guessed that the correct Extend instance for List is needed for Comonad, but didn't have any intuition about it. The way the NICTA course is structured, there's no mention of the dependence between "extend" and "copure" (equivalent to extract and duplicate I suppose) via the Comonad laws when considering Extend first by itself. I'm not knocking the NICTA course. I've found it useful. A quick paragraph or two as you've written, stuck into the source files as comments, would improve it. Regards, Graham On 12/14/2015 5:53 AM, Gesh wrote:

On December 14, 2015 6:57:27 AM GMT+02:00, Graham Gill wrote:

...

The NICTA course https://github.com/NICTA/course includes exercises on the type class Extend, in Course/Extend.hs. Extend is a superclass of Comonad. Here's the class definition:

...

-- | All instances of the `Extend` type-class must satisfy one law. This law -- is not checked by the compiler. This law is given as: -- -- * The law of associativity -- `∀f g. (f <<=) . (g <<=) ≅ (<<=) (f . (g <<=))` class Functor f => Extend f where -- Pronounced, extend. (<<=) :: (f a -> b) -> f a -> f b

infixr 1 <<= Could someone please motivate the Extend instance for List? (Its implementation is left as an exercise. In the course, type List a is isomorphic to [a].) Some of the tests (<<=) is expected to pass are shown, and make clear what ought to happen. -- | Implement the @Extend@ instance for @List@. -- -- >>> length <<= ('a' :. 'b' :. 'c' :. Nil) -- [3,2,1] -- -- >>> id <<= (1 :. 2 :. 3 :. 4 :. Nil) -- [[1,2,3,4],[2,3,4],[3,4],[4]] -- -- >>> reverse <<= ((1 :. 2 :. 3 :. Nil) :. (4 :. 5 :. 6 :. Nil) :. Nil) -- [[[4,5,6],[1,2,3]],[[4,5,6]]] The following (wrong, according to the tests) Extend instance for List nevertheless obeys the types and obeys the Extend law of associativity. instance Extend List where (<<=) :: (List a -> b) -> List a -> List b (<<=) f = (:. Nil) . f (:. Nil) is analogous to (: []), create a singleton list.

I can't find a good reference on the Extend type class to convince me why the correct Extend instance for List in the course is the desirable

one. (I'm not saying my version is desirable, in fact it seems fairly useless, but it works.)

Graham

------------------------------------------------------------------------

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners Indeed, your implementation is a valid Extend instance. However, it cannot be extended into a valid Comonad, whereas the supplied instance can.

Can you see why? Hint: In order to be a Comonad, an Extend instance must also supply a function extract:: f a -> a which must be an identity for extend. Is this possible for your instance?

The intuition behind Extend is that given a computation that takes into account the context of the values in your container, it applies that computation everywhere, passing it the appropriate context. Thus, elements of List may be considered as having the remainder of the list as their context, and that is indeed what is passed to the computation, as evidence by extend id.

Indeed, this function is so essential to the essence of a Comonad that it is given its own name - duplicate - and forms the building block for an equivalent set of laws for Comonad, namely: - duplicate . duplicate = fmap duplicate . duplicate - extract . duplicate = id = fmap extract . duplicate (If you've heard of join in the context of Monad, this is precisely the dual set of laws it satisfies)

Indeed, it may be easier to prove your Extend instance doesn't extend to a Comonad instance by using this formulation of the laws.

HTH, Gesh _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

On December 15, 2015 12:36:58 PM GMT+02:00, Kim-Ee Yeoh wrote:

On Tue, Dec 15, 2015 at 12:43 AM, Graham Gill wrote:

I guessed that the correct Extend instance for List is needed for Comonad,

...

but didn't have any intuition about it.

List is not comonadic. In this case, the function copure must be of type [a] -> a, which must necessarily be partial.

(Non-empty lists, on the other hand, are comonadic.) In fact, it seems this distinction is true of any type that has an empty case, i.e. f s.t. exists g. f a = 1 + g a. What blinded me was the fact that for such types, usually the definition of extend extends naturally to the empty case. So obviously the possibly-empty types have an Extend instance inherited from their nonempty counterparts, but it is only the latter who have Comonad instances.

Graham's "Extend" -- I'll explain the scare quotes in a minute -- instance for List obeys the associative law. So it's a valid instance but a bit boring. The exercise asks for an interesting instance. Indeed, the same problem exists dually for Monad, where one can force the empty case always and obtain a Monad isomorphic to Const ().

Thanks for the correction and illumination, Gesh

The way the NICTA course is structured, there's no mention of the

...

dependence between "extend" and "copure" (equivalent to extract and duplicate I suppose) via the Comonad laws when considering Extend first by itself.

It's a bit terse, but you can find "class Extend f => Comonad f" in Comonad.hs. After all, we're only looking at the exercises. The live lecture version probably does talk about the dependence.

...

I'm not knocking the NICTA course. I've found it useful. A quick paragraph or two as you've written, stuck into the source files as comments, would improve it.

Most folks are neutral about the course. If parts of it work for you, great. If not, no worries. The whole comonadic business is a bit obscure and some of the strongest haskell programmers don't bat an eyelid over not knowing it.

p.s. "Extend" doesn't agree with the CT literature. See the paragraph that starts "The dual problem is the problem of lifting a morphism" here:

http://ncatlab.org/nlab/show/extension

But calling it a "lift" or "lifting" will only add to the confusion since monad transformers got first dibs on the terminology. Which is why you sometimes see "coextend" or (for the flipped version) "cobind".

-- Kim-Ee

------------------------------------------------------------------------

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners