人们会在哪个函数式编程函数中增长一组项目？

Question

这三个中的哪一个（如果有的话（请提供替代方案））将用于将元素添加到项目列表中？

• 还折叠
• 地图
• 过滤器

；如何添加项目？ （附加到末尾/插入在工作项/其他之后）

Answer 1

函数式编程中的列表通常被定义为递归数据结构，它要么是特殊的空值，要么由一个值（称为“头”）和另一个列表（称为“尾”）组成。在 Haskell 中：

-- A* = 1 + A x A*
-- there is a builtin list type:
data [a] = [] | (a : [a])

要在头部添加元素，可以使用“cons”：该函数接受头部和尾部，并生成相应的列表。

-- (:) is "cons" in Haskell
(:) :: a -> [a] -> [a]

x = [1,2,3]   -- this is short for (1:(2:(3:[])))
y = 0 : x     -- y = [0,1,2,3]

要在末尾添加元素，您需要递归列表以添加它。您可以通过折叠轻松完成此操作。

consAtEnd :: a -> [a] -> [a]
consAtEnd x = foldr [x] (:)
    -- this "rebuilds" the whole list with cons,
    -- but uses [x] in the place of []
    -- effectively adding to the end

要在中间添加元素，您需要使用类似的策略：

consAt :: Int -> a -> [a] -> [a]
consAt n x l = consAtEnd (take n l) ++ drop n l
     -- ++ is the concatenation operator: it joins two lists
     -- into one.
     -- take picks the first n elements of a list
     -- drop picks all but the first n elements of a list

请注意，除了头部插入之外，这些操作会跨越整个列表，这可能会成为性能问题。

Answer 2

“cons”是大多数函数式编程语言中用于构造各种数据结构（包括列表）的低级操作。在 lispy 语法中，它看起来像这样：

(cons 0 (cons 1 (cons 2 (cons 3 nil))))

视觉上这是一个链接列表

0 -> 1 -> 2 -> 3 -> nil

或者也许更准确地说

cons -- cons -- cons -- cons -- nil
  |       |       |       |
  0       1       2       3

当然，您也可以构造各种带有 cons 的“树”状数据结构。

树状结构可能看起来像这样，

(cons (cons 1 2) (cons 3 4))

即视觉上：

  cons
  /  \
cons cons
/ \   / \
1 2   3 4

然而，大多数函数式编程语言将提供许多“高级”函数来操作列表。

例如，在 Haskell 中，有

• Append: (++) :: [a] -> [一]-> [a]
• 列表理解：[foo c | c <- s]
• 缺点： (:) :: a -> [一]-> [a]（正如马蒂尼奥已经提到的）
• 还有很多更多

只是提供一个结论性意见，您通常不会像您可能认为的那样操作列表中的各个元素，这是一种命令式思维方式。您更有可能使用递归函数或该行中的某些内容来复制整个结构。编译器/虚拟机负责识别何时可以就地修改内存并更新指针等。