haskell - 如何从链接列表中删除第 n 个元素？

Question

如何从链表中删除第n个元素？

import Data.List 

data LinkedList = LLEmpty  | LLNode Int LinkedList deriving (Eq, Show, Ord)                 

在第n个位置插入一个整数

linkListInsertNPosition :: Int -> Int -> LinkedList -> LinkedList                       
linkListInsertNPosition pos val listL =
    let ninsertion = insertionN val (lengthL listL - pos) listL
        in ninsertion

insertionN :: Int -> Int -> LinkedList -> LinkedList           
insertionN val count listL =
    case listL of
        LLEmpty -> LLEmpty
        (LLNode a b) -> if (count <=0)
                            then LLNode val (LLNode a b)
                       else LLNode a (insertionN val (count - 1) b)            

链接列表的末尾和头部

lastL :: LinkedList -> Int                             
lastL listL =
    case listL of
        LLNode a b -> a

tailL :: LinkedList -> LinkedList                   
tailL listL =
    case listL of
    LLEmpty -> LLEmpty
    LLNode a b -> b

headL :: LinkedList -> Int                   --100
headL listL =
case listL of 
    LLNode a LLEmpty -> a
    LLNode a b -> headL (tailL b)

获取链表长度

lengthL :: LinkedList -> Int                    
lengthL listL =
case listL of
    LLEmpty -> 0
    LLNode a b -> 1 + (lengthL (tailL listL))

我坚持要删除链接列表中的第 n 个元素。任何人都可以帮助我并提出一种方法。删除第n个元素后如何加入链表？或者我需要做一个新的链接列表？

Answer 1

链表 LList 要么是空，要么包含一个值和另一个链表。

data LList a = Empty | Node a LList

如果我们定义一个运算符(比如用于内置 [] 链表的 (:) )，这可能会更容易

data LList a = Empty | a :+: LList
--   much like:
-- data [a]  = []    | a :   [a]

您的列表特别是 Int，因此我们可以放弃多态性

data LList = Empty | Int :+: LList
  deriving (Eq, Show, Ord)

-- and, useful for testing:
fromList :: [Int] -> LList
fromList = foldr (:+:) Empty

---

在 n 之后插入只是插入链表 n 次并在该点重新链接。

import Data.Either (partitionEithers)
-- partitionEithers :: [Either a b] -> ([a], [b])

-- fun fact, I had to look this one up, but this is how haskell implements (++)
(|++|) :: LList -> LList -> LList
Empty    |++| ys    = ys
xs       |++| Empty = xs
(x:+:xs) |++| ys    = x :+: (xs |++| ys)

mySplitAt :: Int -> LList -> (LList, LList)
mySplitAt n = partitionEithers . map (go n) . zip [0..]
  where
  go n (i, x) | i < n     = Left x
              | otherwise = Right x

insertAfter :: Int -> Int -> LList -> LList
insertAfter n x xs = before |++| (x :+: after)
  where (before, after) = mySplitAt n xs

这自然意味着删除第n个值只是在特定节点之后重新链接

delete :: Int -> LList -> LList
delete n xs = before |++| after
  where (before, _ :+: after) = mySplitAt n xs