问执行"max“的功能方法(使用递归/不带可变vars)
EN

Stack Overflow用户

提问于 2013-04-22 13:33:36

回答 3查看 374关注 0票数 2

在带有命令式代码的未排序数组中查找max是非常直接的。

例如在Java中(我确信它可以写得更好，只用于说明)

public class Main {
    public static void main(String[] args) {
        int[] array = {1,3,5,4,2};
        int max = findMax(array);
        System.out.println(max);
    }

    public static int findMax(int[] array){
        int max = Integer.MIN_VALUE; //or array[0], but it requires a null check and I want to keep it simple :)
        for (int i = 0, size = array.length; i < size ; i++) {
            int current = array[i];
            if(current > max) max = current;
        }
        return max;
    }
}

它的功能方式是什么？例如：

没有可变变量(例如，让max成为Scala中的val /Java中的final )
没有循环(例如使用递归，尾优先)

在Scala的源代码中，我看到它是使用recudeLeft完成的，这看起来很聪明

  def max[B >: A](implicit cmp: Ordering[B]): A = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.max")

    reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
  }

但是，假设我没有(由于某种原因)减少/ reduceLeft可用/实现(而且我不想/由于某种原因不能实现它，也就是说，我正在使用普通Java)

在不依赖其他功能方法的情况下，实现最大化的“惯用”功能方法是什么(例如，我将如何在最基本的Java中实现它，但要考虑函数范例)

任何语言都可以给出答案(Java / Scala优先)

functional-programming

java

scala

回答 3

Stack Overflow用户

回答已采纳

发布于 2013-04-22 13:43:48

这是一个带有最大值累加器的尾调用递归实现。

public class Main {

    public static void main(String[] args) {
        System.out.println(max(new int[]{6, 3, 9, 4}));
    }

    public static int max(int[] ints) {
        return max(ints, Integer.MIN_VALUE);
    }

    public static int max(int[] ints, int max) {
        if (ints.length == 0) {
            return max;
        } else {
            return max(Arrays.copyOfRange(ints, 1, ints.length), ints[0] > max ? ints[0] : max);
        }
    }

}

票数 4

Stack Overflow用户

发布于 2013-04-22 13:53:32

您可以使用简单的递归来完成它，但是maba的尾递归版本应该具有更好的性能。

import java.util.Arrays;
public class TestMax {
public static int findMax(int[] array) {
    if(array.length == 1)
        return array[0];
    int[] newArray = Arrays.copyOfRange(array, 1, array.length);
    if(array[0] > findMax(newArray))
        return array[0];
    else
        return findMax(newArray);
}
/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = {1,3,5,4,2, 9};
    int max = findMax(array);
    System.out.println(max);
}
}

票数 1

Stack Overflow用户

发布于 2013-04-22 14:21:41

基于maba的优秀答案，这里是Scala版本，如果有人感兴趣的话

  def max(list: List[Int]) = {
    maxAcc(list, Int.MinValue)
  }                                               

  def maxAcc(list: List[Int], curMax:Int):Int = {
    list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax ) head else curMax )
    }
  }

编辑：感谢maba对@tailrec的评论-以下是修改后的版本

 def max(list: List[Int]) = {
    @tailrec def maxAcc(list: List[Int], curMax: Int): Int = {
      list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax) head else curMax)
      }
    }
    maxAcc(list, Int.MinValue)
  }