Как я могу получить доступ к списку по индексу в Haskell, аналогично этому коду C?

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

Посмотрите, здесь используется оператор !!.

Т.е. [1,2,3]!!1дает вам 2, т.к. списки индексируются 0.

Я не говорю, что с вашим вопросом или ответом что-то не так, но, возможно, вы хотели бы узнать о замечательном инструменте, который представляет собой Hoogle, чтобы сэкономить время в будущем: с помощью Hoogle вы можете искать стандартные библиотечные функции. которые соответствуют данной подписи. Итак, ничего не зная об этом !!, в вашем случае вы можете искать «что-то, что принимает Intи список чего угодно и возвращает одно такое, что угодно», а именно

Int -> [a] -> a

И вот , с !!первым результатом (хотя сигнатура типа фактически имеет два аргумента в обратном порядке по сравнению с тем, что мы искали). Аккуратно, а?

Кроме того, если ваш код полагается на индексацию (вместо использования в начале списка), списки могут фактически не быть надлежащей структурой данных. Для доступа на основе индекса O (1) есть более эффективные альтернативы, такие как массивы или векторы .

Альтернативой использованию (!!)является использование пакета линз , его elementфункции и связанных операторов. Объектив обеспечивает единый интерфейс для доступа широкого спектра структур и вложенных структур выше и вне списков. Ниже я сосредоточусь на приведении примеров и опишу как сигнатуры типа, так и теорию, лежащую в основе упаковки линз . Если вы хотите узнать больше о теории, лучше всего начать с файла readme в репозитории github .

Доступ к спискам и другим типам данных

Получение доступа к упаковке линз

В командной строке:

$ 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

В отличие от (!!)this не вызовет исключения при доступе к элементу за пределами границ и 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

Работа с типами, отличными от списков

Однако это не ограничивается только списками. Например, тот же метод работает с деревьями из стандартного пакета контейнеров .

 > 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

Мы также можем получить доступ к последовательностям из пакета контейнеров :

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

Мы можем получить доступ к стандартным индексированным массивам int из векторного пакета, тексту из стандартного текстового пакета, строкам байтов из стандартного пакета байтов и многим другим стандартным структурам данных. Этот стандартный метод доступа можно распространить на ваши личные структуры данных, сделав их экземпляром класса типов Taversable , см. Более длинный список примеров Traversables в документации Lens. .

Вложенные структуры

Копаться во вложенных структурах просто с помощью взлома линз . Например, доступ к элементу в списке списков:

> [[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]

Пакет линз предоставляет (.~)оператору эту функцию . Хотя, в отличие от 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- это просто функция, а (&)оператор, входящий в комплект линз , - это просто приложение обратной функции. Вот это с более распространенным функциональным приложением.

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

Присваивание снова отлично работает с произвольным вложением Traversables.

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

Прямой ответ уже был дан: используйте !!.

Однако новички часто склонны злоупотреблять этим оператором, что в Haskell дорого (потому что вы работаете с односвязными списками, а не с массивами). Есть несколько полезных методов, чтобы избежать этого, самый простой - использовать почтовый индекс. Если вы напишете zip ["foo","bar","baz"] [0..], вы получите новый список с индексами, «прикрепленными» к каждому элементу в паре:, [("foo",0),("bar",1),("baz",2)]что часто именно то, что вам нужно.

Вы можете использовать !!, но если вы хотите сделать это рекурсивно, ниже приведен один из способов сделать это:

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

Стандартный тип данных списка Haskell 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

При работе со связанными списками часто удобны порядковые номера:

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