Why the order matters in Occurrences? Coursera-Scala

Question

I asked this question on Coursera, but no one replied, so I come here. It's about the last assignment(Anagrams) of the course Functional Programming Principles in Scala.

The last test in AnagramsSuite would fail if function subtract return an unordered Occurrences.

Also, it's required that function wordOccurrences should return a sorted Occurrences.

So, Why the order in Occurrences matters?

// sentenceAnagrams passes the Test
def subtract(x: Occurrences, y: Occurrences): Occurrences = ((y 
    foldLeft x.toMap)((result, current) => {
        result.updated(current._1, result(current._1)-current._2)
    }) filter (_._2>0)).toList.sortWith(_._1<_._1)

// Without sortWith, the sentenceAnagrams will fail to get the right answer
def subtract(x: Occurrences, y: Occurrences): Occurrences = ((y 
    foldLeft x.toMap)((result, current) => {
        result.updated(current._1, result(current._1)-current._2)
    }) filter (_._2>0)).toList

Answer 1

Because it's part of the definition:

  /** `Occurrences` is a `List` of pairs of characters and positive integers saying
   *  how often the character appears.
   *  This list is sorted alphabetically w.r.t. to the character in each pair.
   *  All characters in the occurrence list are lowercase.
   *  
   *  Any list of pairs of lowercase characters and their frequency which is not sorted
   *  is **not** an occurrence list.
   *  
   *  Note: If the frequency of some character is zero, then that character should not be
   *  in the list.
   */
  type Occurrences = List[(Char, Int)]

The List type is ordered. If instead they'd used Map (as it could have been), then this wouldn't be an issue.

Answer 2

Let me explain @Andy Hayden's answer more clearly.

The type of Occurrences is List. We use it to get word from Map dictionaryByOccurrences.

We get meaningful words by dictionaryByOccurrences(subsetOccurrences). If the Occurrences is not ordered, we can't get words from the dictionary. For example, if we get an unordered subset [('s', 1), ('c', 1), ('a', 2), ('l', 1)] through def combinations, we can't get word scala from dictionaryByOccurrences in which scala 's key may be [('a', 2), ('s', 1), ('c', 1), ('l', 1)]. These two lists are not the same.

In fact, dictionaryByOccurrences is wrong, in which anagrams would have different keys, if the Occurrences is not ordered.