[Haskell-beginners] Extend instance for List

[Gesh]

On December 14, 2015 6:57:27 AM GMT+02:00, Graham Gill <math.simplex at gmail.com> 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 at .
>> --
>> -- >>> 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 at 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