scala: implement a generic recursive max function

Question

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?

dejon97 · Accepted Answer · 2014-04-26 18:34:05Z

21

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

answered Apr 26, 2014 at 18:34

dejon97

2972 silver badges4 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

fkoksal Over a year ago

> 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.

dhg · Accepted Answer · 2012-09-20 06:15:54Z

18

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.

edited Sep 20, 2012 at 6:15

answered Sep 20, 2012 at 5:58

dhg

52.8k8 gold badges125 silver badges144 bronze badges

3 Comments

opensas Over a year ago

+1 for having a look at the source... (I still don't have enough courage... use the source!!!)

opensas Over a year ago

I 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 a year ago

ord.max is different from List.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.

eomeroff · Accepted Answer · 2013-03-30 00:10:26Z

6

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)
    }
}

answered Mar 30, 2013 at 0:10

eomeroff

9,99530 gold badges102 silver badges143 bronze badges

4 Comments

opensas Over a year ago

I think this is not a generic solution

eomeroff Over a year ago

@opensas No, but I wonted to attach it to the most relevant question, currently this is the one.

supermasher Over a year ago

@eomeroff Close, but your solution doesn't work for negative numbers (try max(List(-3, -7, -2)). This can be resolved by modifying the second if to if( xs.tail.isEmpty || xs.head >= max(xs.tail) ).

supermasher Over a year ago

@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).

Hegemon · Accepted Answer · 2013-11-07 14:11:07Z

2

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)
  } 
}

edited Nov 7, 2013 at 14:11

answered Nov 7, 2013 at 14:00

Hegemon

4337 silver badges21 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 12:17:36Z

0

Oops, shoulda look better before asking

I found the answer in this thread: https://stackoverflow.com/a/691674/47633

It seems like Haskell's type classes are implemented using implicits in scala (like in dhg's example)

so it ends up like this:

def max[T](list: List[T])(implicit f: T => Ordered[T]): T = {

 def maxElement(value1: T, value2: T): T = if (value1 > value2) value1 else value2

 list match {
    case Nil => throw new Error("empty list found")
    case head :: Nil => head
    case list => maxElement(list.head, max(list.tail))
  }
}

or with some syntactic sugar, just

def max[T <% Ordered[T]](list: List[T]): T = list match {

Still, I think the compiler has enough information to do it by himself...

ps: I prettied up a little bit the function...

edited May 23, 2017 at 12:17

CommunityBot

11 silver badge

answered Sep 20, 2012 at 6:04

opensas

64.4k91 gold badges268 silver badges422 bronze badges

Comments

flydes · Accepted Answer · 2018-07-05 20:40:11Z

def genFunc[A](a1: A, a2: A)(f:(A, A) => Boolean):A = if (f(a1, a2)) a1 else a2
def min[A : Ordering] = (a1: A, a2: A) => implicitly[Ordering[A]].lt(a1, a2)
def max[A : Ordering] = (a1: A, a2: A) => implicitly[Ordering[A]].gt(a1, a2)

List(1,2,8,3,4,6,0).reduce(genFunc(_,_)(min))
List(1,2,8,3,4,6,0).reduce(genFunc(_,_)(max))

or if need only function max with tail recursion and the type Option[_] does not break the referential transparency

def max[A: Ordering](list: List[A]): Option[A] = list match {
  case Nil => None
  case h :: Nil => Some(h)
  case h :: t => if(implicitly[Ordering[A]].gt(h, t.head)) max(h :: t.tail) else max(t)
}

max(List(1,2,8,3,4,6,0)).getOrElse("List is empty") // 8: Any
max(List()).getOrElse("List is empty")              // List is empty: Any

Hind Ahmad · Accepted Answer · 2019-01-17 14:34:54Z

0

this is the simplest way I could come up with:

def max(xs: List[Int]): Int = { if (xs.length == 1) xs.head

else if(xs.isEmpty) throw new NoSuchElementException

else if(xs.head > max(xs.tail))  xs.head

else max(xs.tail)}  }

answered Jan 17, 2019 at 14:34

Hind Ahmad

311 gold badge1 silver badge3 bronze badges

1 Comment

jwvh Over a year ago

Relatively 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).

Jen · Accepted Answer · 2019-08-26 19:29:26Z

0

this works

def max(xs: List[Int]): Int = xs match{
  case Nil => 0
  case head :: Nil => head
  case head :: tail => max(List(head, max(tail)))
}

answered Aug 26, 2019 at 19:29

Jen

11 bronze badge

1 Comment

jwvh Over a year ago

Unfortunately 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.

Buggi · Accepted Answer · 2019-03-05 08:55:12Z

-1

My solve:

  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) 0
    else xs.max
  }

answered Mar 5, 2019 at 8:55

Buggi

1

1 Comment

jwvh Over a year ago

This isn't recursive, which is what was asked for (6 years ago).

Collectives™ on Stack Overflow

scala: implement a generic recursive max function

9 Answers 9

1 Comment

3 Comments

4 Comments

Comments

Comments

Comments

1 Comment

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

1 Comment

3 Comments

4 Comments

Comments

Comments

Comments

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related