在 Elm 中从 LinkedList 的尾部移除（对比 JavaScript）

Question

我认识到这可能不是 JavaScript 中链表的精确实现，但这是我所拥有的：

// a Node is either null or { value: value, next: Node }
function createNode(value) {
    return { value: value, next: null };
}

function isEmpty(node) {
    return node === null;
}

function addToHead(value, node) {
    var newNode = createNode(value);
    newNode.next = node;
    return newNode;
}

function addToTail(value, node) {
    var newNode = createNode(value);
    if (isEmpty(node)) return newNode;
    node.next = addToTail(value, node.next);
    return node;
}

function contains(value, node) {
    if (isEmpty(node)) return false;
    if (node.value === value) return true;
    return contains(value, node.next);
}

function removeFromTail(node) {
    if (isEmpty(node) || isEmpty(node.next)) return null;
    var current = node;
    var next = current.next;
    while (next.next) {
        current = next;
        next = next.next;
    }
    current.next = null;
    return node;
}

我的问题是您将如何在 Elm 中实现 removeFromTail 代码 - 特别是我的代码涉及突变和重新绑定引用。

这是在 Elm 中的部分重新实现：

type List a = Empty | Node a (List a)

addToHead value list =
  case list of
    Empty ->
      Node value Empty
    Node _ _ ->
      Node value list

contains value list =
  case list of
    Empty ->
      False
    Node v sublist ->
      if v == value then
        True
      else
        contains value sublist

但是，我卡在了 addToTail 和 removeFromTail 上，因为我不确定如何在不重建新列表的情况下执行此操作。

Answer 1

在不可变链表的尾部进行操作意味着需要重建链表。没有办法解决这个问题。

由于 List a 是内置的 Elm 类型，我还建议更改名称以避免名称冲突。

type MyList a = Empty | Node a (MyList a)

addToTail 然后是给定一个新的最后一项的项目的问题：

addToTail : a -> MyList a -> MyList a
addToTail val list =
  case list of
    Empty -> Node val Empty
    Node x xs -> Node x <| addToTail val xs

删除最后一项可以通过返回包含最后一项和新列表的元组来完成。可以通过映射 Maybe 值来构建新列表（引入 Maybe 是因为您无法获取空列表的最后一项）：

removeFromTail : MyList a -> Maybe (a, MyList a)
removeFromTail list =
  case list of
    Empty -> Nothing
    Node x Empty -> Just (x, Empty)
    Node x xs -> Maybe.map (\(y, ys) -> (y, Node x ys)) <| removeFromTail xs

在 Elm 中从 LinkedList 的尾部移除（对比 JavaScript）

Removing from Tail on LinkedList in Elm (vs JavaScript)

javascript

data-structures

elm