Haskell lenses: how to make view play nicely with traverse?

Question

I am trying to learn about lenses by implementing it in Haskell. I have implemented the view combinator as follows:

{-# LANGUAGE RankNTypes #-}

import Control.Applicative
import Data.Traversable

type Lens s a = Functor f => (a -> f a) -> s -> f s

view :: Lens s a -> s -> a
view lens = getConst . lens Const

However when I try to use it in conjunction with traverse I get the following error message:

Prelude> :load Lens.hs
[1 of 1] Compiling Main             ( Lens.hs, interpreted )
Ok, modules loaded: Main.
*Main> :t view traverse

<interactive>:1:6:
    Could not deduce (Applicative f) arising from a use of ‘traverse’
    from the context (Traversable t)
      bound by the inferred type of it :: Traversable t => t a -> a
      at Top level
    or from (Functor f)
      bound by a type expected by the context:
                 Functor f => (a -> f a) -> t a -> f (t a)
      at <interactive>:1:1-13
    Possible fix:
      add (Applicative f) to the context of
        a type expected by the context:
          Functor f => (a -> f a) -> t a -> f (t a)
        or the inferred type of it :: Traversable t => t a -> a
    In the first argument of ‘view’, namely ‘traverse’
    In the expression: view traverse

Unfortunately, I don't understand this error message. Please explain what it means and how I may fix it.

Soneson

Answer 1

As the other answers already explain, the issue is that view expects something that works for any Functor f, but traverse only works if f is also Applicative (and there are functors which are not applicative).

In lens, the problem is solved by making the type of view not take a Rank2 argument (in fact, most functions in lens don't use the Lens type synonym, they always use something weaker). For your function, observe that view only ever uses f ~ Const. This is why you can change the type signature to:

view :: ((a -> Const a a) -> s -> Const a s) -> s -> a

The implementation can stay the same, but now view also works on traverse:

view traverse :: (Traversable t, Monoid a) => t a -> a

Note the extra Monoid constraint. This constraint appears because if you set f ~ Const a in traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a), you need an instance Applicative (Const a). That instance has a Monoid constraint on a though. And this also makes sense, because the traversable might be empty or contain more than one element, so you need mempty and mappend.

Forecourse

Great answer. Thank you so much for a smart solution to the problem. I do have one question though: wouldn't the type signature of view become ((a -> Const a a) -> s -> Const a s) -> s -> a? – Soneson

Answer 2

traverse has this type:

traverse :: (Applicative f, Traversable t) => (x -> f y) -> t x -> f (t y)

If we make the free variable f in the type definition of Lens explicit, its definition is actually

type Lens s a = forall f . Functor f => (a -> f a) -> s -> f s

So view wants a function that can operate on any Functor, whereas traverse can only operate on an Applicative.

You can fix the error simply by changing Functor into Applicative in the definition of Lens, but I'm not sure if that's exactly what you would want to achieve here.

Tragedian

Changing Functor to Applicative here will give you a Traversal, won't it? I guess this gives some intuition for where the name "Traversal" comes from. – Pronominal

Answer 3

tl;dr - According to your definition of Lens, a traverse cannot be a Lens because traverse doesn't work for all Functors.

---

Let's take a look at your types:

λ :set -XRankNTypes 
λ :m +Control.Applicative Data.Traversable 
λ type Lens s a = Functor f => (a -> f a) -> s -> f s
λ :t traverse
traverse
  :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

Now at this point we can see that traverse is, in one way, slightly more general than our Lens type - it can take a function from a -> f b where our lens can only take functions from a -> f a.

Restricting it to that case is no problem, so we can say

λ :t traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a)
traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a)
  :: (Applicative f, Traversable t) => (a -> f a) -> t a -> f (t a)

So now it's obvious that if traverse is to be a Lens, it must be a Lens (t a) a, since that's the only way to make the type variables line up.

So let's try that out.

λ :t traverse :: Lens (t a) a

<interactive>:1:1:
    Could not deduce (Traversable t1) arising from a use of `traverse'
    from the context (Functor f)
      bound by the inferred type of
               it :: Functor f => (a -> f a) -> t a -> f (t a)
      at Top level
    or from (Functor f1)
      bound by an expression type signature:
                 Functor f1 => (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1)
      at <interactive>:1:1-24
    Possible fix:
      add (Traversable t1) to the context of
        an expression type signature:
          Functor f1 => (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1)
        or the inferred type of
           it :: Functor f => (a -> f a) -> t a -> f (t a)
    In the expression: traverse :: Lens (t a) a

Oof, it didn't like that. Oh, wait, in order to use traverse our type t has to be Traversable, so let's add that restriction. (Just like the "Possible fix") suggests:

λ :t traverse :: Traversable t => Lens (t a) a

<interactive>:1:1:
    Could not deduce (Applicative f1) arising from a use of `traverse'
    from the context (Functor f, Traversable t)
      bound by the inferred type of
               it :: (Functor f, Traversable t) => (a -> f a) -> t a -> f (t a)
      at Top level
    or from (Traversable t1, Functor f1)
      bound by an expression type signature:
                 (Traversable t1, Functor f1) =>
                 (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1)
      at <interactive>:1:1-41
    Possible fix:
      add (Applicative f1) to the context of
        an expression type signature:
          (Traversable t1, Functor f1) =>
          (a1 -> f1 a1) -> t1 a1 -> f1 (t1 a1)
        or the inferred type of
           it :: (Functor f, Traversable t) => (a -> f a) -> t a -> f (t a)
    In the expression: traverse :: Traversable t => Lens (t a) a

Ok, so the problem now is that it can't infer that f is Applicative (which is also required to use traverse), just that it's a Functor (which it gets from the definition of Lens).

We can't add Applicative f to the context though - the f is hidden. When we say type Lens s a = Functor f => (a -> f a) -> s -> f s, we're saying that the Lens has to work for all Functors.

But traverse only works for the subset of Functors that are also Applicative. So in this way the type of traverse is more specific than is allowed for Lenses.

Andesite