将Haskell函数转换为java"函数"

Question

我在Haskell中有这个函数,我想知道如何将它转换为Java,特别是使用流:

build = [(w,m,n,g) | w <- [240..1280], m <- [2,4..20], n <- [2..100], g <- [240..1280], ((w - 2*m - n*g) `mod` (n+1) == 0), n*g+2*m <= w, n*g <= w]

Answer 1

(我不是Haskell专家,但我知道这很危险.)

给出的示例代码有几个Haskell结构,可以很好地映射到Java构造中:

• Haskell列表是惰性的,因此它对应于Java Stream.

• 使用的范围是整数,因此它们对应于IntStream.例如,[240..1280]对应于IntStream.rangeClosed(240, 1280).

• 带步长的范围在Java中没有直接对应关系,但可以很容易地计算出来; 你只需要做一些算术运算,然后将顺序范围内的值映射到带步骤的值.例如,[2, 4..20] 可以写成

  IntStream.rangeClosed(1, 10).map(i -> 2 * i)
  

• 列表理解的条件对应于通过谓词过滤流.

• 对多个生成器的理解对应于嵌套流的平面映射.

• 在Java中没有通用的方法来表示元组.各种第三方库提供了关于泛型和装箱的不同权衡的元组实现.或者,您可以使用所需的字段编写自己的类.(但是如果使用许多不同类型的元组,这可能会非常繁琐.)在这种情况下,元组只有四个整数,因此可以使用带有四个元素的int数组轻松表示.

总而言之,我们得到以下内容.

static Stream<int[]> build() {
    return IntStream.rangeClosed(240, 1280).boxed()
               .flatMap(w -> IntStream.rangeClosed(1, 10).map(m -> 2 * m).boxed()
                   .flatMap(m -> IntStream.rangeClosed(2, 100).boxed()
                       .flatMap(n -> IntStream.rangeClosed(240, 1280)
                                              .filter(g -> ((w - 2*m - n*g) % (n+1) == 0))
                                              .filter(g -> n*g+2*m <= w)
                                              .filter(g -> n*g <= w)
                                              .mapToObj(g -> new int[] { w, m, n, g }))));
}

与原始的Haskell相比,这显然非常冗长,但您可以很容易地看到Haskell结构在Java代码中的最终位置.我相信这是正确的,因为它似乎生成与Haskell代码相同的输出.

请注意,我们正在使用生成值,IntStream但我们希望flatmap提供一个数组流(它们是对象),而IntStream.flatMap返回一个IntStream.也许理想情况下会有一个flatMapToObj操作,但是没有,所以我们必须将int值打包到一个Integer对象然后调用Stream.flatMap它.

可以将流管道分配给Stream类型的变量,但这不是很方便,因为Java流最多可以使用一次.由于构造这样的流很便宜(与评估它相比),编写一个build()返回新创建的流的函数是合理的,准备由调用者进行评估.

运行以下Java代码时

    System.out.println(build().count());
    System.out.println(build().findFirst().map(Arrays::toString).orElse("not found"));
    System.out.println(build().reduce((a, b) -> b).map(Arrays::toString).orElse("not found"));

结果是:

654559
[484, 2, 2, 240]
[1280, 20, 5, 248]

运行以下Haskell代码(build从问题中复制定义)

build = [(w,m,n,g) | w <- [240..1280], m <- [2,4..20], n <- [2..100], g <- [240..1280],
                     ((w - 2*m - n*g) `mod` (n+1) == 0), n*g+2*m <= w, n*g <= w]

main = do
    print (length build)
    print (head build)
    print (last build)

给出以下输出:

654559
(484,2,2,240)
(1280,20,5,248)

所以音译在我看来是正确的.

为时代head(在Java中findFirst)和last(在Java中reduce((a, b) -> b))操作如下:(GHC使用7.6.3更新-02)

       head     last
GHC      8s      36s
JDK      3s       9s

这至少表明两个系统都提供了懒惰,因为在找到第一个元素之后计算被短路,而找到最后一个元素则需要计算所有元素.

有趣的是,在Haskell,呼吁所有三个length,head和last不采取任何更多的时间不仅仅是调用last(约36秒),大概是因为记忆化的.Java中没有memoization,但当然你可以将结果显式地存储在一个数组或List中并多次处理.

但总的来说,我对Java实现的速度有多惊讶.我并不真正理解Haskell的性能,所以我将把它留给Haskell专家来评论.我很可能做错了,虽然大多数情况下我只是将问题中的函数复制到文件中并使用GHC进行编译.

我的环境:

JDK 9,GHC 7.6.3 -O2,MacBook Pro 2014年中期2核3GHz Intel Core i7