_last ignores the first element of NonEmpty

[int-index]

Actual behavior:

Prelude Control.Lens Data.List.NonEmpty> over _last not (True :| [])
True :| []

Expected behavior:

Prelude Control.Lens Data.List.NonEmpty> over _last not (True :| [])
False :| []

[int-index]

Same for _head.

[s9gf4ult]

I think that is why:

instance a~b => Cons (NonEmpty a) (NonEmpty b) a b where
  _Cons = prism' (uncurry NonEmpty.cons) $ \ xyz -> case xyz of
    (x:|y:z) -> Just (x,y:|z)
    _        -> Nothing
  {-# INLINE _Cons #-}

here must be one more case, but (x :| []) -> Just (x, ???)

[int-index]

Surely we can have a ~ b => Cons (NonEmpty a) [a] a b instead?

[s9gf4ult]

Nice trick to brake fundeps...

[phadej]

@int-index functional dependencies would prevent that, and render impossible to use _Cons to cons stuff in front of NonEmpty

[int-index]

Yet it makes sense that we can cons in front of a list and get a NonEmpty. Fundeps aren't written in stone, what happens if we remove it?

In any case, it's better to have no instance at all than such a bogus one.

[phadej]

@int-index I'm afraid it will make a bad inference story. I'm also of removing the instance (and having _head and _tail implemented differently). AFter all, head and tail could be a Lens for NonEmpty

[s9gf4ult]

We could make _head and _tail a methods of typeclasses, like Head and Tail respectively and default overlapping instances for them like instance Cons s s a a => Head s a and instance Cons s s a a => Tail s a

[s9gf4ult]

Or we could change typeclasses _Cons and _Snoc like.

class Cons s t a b | s -> a, t -> b, s b -> t, t a -> s where
  _Cons :: Prism s t (a,Maybe s) (b,Maybe t)

class Snoc s t a b | s -> a, t -> b, s b -> t, t a -> s where
  _Snoc :: Prism s t (Maybe s,a) (Maybe t,b)

[Icelandjack]

Another direction is to have a type class of an Optic where _Cons and _Snoc can be Prisms or Isos:

class Cons' s t a b | s -> a, t -> b, s b -> t, t a -> s where
  type Cons'Optic s (p :: Type -> Type -> Type) (f :: Type -> Type)  = (res ∷ Constraint) | res -> p f
  type Cons'Optic s p f = (Choice p, Applicative f)

  type Minus1 s
  type Minus1 s = s
  _Cons' :: Cons'Optic s p f => Optic p f s t (a, Minus1 s) (b, Minus1 t)
  default 
    _Cons' :: (Cons s t a b, Applicative f, Minus1 s ~ s, Minus1 t ~ t) => LensLike f s t (a, Minus1 s) (b, Minus1 t)
  _Cons' = _Cons

This way we can define an isomorphisms for NonEmpty and length-indexed vectors:

instance Cons' (NonEmpty a) (NonEmpty b) a b where
  type Cons'Optic (NonEmpty a) p f = (Profunctor p, Functor f)

  type Minus1 (NonEmpty a) = [a]
  _Cons' :: Iso (NonEmpty a) (NonEmpty b) (a, [a]) (b, [b])
  _Cons' = iso 
    (\case x:|xs -> (x, xs))
    (uncurry (:|))

instance Cons' (Vec (S n) a) (Vec (S n) b) a b where
  type Cons'Optic (Vec (S n) a) p f = (Profunctor p, Functor f)

  type Minus1 (Vec (S n) a) = Vec n a
  _Cons' :: Iso (Vec (S n) a) (Vec (S n) b) (a, Vec n a) (b, Vec n b)
  _Cons' = iso 
    (\case Cons x xs -> (x, xs))
    (uncurry Cons)

and prisms for the usual:

instance Cons' [a] [b] a b where
  type NameConstraint [a] p f = (Choice p, Applicative f)
  type Minus1 [a] = [a]

  _Cons' :: Prism [a] [b] (a, [a]) (b, [b])
  _Cons' = prism 
    (uncurry (:))
    (\case
      []   -> Left []
      x:xs -> Right (x, xs))

[ekmett]

@Icelandjack

Cons and Snoc used to take more type parameters which allowed for things like it being an Iso or for types to change to allow manipulation of HList and Rec types, but we found it too difficult for users to use when they wanted to abstract over the instance.

[ekmett]

Surely we can have a ~ b => Cons (NonEmpty a) [a] a b instead?

That is not going to give rise to a legal optic.

s and t must be drawn from the same parametric indexed family of types S and a and b must be drawn from the same family A, such that s = S i, t = S j, a = A i, b = A j

[ekmett]

I think the most likely solution either we document the instance with a comment clearly noting that it is law-abiding but not what you'd expect or we remove the instance.

[int-index]

I didn't even look at the documentation when I wrote this code. Treating NonEmpty a as a non-empty list makes you think that using _last will actually give you the last element.

If it's law-abiding then the laws are wrong (or insufficient).

[int-index]

I vote for either changing the typeclass or removing the instance.

[int-index]

The worst thing, of course, is that most of the times (when you have >1 elements) the instance works as expected. So it's really easy to introduce logical errors.

[ekmett]

If you view NonEmpty as isomorphic to a two constructor solution where you have

data NonEmpty a = Cons a (NonEmpty a) | Last a

then _Cons it picks out the Cons constructor, but can't remove the "proper" last element.

[ekmett]

I have no particular objection to removing the instance.

[ekmett]

This is effectively a duplicate of #537 where we talked about the same issue.

[ekmett]

I'd handily take a patch for a major version bump and removal of this instance. It has raised two issues so far, and clearly doesn't have the expected semantics.

[int-index]

I'll go ahead and make a PR.

[Icelandjack]

@ekmett It should be possible to abstract over it, it would be nice to be able to use uncons on those instances and knowing it won't fail. I understand if it doesn't warrant the complexity though

[ekmett]

@Icelandjack

We used to have a more complex type on the instance for AsArithException and the like that let the instance for ArithException be an Equality, while the instance for SomeException was a Prism. The problem was that it requires either using a constraint valued type synonym to the class, limiting us to ghc 7.6+, or it requires adding parameters for p and f to the class, so we can pick constraints pointwise, the latter solution is what we adopted the first time here, the former solution we tried around Contains at one point, so you could e.g. use it as just a Getter on a Map.

Either solution wreaks havoc on users who want to abstract over an instance.

You leak particular ps and fs into the context, or you have a hard time specifying an "AsArithException that is at least a Prism" constraint, because we don't have first-class exponentials in the category of constraints that type inference knows about, so we can't ask if the type of constraints we do require is entailed by the one we put into the context, so then the constraint-valued type family leaks instead until we pick a concrete instance.

The cure is worse than the disease, which is why we stopped doing this for Cons and Contains in the first place. These were too painful for users to use.

[ekmett]

(ConstraintKinds is nominally accepted by GHC 7.4, but you get broken interface files, hence 7.6+)

[s9gf4ult]

We could also make head and tail be methods of typeclasses Head' and Tail' and give them default instances implemented through Cons' and Snoc' respectively.

[ekmett]

We could, but it would make the whole affair a lot more ad hoc and complicated. The nice thing about _Cons is that it being a prism precisely captures the most common relationship between head, tail and uncons. NonEmpty has a different such relationship with a different signature for uncons.