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

Question

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

50

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

例如，考虑以下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 等）中，会是什么样子呢？我一直在学习关于单子的知识，认为它们可能与此相关，但我的理解还不够好。

- AaronC

23

如下所指出的，这并不是需要使用索引的例子。实际上，许多常见算法不需要索引。但是，有些算法确实需要：例如，计算序列0，a[0]，a[a[0]]，a[a[a[0]]]，...需要随机访问（除了假设所有元素都是有效索引之外）。在这些罕见的情况下，我们会采用数组，例如Data.Vector。当需要时，Haskell可以用于命令式编程--只是我们很少需要这样做。 - chi

3

你的问题是关于在任何函数式语言中实现你的算法，还是只是关于仅使用 ADT（例如如何将 Haskell 的 List 实现为链表）？有一些函数式语言拥有不是 ADT 的值类型，例如 Swift 的 Array 或者 Haskell 的 Vector（如上所述），尽管后者不支持 O(1) 更新。 - Feuermurmel

13

你的实现已经非常完美地运作了。prefixList() 只依赖于传入其参数的数据，而且除了返回值之外没有任何影响。这就是“纯函数”的本质。当然，有些编程语言比其他语言更容易编写函数式代码，我会将 Java 的函数式编程能力评为 10 分中的 4.5 分。 - Feuermurmel

1

@Feuermurmel 我的问题与我提供的前缀算法示例不太相关。我正在尝试学习如何应用思考模式，以摆脱总是使用索引的习惯。 - AaronC

@AaronC 当然，这是一个公平的目标，试图通过整个列表的转换来实现算法，而不是显式地按索引访问单个元素！让我困扰的是标题，因为它暗示函数式语言本身无法处理基于索引的算法。 - Feuermurmel

8个回答

25

这不是一个索引密集型的操作，实际上您可以使用 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包中定义的数据结构。

- Willem Van Onsem

14

虽然这不是一个 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开始的自然数是正确的。）

- ignis volens

6

在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]

In Clojure，数据通常是不可变的（无法被修改）。在这种情况下，函数assoc接受一个向量，并返回一个类似原始向量的新向量，但改变了第i个元素。这可能听起来效率不高，但底层数据结构允许在近乎恒定的时间内更新（O(log₃₂(n))）。

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

- vanyo

5

我知道您询问的是函数式语言，但我想插一句话，提到 Python 作为一种多范式语言，也有很好的高阶 itertools.accumulate 函数。

Accumulate 接收一个集合并返回其部分和或任何自定义二元函数的迭代器。相当于您示例的函数式 Python 代码只需：

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

通常情况下，Python标准库中的`itertools`和`functools`模块提供了出色的函数式编程工具。 itertools和functools

- yoniLavi

2

与C ++的std :: accumulate共享相同目的的名称。 - ShadowRanger

3

其他人指出，像scanl这样的函数可以很好地处理您的特定示例，因此让我们看看“依赖于循环/执行顺序的索引重型操作”的更广泛问题。我们可以将问题分解为三个问题：

索引
循环
突变

无论何时索引概念有意义，都支持对数据结构进行索引。例如，List和Vector都支持索引。正如其他人所指出的那样，如果您的索引是随机的，则Vector具有更好的性能，但这种情况令人惊讶地少见。

命令式循环可以直接用递归函数替换（参见维基百科），尽管标准库中实现了如此多的“高阶函数”（接受函数作为参数的函数），以至于您很少需要显式递归。 scanl就是一个例子。它允许您通过将其外包给预先编写的函数来避免显式递归调用。然而，该函数递归定义。编译器在生成机器代码时可能会将该递归优化为循环。

最后，您可能拥有一堆数字数组，并且确实非常希望在一系列步骤中突变数组中的值。包括我在内的本主题中的每个人都会竭尽全力说服您以更“功能性”的方式思考。但是，如果我们失败了，那么您可以使用状态线程单子。这为您提供了一种本地突变数据结构（令人害怕）的方法，同时仅与不可变（不可怕）的数据结构交互函数外部的东西，并因此确保函数是引用透明的。

- Jamie Ballingall

1

这个功能也被称为“累加和”，另一种使用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]

- user17242583

0

在 Elixir 中有一些类似于 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函数，或者某种形式的尾递归。

例如，您可以通过使用尾递归和手动累加器来构建自己的函数来处理此操作：

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]

- Everett

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Silvio Mayolo · Accepted Answer

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

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

因此，总体而言，很多时候我们会使用方便的列表相关原语来构建，而不是手写循环。人们喜欢说递归是FP中与命令式编程中的“for循环”最相似的东西。虽然这可能是真的，但平均功能程序使用的显式递归要比平均命令式程序使用的for循环少得多。我们所做的大部分事情（特别是与列表有关的）都是由map、filter、foldl以及Data.List、Data.Foldable、Data.Traversable中高度优化的其他好东西构建而成。

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