在列表末尾添加元素 [英] Append an element at the end of a list

问题描述

如何在ReasonML中的列表末尾附加元素(在JavaScript中等于Array.concat)?

How to append an element at the end of a list in ReasonML (the equivalent of Array.concat in JavaScript)?

推荐答案

虽然尼尔的答案在技术上是正确的，但它掩盖了您在寻求append之前可能要考虑的一些细节；特别是，虽然将元素添加到列表的开头非常便宜，但是将元素添加到列表的结尾非常昂贵.

While Neil's answer is technically correct, it glosses over some details that you might want to consider before reaching for append; specifically that while adding an element to the beginning of a list is very cheap, adding an element to the end is very expensive.

要了解原因，让我们看看如何定义和构造列表.列表的(概念上)定义是:

To understand why, let's look at how a list is defined and constructed. The (conceptual) definition of a list is:

// Reason
type list('a) = Cons('a, list('a)) | Nil;

(* OCaml *)
type 'a list = Cons of 'a* 'a list | Nil

其中，Nil表示列表的末尾(并且本身是一个空列表)，而Cons表示列表中的节点，其中包含类型为'a的元素和指向列表其余部分的指针( list('a)，OCaml:'a list).

where Nil represents the end of a list (and by itself an empty list) and Cons represents a node in the list, containing an element of type 'a and a pointer to the rest of the list (list('a), OCaml: 'a list).

如果我们删除了所有语法糖和每个辅助函数，则必须构造一个这样的列表:

If we took away all the syntax sugar and every helper function, you would have to construct a list like this:

// Reason
let myList = Cons(1, Cons(2, Cons(3, Nil)));

(* OCaml *)
let myList = Cons (1, Cons (2, Cons (3, Nil)))

然后要将一个元素添加到此列表的开头，我们构造一个节点，其中包含我们的新元素和一个指向旧列表的指针:

To add an element to the head of this list then, we construct a node containing our new element and a pointer to the old list:

// Reason
let myBiggerList = Cons(0, myList);

(* OCaml *)
let myBiggerList = Cons (0, myList)

这与执行[0, ...myList](OCaml:0 :: myList)完全相同.当然，如果myList可以更改，我们将无法执行此操作，但是由于列表是不可变的，因此我们知道不会.这使得它非常便宜，并且出于同样的原因，让您摆脱困境也是如此便宜，这就是为什么您通常会看到使用递归实现的列表处理功能的原因，例如:

This is exactly the same as doing [0, ...myList] (OCaml: 0 :: myList). If myList could change we wouldn't be able to do this, of course, but we know it doesn't since lists are immutable. That makes this very cheap, and for the same reason it's just as cheap to pop the head off, which is why you'll usually see list processing functions implemented using recursion, like this:

// Reason
let rec map = f =>
  fun | []         => []
      | [x, ...xs] => [f(x), ...map(f, xs)];

(* OCaml *)
let rec map f = function
  | [] -> []
  | x::xs -> (f x) :: (map f xs)

好吧，那为什么在列表的尾部添加元素如此昂贵?如果回头看myList，在元素的末尾添加元素意味着替换最后一个Nil和Cons(4, Nil).但是然后我们需要替换Cons(3, ...)，因为它指向旧的Nil，而Cons(2, ...)则指向旧的Cons(3, ...)，依此类推，直到整个列表.而且每次添加元素时都必须这样做.很快就加起来了.

Ok, so then why is it so expensive to add an element to the tail of the list? If you look back at myList, adding an element to the end means replacing the final Nil with, say, Cons(4, Nil). But then we need to replace Cons(3, ...) since that points to the old Nil, and Cons(2, ...) because it point to the old Cons(3, ...), and so on through the entire list. And you have to do that every time you add an element. That quickly adds up.

那您应该怎么做?

如果要添加到末尾，或者只是遍历末尾，或者总是像在JavaScript中那样经常删除元素，那么很有可能只是颠倒了逻辑.不必添加和删除结尾，而是添加和删除开头.

If you're adding to the end and either just iterating through it or always taking elements off the end, like you often would in JavaScript, you cam most likely just reverse your logic. Instead of adding to and taking off the end, add to and take off the beginning.

如果您实际上需要FIFO数据结构，其中元素在一端插入而另一端取出，请考虑使用队列.通常，请查看标准容器性能特征的比较.

If you actually need a FIFO data structure, where elements are inserted at one end and taken off at the other, consider using a Queue instead. In general, have a look at this comparison of the performance characteristics of the standard containers.

或者如果这一切太多了，并且您真的想像从JavaScript中那样习惯使用它，只需使用array而不是list.您将在 Js.Array模块中找到所有熟悉的功能

Or if this is all a bit much and you'd really just like to do it like you're used to from JavaScript, just use an array instead of a list. You'll find all the functions you're familiar with in the Js.Array module

这篇关于在列表末尾添加元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！