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.
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
.
tl;dr - According to your definition of Lens
, a traverse
cannot be a Lens
because traverse
doesn't work for all Functor
s.
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 Functor
s.
But traverse
only works for the subset of Functor
s that are also Applicative
. So in this way the type of traverse
is more specific than is allowed for Lens
es.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With