List based on right Kan extension

Question

In the ``Kan Extensions for Program Optimisation'' by Ralf Hinze there is the definition of List type based on right Kan extension of the forgetful functor from the category of monoids along itself (section 7.4). The paper gives Haskell implementation as follows:

newtype List a = Abstr {
  apply :: forall z . (Monoid z) => (a -> z) -> z
  }

I was able to define usual nil and cons constructors:

nil :: List a
nil = Abstr (\f -> mempty)

cons :: a -> List a -> List a
cons x (Abstr app) = Abstr (\f -> mappend (f x) (app f))

With the following instance of Monoid class for Maybe functor, I managed to define head function:

instance Monoid (Maybe a) where
  mempty = Nothing
  mappend Nothing m = m
  mappend (Just a) m = Just a

head :: List a -> Maybe a
head (Abstr app) = app Just

Question: How can one define tail function?

For what it's worth, your Monoid instance for Maybe is typically provided with the newtype Data.Monoid.First. — shachaf
That's a common pitfall without any obvious solution. A version, that traverses the whole list, was discussed somewhere in the TAPL book. For a better version see this. Also, there is a library with FoldMap lists. — user3237465

gallais gallais · Accepted Answer · 2014-12-09T15:10:20

Here is a rather principled solution to implementing head and tail in one go (full gist):

First of all, we know how to append lists (it will be useful later on):

append :: List a -> List a -> List a
append (Abstr xs) (Abstr ys) = Abstr (\ f -> xs f <> ys f)

Then we introduce a new type Split which we will use to detect whether a List is empty or not (and get, in the case it's non empty, a head and a tail):

newtype Split a = Split { outSplit :: Maybe (a, List a) }

This new type forms a monoid: indeed we know how to append two lists.

instance Monoid (Split a) where
  mempty = Split Nothing
  mappend (Split Nothing)        (Split nns)            = Split nns
  mappend (Split mms)            (Split Nothing)        = Split mms
  mappend (Split (Just (m, ms))) (Split (Just (n, ns))) =
    Split $ Just (m, append ms (cons n ns))

Which means that we can get a function from List a to Split a using List a's apply:

split :: List a -> Split a
split xs = apply xs $ \ a -> Split $ Just (a, nil)

head and tail can finally be trivially derived from split:

head :: List a -> Maybe a
head = fmap fst . outSplit . split

tail :: List a -> Maybe (List a)
tail = fmap snd . outSplit . split

List based on right Kan extension

2 Answers