6

我是函数式编程的新手，所以使用函数式方法似乎更难解决一些问题。

假设我有一个数字列表，例如 1 到 10.000，并且我想获取列表中的项目，其总和最多为一个数字 n（比如说 100）。所以，它会得到这些数字，直到它们的总和大于 100。

在命令式编程中，解决这个问题是微不足道的，因为我可以在每次交互中保留一个变量，一旦达到目标就停止。

但是我怎样才能在函数式编程中做同样的事情呢？由于 sum 函数对已完成的列表进行操作，而我仍然没有已完成的列表，我该如何“继续”计算？

如果 sum 是懒惰计算的，我可以写这样的东西：

           (1 to 10000).sum.takeWhile(_ < 100)

PS：即使任何答案都会受到赞赏，但我想要一个不会每次都计算总和的答案，因为显然命令式版本在速度方面会更加优化。

编辑：

我知道我可以将命令式循环方法“转换”为函数式递归函数。我更感兴趣的是找到一个现有的库函数是否可以为我提供一种方法，让我不必在每次需要某些东西时都编写一个。

4

4 回答 4

9

使用Stream.

scala> val ss = Stream.from(1).take(10000)
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> ss.scanLeft(0)(_ + _)
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res60.takeWhile(_ < 100).last
res61: Int = 91

编辑：

获取组件也不是很棘手。您可以这样做：

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) }
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?)

scala> res62.takeWhile(_._1 < 100).last
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13))

元组的第二部分是您想要的结果。

应该很明显，在这种情况下，构建向量是浪费的。相反，我们只能存储对 sum 有贡献的流中的最后一个数字。

scala> ss.scanLeft(0)(_ + _).zipWithIndex
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> res64.takeWhile(_._1 < 100).last._2
res65: Int = 13
于 2012-05-14T11:28:50.467 回答
1

我这样做的方法是递归。在每次通话时，添加下一个号码。您的基本情况是当总和大于 100 时，您会一直返回堆栈。您需要一个辅助函数来执行实际的递归，但这没什么大不了的。

于 2012-05-14T11:16:21.300 回答
1

使用“功能”方法也不难。
使用递归，而不是将您的状态保存在您变异的局部变量中，您将其保存在参数和返回值中。

因此，要返回总和最多为 的列表的最长初始部分N：

  1. 如果列表是空的，你就完成了；返回空列表。
  2. 如果列表的头部大于N，你就完成了；返回空列表。
  3. 否则，让我们H成为列表的头部。我们现在需要的是列表尾部
    的初始部分，其总和最多为，然后我们可以“cons”到该列表上，我们就完成了。 我们可以使用与到目前为止相同的过程递归地计算它，所以这是一个简单的步骤。N - HH

一个简单的伪代码解决方案：

sum_to (n, ls) = if isEmpty ls or n < (head ls)
                 then Nil
                 else (head ls) :: sum_to (n - head ls, tail ls)

sum_to(100, some_list)
于 2012-05-14T12:06:07.143 回答
0

所有只需要一次通过序列的序列操作都可以使用我们的 reduce 来实现，就像有时调用的那样。自从我习惯了函数式编程后，我发现自己经常使用折叠

所以这里奇怪的一种可能的方法使用一个空集合作为初始值并根据这个策略折叠给定已处理的集合和新值检查它们的总和是否足够低，如果然后将值花费到集合中，则什么都不做

该解决方案不是很有效，但我想强调以下地图折叠过滤器 zip 等是习惯函数式编程的方式尝试尽可能多地使用它们而不是循环构造或递归函数您的代码将更具声明性和功能性

于 2012-05-15T18:29:49.937 回答