纯函数式语言如何处理基于索引的算法？

Question

我一直在尝试学习函数式编程，但我仍然很难像函数式程序员一样思考。其中一个难题是如何实现强烈依赖于循环/执行顺序的索引密集型操作。

例如，考虑以下 Java 代码：

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1,2,3,4,5,6,7,8,9);
        System.out.println("Nums:\t"+ nums);
        System.out.println("Prefix:\t"+prefixList(nums));
    }
  
    private static List<Integer> prefixList(List<Integer> nums){
      List<Integer> prefix = new ArrayList<>(nums);
      for(int i = 1; i < prefix.size(); ++i)
        prefix.set(i, prefix.get(i) + prefix.get(i-1));
      return prefix;
    }
}
/*
System.out: 
Nums:   [1, 2, 3, 4, 5, 6, 7, 8, 9]
Prefix: [1, 3, 6, 10, 15, 21, 28, 36, 45]
*/

这里，在prefixList函数中，首先克隆 nums 列表，然后对其执行迭代操作，其中索引 i 上的值依赖于索引 i-1 （即需要执行顺序）。然后返回这个值。

这在函数式语言（Haskell、Lisp 等）中会是什么样子？我一直在学习单子并认为它们可能与这里相关，但我的理解仍然不是很好。

Answer 1

不管你相信与否，该函数实际上是Haskell内置的。

> scanl (+) 0 [1..9]
[0,1,3,6,10,15,21,28,36,45]

因此，广泛的答案通常是：有一些方便的与列表相关的原语，我们可以从中构建而不是手动编写循环。人们喜欢说递归是 FP 中最接近命令式编程中“for 循环”的类比。虽然这可能是真的，但一般的函数式程序使用的显式递归比一般的命令式程序使用的 for 循环要少得多。map我们所做的大部分工作（尤其是列表）都是由、filter、以及、、 和 的其余部分中foldl的所有其他（高度优化的）好东西组成的。Data.ListData.FoldableData.Traversablebase

至于我们如何实现这些功能，你可以看一下源码scanl。出于效率原因，GHC 的写法有点不同，但基本要点是这样的

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl _ q [] = [q]
scanl f a (b:xs) = a : scanl f (f a b) xs

你不需要索引。您需要在构建列表时跟踪单个先前的值，我们可以使用函数参数来做到这一点。如果您确实有一个需要随机访问各种索引的算法，我们就有Data.Vector。但 99% 的情况下，答案是“停止考虑指数”。

Answer 2

这不是一个索引繁重的操作，事实上您可以使用以下命令来完成此操作scanl1 :: (a -> a -> a) -> [a] -> [a]：

prefixList = scanl1 (+)

事实上，对于 的列表Nums，我们得到：

Prelude> prefixList [1 .. 9]
[1,3,6,10,15,21,28,36,45]

scanl1将原始列表的第一项作为累加器的初始值，并产生该值。然后每次它都会获取累加器和给定列表的下一项，并将它们求和为新的累加器，并产生新的累加器值。

通常不需要索引，但枚举列表就足够了。命令式编程语言通常使用for带索引的循环，但在许多情况下，这些循环可以替换为foreach不考虑索引的循环。在 Haskell 中，这通常也有助于使算法变得更加懒惰。

如果您确实需要随机访问查找，您可以使用array和vector包中定义的数据结构。

Answer 3

这不是 Haskell 的答案，但您标记了问题，lisp因此这是 Racket 中的答案：这既完全实用，又表明您不需要索引来解决此问题。

该函数的作用是获取数字流并返回其前缀流。这一切都是懒惰地完成的。

(define (prefix-stream s)
  (let ps-loop ([st s]
                [p 0])
    (if (stream-empty? st)
        empty-stream
        (let ([np (+ p (stream-first st))])
          (stream-cons 
              np 
              (ps-loop 
                  (stream-rest st)
                  np))))))

所以现在

> (stream->list (prefix-stream (in-range 1 10)))
'(1 3 6 10 15 21 28 36 45)

但当然你也可以这样做：

> (prefix-stream (in-naturals))
#<stream>

这显然不是可以转换为列表的流，但您可以查看其中的部分内容：

(stream->list (stream-take (prefix-stream (in-naturals)) 10))
'(0 1 3 6 10 15 21 28 36 45)
> (stream->list (stream-take (stream-tail (prefix-stream (in-naturals)) 1000) 10))
'(500500 501501 502503 503506 504510 505515 506521 507528 508536 509545)

（请注意，in-naturals考虑自然数从 0 开始，这是正确且正确的。）

Answer 4

在 Clojure 中，这可以写成：

(defn prefix-list [nums]
  (loop [i 1
         prefix nums]
    (if (= i (count nums))
      prefix
      (recur (inc i) (assoc prefix i (+ (get prefix i) (get prefix (dec i))))))))

(prefix-list [1 2 3 4 5 6 7 8 9])回报[1 3 6 10 15 21 28 36 45]

在 Clojure 中，数据通常是不可变的（无法修改）。本例中的函数assoc接受一个向量，并返回一个与原始向量类似的新向量，但第i^{th 个}元素已更改。这听起来可能效率低下，但底层数据结构允许在接近恒定的时间内完成更新 ( O (log ₃₂ (n)))。

正如其他人指出的那样，这个特定问题可以在不使用索引向量的情况下进行编码，但我正在努力提供一个适合使用索引数组的原始 Java 代码的解决方案。

Answer 5

我知道你问过关于函数式语言的问题，但我只是想顺便提一下，Python 作为一种多范式语言，也有一个很好的高阶itertools.accumulate函数。

Accumulate接受一个集合并返回其部分和的迭代器或任何自定义二进制函数。与您的示例等效的功能性 Python 代码如下：

from itertools import accumulate
print(list(accumulate(range(1, 10))))

一般来说，Python itertools和functools标准库模块为函数式编程提供了出色的工具。