做“最大”（与递归/无可变VARS）的功能性的方式

与命令性代码未排序阵列查找max是相当直截了当做“最大”（与递归/无可变VARS）的功能性的方式

例如在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; 
    } 
}

这样做的功能性方法是什么？例如

没有可变的变量（例如使最大在斯卡拉中的Java/final一个val）
没有循环（如使用递归，尾首选）

在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可用做/ implemente d（我不希望/不能实现它，出于某种原因，即我正在使用普通的Java）

什么是“惯用”功能方式来做一个最大值而不依赖于其他功能方法（例如我将如何实现它在裸露的骨头的Java的例子，但在考虑到功能范式）

答案可以用任何语言（Java /斯卡拉虽然首选）

来源

2013-04-22 Eran Medan

这是一个尾调用递归执行与累加器为最大值。

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

}

来源

2013-04-22 21:43:48 maba

我会使空列表的最大值是一个错误，而不是'Integer.MIN_VALUE'，就像Scala版本中的reduce一样。 – ataylor 2013-04-22 22:08:51

@ataylor我同意，但此代码片段更像是一个插图，而不是生产就绪交付物。 – maba 2013-04-22 22:14:16

谢谢！我的眼睛已经关闭到目前为止:) p.s.令人惊讶的是，这是所以在斯卡拉小得多（根据您的答案）： '高清MAX（名单：名单[INT]）= { \t maxAcc（列表，Int.MinValue） } 高清maxAcc（名单：名单[INT]，curMax：智力）：INT = { \t列表匹配{ \t \t情况下无=> curMax \t \t壳头::尾=> maxAcc（尾，如果（头> curMax）头别的curMax） \t} }' – 2013-04-22 22:15:19

你可以用一个简单的递归但马坝的尾递归版本做它应该有更好的表现。

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

来源

2013-04-22 21:53:32 pt2121

基于马坝的出色答卷这里是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) 
    } 
    }

编辑：2009年，由于@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) 
    }

来源

2013-04-22 22:21:41

做“最大”（与递归/无可变VARS）的功能性的方式

回答

相关问题