Scala Syntax Help

[tatteredpotato]

I learned SML last semester and I've been trying to learn Scala and have started working through this site. Anyways I'm attempting to work with folds and tuples and option types and I'm not quite sure what I'm doing wrong in Scala:

/**
 * Eliminate consecutive duplicates of list elements.
 */
object problem08 {
	def main(args:Array[String]) = {
		val x = List('a','a','a','a','b','c','c','a','a','d','e','e','e','e')
		println("Compressed = " + compress(x))
	}
	
	def compress[A](list:List[A]):List[A] = {
		/**
		 * @param x The current element of the list.
		 * @param a The accumulated value; tuple of (Option[A],List[A])
		 */
		def fldr[B](x:B,a:(Option[B],List[B])):(Option[B],List[B]) = {
			val lst = a._2
			val last = a._1
			
			last match {
				case None		=>
					(Some(x),lst:::List(x))
				case Some(y)	=>
					if (x==y)
						a
					else
						(Some(x),lst:::List(x))
			}
		}
		list.foldRight (None,list) {fldr(_,_)}._2
	} 
}

The type-checker doesn't like my use of None in the initial value of the fold:

problem08.scala:29: error: type mismatch;
 found   : (Option[A], List[A])
 required: (object None, List[A])
		list.foldRight (None,list) {fldr(_,_)}._2

It seems to me that it's saying object None is not the same type as Option[A]. As I said I'm coming from SML so this is close to what I would write in SML.

EDIT: I realize now the tuple has redundant information... The option type will just be the element at the head of the list if I do the concatenation correctly, but I'm still curious about tuple accumulators on folds.

 

[dinkumthinkum]

This looks like a type error, not a syntax error. I don't really know anything about Scala, but I'm pretty familiar with parametric polymorphism and the consequences of mixing that with subtyping. It appears that the compiler is generalizing "None" and not unifying it with Option[A]. I made the following change and it successfully type-checks:

		list.foldRight (None:Option[A],list) {fldr(_,_)}._2

Subtyping makes type reconstruction undecidable in general, so you'll find that type inference algorithms often fall down when unifying subclasses and siblings like this, without some explicit guidance from the programmer. In other words, I think it wasn't able to figure out that "None" and "Some(x)" were supposed to both be the same "Option[A]" type.

Also:

		list.foldRight[(Option[A], List[A])] (None,list) {fldr(_,_)}._2

 

[tatteredpotato]

Thanks... that makes sense. SML made me lazy with regard to adding type information to my code.