It's actually not the sortedness of the map that we care about, it really doesn't matter whether the headers are sorted or not.  It's the case insensitivity.  The reason a sorted map is being used is an implementation detail (it's the only type of map in the Scala collections API that allows you to arbitrarily define the equality of keys).  The comparator is important, but not because we want a sorted map, it's because we want a case insensitive map.

I'm not sure what your point is about mixing in traits... if I had:

```scala
trait CaseSensitiveMap extends Map
```

That's easy, but then I can't assign anything to that type, because there's no implementation of it.  And if I had a constructor that accepted it, eg:

```scala
case class ResponseHeader(status: Int, headers: CaseInsensitiveMap)
```

I couldn't construct it with this:

```scala
ResponseHeader(200, Map("foo" -> "bar"))
```

I would have to provide my own `CaseInsensitiveMap` companion object - mixing in traits doesn't help there.