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

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的答案，但您标记了问题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认为Naturals从0开始，这是正确的。）

Answer 2

这不是一个索引繁重的操作，事实上，您可以使用一个带有scanl1:：（a-

prefixList = scanl1 (+)

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

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

scanl1将原始列表中的第一项作为累加器的初始值，并生成该初始值。然后每次它都将累加器和给定列表中的下一项相加为新累加器，并生成新的累加器值。

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

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

Answer 3

信不信由你，这个函数实际上是Haskell内置的。

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

因此，大致的答案通常是：有一些方便的与列表相关的原语，我们可以用它们来构建，而不是手工编写循环。人们喜欢说递归在FP中与命令式编程中的“for循环”最相似。虽然这可能是真的，但与命令式程序用于循环的平均递归相比，普通函数式程序使用的显式递归要少得多。我们所做的大部分工作（尤其是列表）都是由map、filter、foldl，以及数据中所有其他（高度优化的）好东西组成的。列出，数据。可折叠的，数据。可遍历的，以及基础的其余部分。

至于我们如何实现这些函数，您可以查看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%的情况下，答案是“停止思考索引”。