從尾巴上鍊表中刪除在榆樹（VS的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代碼 - 特別是我的代碼涉及到變異和重新綁定引用。

下面是榆樹的部分重新實現：

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然後consing的問題賦予了新的最後一個項目的項目：通過返回包含的最後一個項目和新的元組

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值（由於無法獲得空列表的最後一項而映射）來構建：

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