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.

bennofs · Accepted Answer · 2014-09-11T14:39:27.957

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.

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`? — Aadit M Shah, Sep 11 '14 at 02:29

Ganesh Sittampalam · Answer 2 · 2014-09-10T19:59:30.073

3

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.

edited Sep 10 '14 at 19:59

answered Sep 10 '14 at 19:49

Ganesh Sittampalam

28,821
4
79
98

2

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. – Tikhon Jelvis Sep 11 '14 at 01:05

score 3 · Answer 3 · answered Sep 10 '14 at 19:53

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.

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

3 Answers3