haskell - Haskell：获取Snoc列表中的第N个元素

Question

我编写了以下函数来查找给定 Snoc 列表中的第 N 个元素（反向缺点），但我认为这不是问题的最佳解决方案。我想知道您是否愿意分享一些见解、代码或建议以查看不同的解决方案；您可能会考虑更有效地完成这项工作：

这是我的功能：

data ListS a = NilS 
              |Snoc (ListS a) a deriving Show

len :: ListS a -> Int
len NilS       = 0
len (Snoc a b) = 1 + len(a) 

nthElementS :: Int -> ListS a -> a
nthElementS _ NilS = error "Empty List"
nthElementS n s    = if n < 0 || n >= len(s) then error "Invalid Index" 
                     else nthAux ((len(s)-1)-n) s where
                          nthAux 0 (Snoc a b) = b
                          nthAux m (Snoc a b) = nthAux (m-1) a

一些例子：

Main> nthElementS 0 (Snoc (Snoc (Snoc (Snoc (Snoc NilS 1) 2) 3) 4) 5)
1

Main> nthElementS 2 (Snoc (Snoc (Snoc (Snoc (Snoc NilS 1) 2) 3) 4) 5) 
3

作为附加询问：实现连接 2 个 Snoc 列表的函数的最佳方法是什么？我已经在考虑一个解决方案，但它需要一个辅助函数来跟踪第 N 个位置，而且我觉得这不会充分利用 Haskell 相对于其他语言的优势。

提前致谢。

标签： haskell

Answer 1

我们可以使用“ try-and-error ”方法，首先尝试在“前缀列表”中找到该元素，如果这还不够（因为索引更大），然后我们尝试当前元素。如果这还不够，则由“家长电话”来处理这种情况。我们可以通过首先定义一个输出类型略有不同的函数来做到这一点：

nthShelp :: Int -> ListS a -> Either a Int

因此Left x，如果它找到了元素（x作为元素），或者它需要遍历的“剩余”元素，它就会返回Right。, with

所以我们可以这样定义：

nthShelp :: Int -> ListS a -> Either a Int
nthShelp n NilS = Right n
nthShelp n (Snoc hs t) = progress nhs
    where nhs = nthElementS n hs
          progress lx@(Left _) = lx
          progress (Right 0) = Left t
          progress (Right n) = Right (n-1)

因此，我们首先在列表的头部递归调用，然后通过递减索引直到它达到零来解决递归调用，在这种情况下，我们返回相应的Left t，然后Left t从递归调用传回。

我们可以利用 istance 的事实，Either a将其Monad写得更有效，例如：

nthShelp :: Int -> ListS a -> Either a Int
nthShelp n NilS = Right n
nthShelp n (Snoc hs t) = nthElementS n hs >>= progress
    where progress 0 = Left t
          progress n = Right (n-1)

然后我们可以写成nthElementS：nthShelp

nthElementS :: Int -> ListS a -> a
nthElementS n l | n < 0 = error "Index too small"
                | Left a <- nthShelp n l = a
                | otherwise = error "Index too large"

就时间复杂度而言，仍然是O(n)（其中n是列表的长度，不是我们要获取的索引）。没有办法用这种数据结构做得更好，因为在我们知道要返回什么元素之前，我们需要知道前缀中元素的数量。

作为附加询问：实现连接 2 个 Cons 列表的函数的最佳方法是什么？我已经在考虑一个解决方案，但它需要一个辅助函数来跟踪第 N 个位置，而且我觉得这不会充分利用 Haskell 相对于其他语言的优势。

好吧，您可以在这里看到一个串联，用第一个列表替换第二个NlS列表的（通常很深）嵌套。所以如果我们连接，那么它就是，如果我们连接，那么它就是。所以我们可以递归定义为：concatS l1 NilSl1concatS l1 (Snoc NilS x)Snic l1 x)

concatS :: ListS a -> ListS a -> ListS a
concatS l1 NilS = l1
concatS l1 (Snoc l2 x) = Snoc (concatS l1 l2) x

上述方法的一个缺点是，如果第一个列表（如此空） ，它仍然可以在O(n)中工作。NilS我们可以为此添加一个警卫来处理这种情况：

concatS :: ListS a -> ListS a -> ListS a
concatS NilS = id
concatS l1 = go
    where go NilS = l1
          go (Snoc l2 x) = Snoc (go l2) x