Should be pretty simple:
scala> def reverse[T](l: List[T]) : List[T] = l match {
| case Nil => Nil
| case h::Nil => h
| case h::t => reverse(t)::h
| }
:7: error: value :: is not a member of T
case h::t => reverse(t)::h
^
Hmmm, :: isn’t the List append operator. Lets try +
scala> def reverse[T](l: List[T]) : List[T] = l match {
case Nil => Nil
case h::Nil => List(h)
case h::t => reverse(t)+h
}
| | | | warning: there were deprecation warnings; re-run with -deprecation for details
reverse: [T](List[T])List[T]
scala> reverse(List())
res13: List[Nothing] = List()
scala> reverse(List(1))
res14: List[Int] = List(1)
scala> reverse(List(1,2,3,4,5,6))
res15: List[Int] = List(6, 5, 4, 3, 2, 1)
Voilá, but what about the deprecation warnings?
It looks like + was deprecated, so I again asked on the Scala IRC channel about it, but nobody seemed to have a definitive answer why it was deprecated. Someone did suggestion using ::: instead, and cautioned that it associates right-to-left. Normally, when you see a+b it means a.+(b), which is like saying a.add(b) in Java. That’s because operators are left associative, meaning they are a function of the parameter on the left. Being right-associative, ::: associates with the parameter with on the right, so a:::b means b.:::(a), which you might read as b.append(a), if you were reading Java. It took a bit of searching in the Scala Language Reference to find out why:
The associativity of an operator is determined by the operator’s last character. Operators ending in a colon ‘:’ are right-associative. All other operators are left-associative. (6.12.3 Infix Operations)
So, in fact a:::b is not the “append” operation on a, but the “prepend” operation on b. This is also true for ::.
Note that + takes a List[T] and appends an element of type T, but ::: tales two parameters of type List[T], so we’ll have to wrap the matched head element in a List.
So let’s try changing + to :::, and at the time see if we can’t shorten up our solution, since reverse(t), when t is Nil, is still Nil.
scala> def reverse[T](l: List[T]) : List[T] = l match {
case Nil => Nil
case h::t => reverse(t):::List(h)
}
reverse: [T](List[T])List[T]
scala> reverse(List(1,2,3,4,5,6,7))
res24: List[Int] = List(7, 6, 5, 4, 3, 2, 1)
scala> reverse(List(1))
res25: List[Int] = List(1)
scala> reverse(List())
res26: List[Nothing] = List()
Very nice.
The first answer is identical to our own, but there are two more answers. Answer two is the “tail recursive” version as per the previous post.
The third answer, however, is labelled as “Pure functional”:
def reverse[T](l: List[T]): List[T] = l.foldLeft(List[T]())((r, h) => h :: r)
Wow, I have no idea how to read that!
AND, I thought my answers were functional, but they are not functional enough!
According to the docs, foldLeft is defined as
Combines the elements of this list together using the binary function f, from left to right, and starting with the value z.
I take this to mean that if you have List(a, b, c, d) and the binary function +, then fold left means ((a+b)+c)+d).
So List[T]() is the type of the binary function which we want to use, and it returns a List[T]. At the end of the def is ((r, h) => h :: r), which is the definition of the binary function. Since r and h are swapped and appended, lets call this function swap. So folding left with a swap on List(a,b,c,d), we get:
((a swap b) swap c) swap d)
((b, a) swap c) swap d)
((c, b, a) swap d)
(d, c, b, a)
And again we have a reversed List!
So even though it was an easy exercise, we learned that a trailing colon on an operator means it associates right, and we learned how to pass functions to other functions!
99 Problems in Scala 