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

Question

我一直在尝试学习函数式编程，但我仍然难以像函数式程序员一样思考。一个这样的挂断是如何实现强烈依赖 loops/order-of-execution.

的索引密集型操作

例如，考虑以下 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 等）中会是什么样子？我一直在学习 monad 并认为它们在这里可能是相关的，但我的理解仍然不是很好。

Answer 1

这不是 index-heavy 操作，实际上您可以使用 one-liner 和 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 and vector packages.

中定义的数据结构

Answer 2

信不信由你，那个函数实际上是built-in到Haskell。

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

所以广泛的答案通常是：有方便的 list-related 原语，我们可以从中构建而不是手动编写循环。人们喜欢说递归是 FP 中最接近命令式编程中“for 循环”的类比。虽然这可能是正确的，但与普通命令式程序使用的循环相比，普通函数式程序使用 lot 更少显式递归。我们所做的大部分事情（尤其是列表）都是由 map、filter、foldl 和 [=22= 中的所有其他 (highly-optimized) 好东西组成的]，以及 base.

的其余部分

至于我们如何实现那些功能，你可以查看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 3

这不是 Haskell 答案，但你标记了问题 lisp 所以这是 Racket 中的一个答案：这既是完整的功能，又表明你不需要索引问题。

这个函数的作用是获取数字流和 return 它的前缀流。这都是偷懒做的。

(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]) returns [1 3 6 10 15 21 28 36 45]

在 Clojure 中，数据通常是不可变的（无法修改）。在这种情况下，函数 assoc 采用一个向量，returns 一个与原始向量类似的新向量，但 i^th 元素发生了变化。这听起来可能效率低下，但底层数据结构允许更新在接近恒定的时间内完成 (O(log₃₂(n))) .

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

Answer 5

我知道你问过函数式语言，但我只是想不请自来地插话一下 Python，作为一种 multi-paradigm 语言，它也有很好的 higher-order itertools.accumulate函数。

Accumulate 采用一个集合和 returns 其部分和的迭代器，或任何自定义二元函数。与您的示例等效的功能 Python 代码只是：

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

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

Answer 6

此功能也称为“累计和”，另一种 Python 方法是使用 numpy（用 C 编写，速度超快）：

nums = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) # or np.arange(1, 10) or np.arange(9)+1
print(nums.cumsum())

输出：

[1, 3, 6, 10, 15, 21, 28, 36, 45]

Answer 7

其他人指出，您的特定示例可以用 scanl 等函数很好地处理，所以让我们看看更广泛的问题“index-heavy 强烈依赖 loops/order-of-execution 的操作”。我们可以将问题分解为三个问题：

索引
循环播放
突变

只要索引的概念有意义，就支持对数据结构进行索引。例如，List 和 Vector 都支持索引。正如其他人指出的那样，如果您的索引是随机的，Vector 会有更好的性能，但这种情况非常罕见。

命令式循环可以直接替换为递归函数（参见 Wikipedia) although there are so many "higher-order functions" (functions that take functions as arguments) implemented in Prelude and standard libraries that you will need explicit recursion rarely. scanl is an example of this. It allows you to avoid an explicit recursive call by farming it out to a prewritten function. That function, however, is defined recursively。编译器在生成机器代码时可能会优化递归到循环中。

最后，您可能有一个数字数组，并且真的非常想通过一系列步骤改变数组中的值。这个线程中的每个人，包括我，都会非常努力地说服你不要这样做，让你以更“实用”的方式思考。但是如果我们失败了那么你可以使用 state thread monad. This gives you a way to mutate your data structures locally (scary) within a function while interacting with things outside the function only with immutable (not scary) data structures and hence ensures that the function is referentially transparent.

Answer 8

Elixir 中有 built-in 个函数类似于 Haskell 的函数：Enum.scan/2 和 Enum.scan/3:

Enum.scan(1..9, 0, fn element, acc -> element + acc end) |> IO.inspect()
# yields:
# [1, 3, 6, 10, 15, 21, 28, 36, 45]

当您第一次从面向对象的思维方式切换到函数式思维方式时，可能很难放弃索引，但我发现几乎所有以前我会寻求索引解决方案的问题（例如 for next 循环）在 map 或 reduce 函数或某种形式的尾递归中有一个优雅的对应物。

例如，您可以使用 tail-recursion 和手动累加器构建自己的函数来处理此操作：

defmodule Foo do
  def bar(nums, acc \ [])

  # We've reached the end of input: return the accumulator (reversed)
  def bar([], acc), do: Enum.reverse(acc)

  # The very first call is special because we do not have a previous value
  def bar([x | tail], []) do
    bar(tail, [x])
  end

  # All other calls land here
  def bar([x | tail], [prev | _] = acc) do
    bar(tail, [x + prev | acc])
  end
end


nums =   [1, 2, 3, 4,  5,  6,  7,  8,  9]
prefix = Foo.bar(nums)
IO.inspect(prefix)

# Yields the same result:
# [1, 3, 6, 10, 15, 21, 28, 36, 45]

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

How do purely functional languages handle index-based algorithms?

lisp

haskell

functional-programming