如何从列表中获取第n个元素？

Question

如何在Haskell中通过索引访问列表，类似于这个C代码？

int a[] = { 34, 45, 56 };
return a[1];

- eonil

Answer 1

请看这里，使用的运算符是!!。

也就是说，[1,2,3]!!1会给你2，因为列表是从0开始计数的。

- phimuemue

---

就我个人而言，我无法理解为什么一个不返回Maybe类型的下标访问器被视为惯用的Haskell语法。[1,2,3]!!6会导致运行时错误。如果 !! 的类型是 [a] -> Int -> Maybe a，这种情况很容易避免。我们使用Haskell的一个非常重要的原因就是为了避免这种运行时错误！ - worldsayshi

这是一种权衡。他们选择的符号可能是最令人担忧的符号。所以我认为这个想法是允许它用于边缘情况，但要使其显眼且不符合惯用语。 - cdosborn

函数名称：itemOf 参数：Int类型的x和[a]类型的xs 返回值：Maybe a类型函数功能：如果x的绝对值大于列表xs的长度，则返回Nothing，否则返回xs中索引为x（取模后）的元素。 注意：这个函数在一个无限列表上会发生致命错误。 - djvs

!! 是一个部分函数，因此不安全。请查看下面的评论，并使用 lens 库 https://dev59.com/Hm435IYBdhLWcg3wxDP_#23627631 - goetz

@worldsayshi，这也是为什么除法运算符不返回Maybe的原因。一些基本运算符作为部分函数表达更有用。当然，您应该以某种方式证明前提条件已满足。我同意，在Kotlin中像List.get和List.getOrNull那样同时拥有两个版本通常很有用。甚至可能会有一个额外的除法运算符，它可能返回DivideByZeroError，这很酷。但是只有“安全”的那些...我不知道，我不喜欢那样。 - cubuspl42

Answer 2

我并不是在说你的问题或答案有什么问题，但也许你想了解一下未来可以节省时间的神奇工具Hoogle：使用Hoogle，您可以搜索与给定签名匹配的标准库函数。所以，在您不知道任何关于!!的情况下，您可以搜索"接受一个Int和一个whatevers列表并返回单个这样的whatever的函数"。

Int -> [a] -> a

Lo and behold, 第一个结果竟然是 !!（尽管类型签名实际上与我们搜索的相反）。很神奇，不是吗？

此外，如果你的代码依赖于索引（而不是从列表前面消耗），那么列表可能并不是合适的数据结构。对于基于 O(1) 索引访问，有更高效的替代品，比如arrays或vectors。

- gspr

---

Hoogle非常棒，每个Haskell程序员都应该知道。还有一个名为Hayoo（http://holumbus.fh-wedel.de/hayoo/hayoo.html）的替代品。它可以随着你的输入进行搜索，但似乎不像Hoogle那样聪明。 - musiKk

Answer 3

使用lens包及其element函数和相关运算符是使用(!!)的一种替代方法。 lens提供了一个统一的接口，用于访问各种结构和嵌套结构，超出了列表的范围。以下将重点提供示例，并略过lens包的类型签名和理论部分。如果您想了解更多关于理论的信息，可以在github存储库的自述文件中找到很好的起点。

访问列表和其他数据类型

获取访问lens包的权限

在命令行上：

$ cabal install lens
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
> import Control.Lens

访问列表

使用中缀操作符来访问列表

> [1,2,3,4,5] ^? element 2  -- 0 based indexing
Just 3

与 (!!) 不同的是，当访问越界元素时，它不会抛出异常，而是返回 Nothing。通常建议避免使用像 (!!) 或 head 这样的部分函数，因为它们有更多的边角情况，并且更容易导致运行时错误。您可以在这个维基页面上了解更多关于如何避免使用部分函数的信息。

> [1,2,3] !! 9
*** Exception: Prelude.(!!): index too large

> [1,2,3] ^? element 9
Nothing

您可以使用(^?!)运算符代替(^?)运算符，将镜头技术强制变为部分函数并在超出范围时引发异常。

> [1,2,3] ^?! element 1
2
> [1,2,3] ^?! element 9
*** Exception: (^?!): empty Fold

使用除了列表以外的类型

这不仅仅适用于列表。例如，相同的技术可以用于标准containers包中的树。

 > import Data.Tree
 > :{
 let
  tree = Node 1 [
       Node 2 [Node 4[], Node 5 []]
     , Node 3 [Node 6 [], Node 7 []]
     ]
 :}
> putStrLn . drawTree . fmap show $tree
1
|
+- 2
|  |
|  +- 4
|  |
|  `- 5
|
`- 3
   |
   +- 6
   |
   `- 7

我们现在可以按照深度优先的顺序访问树中的元素。

> tree ^? element 0
Just 1
> tree ^? element 1
Just 2
> tree ^? element 2
Just 4
> tree ^? element 3
Just 5
> tree ^? element 4
Just 3
> tree ^? element 5
Just 6
> tree ^? element 6
Just 7

我们也可以从containers包中访问序列：

> import qualified Data.Sequence as Seq
> Seq.fromList [1,2,3,4] ^? element 3
Just 4

我们可以从vector包中访问标准的int索引数组，从标准text包中访问文本，从标准bytestring包中访问字节串，以及许多其他标准数据结构。您可以通过将它们变成可遍历的类型类实例来扩展此标准访问方法，详见Lens文档中的更长示例列表。

嵌套结构体

使用lens hackage深入嵌套结构很简单。例如，在一个列表的列表中访问元素：

> [[1,2,3],[4,5,6]] ^? element 0 . element 1
Just 2
> [[1,2,3],[4,5,6]] ^? element 1 . element 2
Just 6

即使嵌套的数据结构类型不同，此组合仍然适用。例如，如果我有一组树的列表：

> :{
 let
  tree = Node 1 [
       Node 2 []
     , Node 3 []
     ]
 :}
> putStrLn . drawTree . fmap show $ tree
1
|
+- 2
|
`- 3
> :{
 let 
  listOfTrees = [ tree
      , fmap (*2) tree -- All tree elements times 2
      , fmap (*3) tree -- All tree elements times 3
      ]            
 :}

> listOfTrees ^? element 1 . element 0
Just 2
> listOfTrees ^? element 1 . element 1
Just 4

只要它们符合 Traversable 要求，您可以任意嵌套任意类型。 因此，访问树列表的文本序列毫不费力。

更改第n个元素

许多语言中的常见操作是在数组的索引位置上赋值。在Python中，您可能会这样：

>>> a = [1,2,3,4,5]
>>> a[3] = 9
>>> a
[1, 2, 3, 9, 5]

lens软件包通过(.~)运算符提供此功能。 不同于Python，原始列表不会被改变，而是返回一个新列表。

> let a = [1,2,3,4,5]
> a & element 3 .~ 9
[1,2,3,9,5]
> a
[1,2,3,4,5]

element 3 .~ 9是一个函数，(&)运算符是lens包中的一部分，它只是反向函数应用。这里是常见函数应用的实现。

> (element 3 .~ 9) [1,2,3,4,5]
[1,2,3,9,5]

使用任意嵌套的 Traversable，分配再次完美运行。

> [[1,2,3],[4,5,6]] & element 0 . element 1 .~ 9
[[1,9,3],[4,5,6]]

- Davorak

---

我可以建议链接到Data.Traversable而不是在lens中重新导出吗？ - dfeuer

@dfeuer - 我在base中添加了Data.Traversable的链接。我还保留了旧链接，并指出Lens文档中有更长的可遍历示例列表。感谢您的建议。 - Davorak

Answer 4

直接的答案已经给出：使用 !!。

然而，新手往往会过度使用这个操作符，在Haskell中这是昂贵的（因为你在单链列表上操作，而不是在数组上）。有几种有用的技术可以避免这种情况，其中最简单的方法是使用zip。如果你写zip ["foo","bar","baz"] [0..]，你会得到一个新的列表，其中每个元素都与一个索引“附加”在一起形成一对：[("foo",0),("bar",1),("baz",2)]，这通常正是你所需要的。

- Landei

---

在这里，你还需要注意类型的问题。大多数情况下，你不希望索引变成慢速的整数（Integers），而是快速的机器整数（Ints）。根据你的函数具体做什么以及类型的明确程度，Haskell可能会推断[0..]的类型为[Integer]而不是[Int]。 - chrisdb

Answer 5

你可以使用!!，但如果你想要递归地做到这一点，下面是一种方法：

dataAt :: Int -> [a] -> a
dataAt _ [] = error "Empty List!"
dataAt y (x:xs)  | y <= 0 = x
                 | otherwise = dataAt (y-1) xs

- Abgo80

Answer 6

哈斯克尔的标准列表数据类型 forall t. [t] 在实现上非常类似于经典的 C 链表，并且共享其基本属性。链表与数组非常不同。特别是，按索引访问是一种 O(n) 线性操作，而不是一种 O(1) 常量时间操作。

如果需要频繁随机访问，请考虑使用标准库中的 Data.Array。 !! 是一种不安全的部分定义函数，对于超出范围的索引会导致崩溃。请注意，标准库包含一些这样的部分函数（例如 head、last 等）。为了安全起见，请使用一个选项类型 Maybe 或者 Safe 模块。

以下是一个相当高效且稳健的完整（对于索引 ≥ 0）索引函数示例：

data Maybe a = Nothing | Just a

lookup :: Int -> [a] -> Maybe a
lookup _ []       = Nothing
lookup 0 (x : _)  = Just x
lookup i (_ : xs) = lookup (i - 1) xs

在处理链表时，常常使用序数（ordinals）来方便地操作:

nth :: Int -> [a] -> Maybe a
nth _ []       = Nothing
nth 1 (x : _)  = Just x
nth n (_ : xs) = nth (n - 1) xs

- user6428287

---

这些函数对于负整数和非正整数分别进行无限递归。 - Bjartur Thorlacius

Answer 7

我知道这是一篇旧帖子...但它可能对某些人有用... 以"功能性"的方式...

import Data.List

safeIndex :: [a] -> Int -> Maybe a
safeIndex xs i 
        | (i> -1) && (length xs > i) = Just (xs!!i)
        | otherwise = Nothing

- cealex

Answer 8

以下函数看起来很理想，因为它不是部分的（与!!不同），并且由现有库（relude）实现：

(!!?) :: [a] -> Int -> Maybe a

https://hackage.haskell.org/package/relude-1.0.0.1/docs/Relude-List.html#v:-33--33--63-

Prelude> import Relude.List
Prelude Relude.List> ['a'..'f'] !!? 0
Just 'a'
Prelude Relude.List> ['a'..'f'] !!? 100
Nothing

- Chris Stryczynski

Answer 9

“Maybe-way” 是一种合理的方法。

只需提出另一种选择，当您需要获取预先确定的默认值时。

atDefault :: a -> Integer -> [a] -> a
atDefault aDef _ [] = aDef                        -- case: is empty anyway
atDefault _ 0  (a:_) = a                          -- case: index is 0 -> take it
atDefault aDef nIndex  (a:la) 
    | nIndex > 0 = atDefault aDef (nIndex - 1) la -- case: index is positive
    | otherwise  = aDef                           -- case: index is negative

一个使用案例可能是以下内容：

您想通过使用八位字节列表来表示无限的数字集。假设该列表始终具有给定的n个元素，假设n>0，但元素也可能被访问到通常认为超出索引范围的位置（索引>=n或索引<0），但您不会这样做。相反，您提供0作为默认值。

例如：

module Main where

import qualified Data.Word as W
import qualified Data.Bits as Bts
import Data.Bits ((.|.))
import qualified Data.List as L

main :: IO ()
main = do
    print $ atDefault 0x00 (-1) myOctet
    print $ atDefault 0x00 0 myOctet
    print $ atDefault 0x00 1 myOctet
    print $ atDefault 0x00 2 myOctet
    print $ atDefault 0x00 3 myOctet
    print $ atDefault 0x00 4 myOctet

myOctet = toOctets (0xA4B3C2D1 :: W.Word32)

atDefault :: a -> Integer -> [a] -> a
atDefault aDef _ [] = aDef                        -- case: is empty anyway
atDefault _ 0  (a:_) = a                          -- case: index is 0 -> take it
atDefault aDef nIndex  (a:la) 
    | nIndex > 0 = atDefault aDef (nIndex - 1) la -- case: index is positive
    | otherwise  = aDef                           -- case: index is negative

class Octetable w where
    toOctets :: w -> [W.Word8]

instance Octetable W.Word32 where
    toOctets w32 = 
        [ fromIntegral (w32 `Bts.shiftR` 24)
        , fromIntegral (w32 `Bts.shiftR` 16)
        , fromIntegral (w32 `Bts.shiftR` 8)
        , fromIntegral w32
        ]

输出

0
164
179
194
209
0

- Jörg Brüggmann

Answer 10

另一个选择是使用genericIndex :: Integral i => [a] -> i -> a函数，它的索引类型参数比(!!) :: [a] -> Int -> a更少限制。在某些情况下可能会很方便。

- Ed'ka