Why is List a Semigroup but Seq is not?

Question

I'm fairly new to scalaz and I am trying to figure out why the following code works:

import scalaz._
import Scalaz._
scala> Map[String,List[String]]() |+| Map[String,List[String]]()
res3: scala.collection.immutable.Map[String,List[String]] = Map()

but this doesn't...

import scalaz._
import Scalaz._
scala> Map[String,Seq[String]]() |+| Map[String,Seq[String]]()
<console>:14: error: value |+| is not a member of      scala.collection.immutable.Map[String,Seq[String]]
          Map[String,Seq[String]]() |+| Map[String,Seq[String]]()

I see the Map implicit for Semigroup, but I don't see the one for List or Seq.

Couple questions:

1. Where is the implicit for ListSemigroup?
2. Why isn't there one for Seq?

Niobium

What version are you using? Your tags suggest, you are asking about scalaz-seven, while the link to Semigroup.scala leads to master, which is 6.x. – Kryska

I am indeed using 7. I'll fix my link. – Niobium

Answer 1

So, in Scalaz 7 there's an implicit List to Monoid function which gives you back a Monoid[List[A]]. Monoid extends SemiGroup so we have List covered.

Seq does not get this special treatment. There's no implicit conversion from Seq to Monoid or Semigroup. There is an implicit IndexedSeq to Monoid, but this doesn't help us.

Why isn't there one for Seq? I don't know. Perhaps Seq violates some laws of monoids/semigroups so there is no conversion. It seems like there were issues with Seq in Scalaz 6 so they've removed some features: https://groups.google.com/forum/?fromgroups=#!searchin/scalaz/Seq/scalaz/Deaec1H11W4/gYFSquXjTzYJ

UPDATE

Looking at the scala doc it becomes more apparent why the scalaz folks went this way. List inherits LinearSeq which inherits Seq. IndexedSeq inherits Seq. If they were to provide a semigroup for Seq, it could override any other semigroup on IndexedSeq or LinearSeq and loose performance advantages between the two. If you look at the scalaz signatures for append you can see that they take advantage of these performance differences:

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/std/List.scala

  implicit def listMonoid[A]: Monoid[List[A]] = new Monoid[List[A]] {
    def append(f1: List[A], f2: => List[A]) = f1 ::: f2
    def zero: List[A] = Nil
  } 

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/std/IndexedSeq.scala

implicit def ixSqMonoid[A]: Monoid[IxSq[A]] = new Monoid[IxSq[A]] {
    def append(f1: IxSq[A], f2: => IxSq[A]) = f1 ++ f2
    def zero: IxSq[A] = empty
  }

If we dig deeper, we see that Seq only implements ++ which has worse performance on lists than ::: for append operations. So, to answer your second question, performance. If scalaz implemented semigroup for Seq it would most likely lead to ambiguous performance as you would only be able to optimize for indexed. Iterable has the same issue.

Weissman

Great answer to the question about where the one is for list. It seems all iterables should be at least semigroups... – Niobium

If you look at the scala doc, Seq is the base for LinearSeq and IndexedSeq which both have different performance differences. List inherits LinearSeq, so I can see why they had to choose List and IndexedSeq instead of Seq. I'll see if I can update this more concisely. – Weissman

In addition to what is already said here, you can have a look at this example: github.com/scalaz/scalaz/blob/… It uses Isomorphism to derive instances for Seq from a List. Use it at your own risk: as per Jason Zaugg, instances for Seq are dangerous. – Kryska