scala: implement a generic recursive max function
Solution 1
Maybe you want the Ordering
type class?
def max[T: Ordering](list: List[T]): T = list match {
case Nil => throw new RuntimeException("maximum of empty list")
case head :: Nil => head
case list =>
val maxTail = max(list.tail)
if (implicitly[Ordering[T]].gt(list.head, maxTail)) list.head else maxTail
}
This is, after all, how the built-in max
method works:
// From GenTraversableOnce
def max[A1 >: A](implicit ord: Ordering[A1]): A
You can clean things up a lot if you do this:
def max[T](list: List[T])(implicit ord: Ordering[T]): T = list match {
case Nil => throw new RuntimeException("maximum of empty list")
case head :: Nil => head
case head :: tail => ord.max(head, max(tail))
}
Or, you can make it tail-recursive for increased efficiency (because the compiler will optimize it):
def max[T](list: List[T])(implicit ord: Ordering[T]): T = {
if (list.isEmpty)
throw new RuntimeException("maximum of empty list")
@tailrec
def inner(list: List[T], currMax: T): T =
list match {
case Nil => currMax
case head :: tail => inner(tail, ord.max(head, currMax))
}
inner(list.tail, list.head)
}
Also, you should throw RuntimeException
or a subclass of it, not Error
.
Solution 2
Went through a similar exercise as the OP sans pattern matching and generic types, and came up with the following:
def max(xs: List[Int]): Int = {
if (xs.isEmpty) throw new NoSuchElementException
if (xs.length == 1)
return xs.head
else
return max(xs.head, max(xs.tail))
}
def max(x: Int, y: Int): Int = if (x > y) x else y
Solution 3
I have just come up with this solution.
def max(xs: List[Int]): Int = {
if (xs.isEmpty) 0
else {
if( xs.head >= max(xs.tail) ) xs.head
else max(xs.tail)
}
}
Solution 4
I came up with quite a simple solution which is easy to understand. It caters for an empty list, a list with only one element, and negative numbers.
def max(xs: List[Int]): Int = {
if (xs.isEmpty) throw new NoSuchElementException
else {
def inner(max: Int, list: List[Int]): Int = {
def compare(x: Int, y: Int): Int =
if (x > y) x
else y
if (list.isEmpty) max
else inner(compare(max, list.head), list.tail)
}
inner(xs.head, xs.tail)
}
}
opensas
Updated on August 27, 2020Comments
-
opensas over 3 years
I'm trying to port this haskell max function implementation to scala
maximum' :: (Ord a) => [a] -> a maximum' [] = error "maximum of empty list" maximum' [x] = x maximum' (x:xs) = max x (maximum' xs)
This is my first attempt:
def max[T <: Ordered[T]](list: List[T]): T = list match { case Nil => throw new Error("maximum of empty list") case head :: Nil => head case list => { val maxTail = max(list.tail) if (list.head > maxTail) list.head else maxTail } } max(List[Int](3,4))
But I get the following error:
inferred type arguments [Int] do not conform to method max's type parameter bounds [T <: Ordered[T]]
I tried with ordering, comprable, etc with similar results...
Any idea about what's missing?
-
opensas over 11 years+1 for having a look at the source... (I still don't have enough courage... use the source!!!)
-
opensas over 11 yearsI guess using ord.max would be like cheating, I'm doing it just for educational purposes... anyway, I created a maxElement helper function to avoid that val in there...
-
dhg over 11 years
ord.max
is different fromList.max
. One is basically an operator that compares two things while the other is a method of an entire collection. They just happen to have the same name. -
opensas about 11 yearsI think this is not a generic solution
-
eomeroff about 11 years@opensas No, but I wonted to attach it to the most relevant question, currently this is the one.
-
supermasher over 10 years@eomeroff Close, but your solution doesn't work for negative numbers (try
max(List(-3, -7, -2)
). This can be resolved by modifying the secondif
toif( xs.tail.isEmpty || xs.head >= max(xs.tail) )
. -
supermasher over 10 years@eomeroff No probs, perhaps you can update your answer to help somebody else. You should also throw an exception if the list is empty, as 0 is incorrect (max can also be negative).
-
fkoksal about 7 years> return max(xs.head, max(xs.tail)) You can not make this call, as you don't have any function max(x: Int, xs: List[Int]) defined.
-
jwvh over 5 yearsRelatively simple, true, but massively inefficient. A small
List
of only 7 elements, with the max element at the end, will recurse 126 times. Change it to 8 elements and it recurses 254 times, approximately doubling for each (smaller) element added (before the end). -
jwvh about 5 yearsThis isn't recursive, which is what was asked for (6 years ago).
-
jwvh over 4 yearsUnfortunately this is not generic, as requested in the title, and it doesn't work. For lists of two or more elements it is infinitely recursive.