Jak uzyskać n-ty element z listy?

97

Jak mogę uzyskać dostęp do listy według indeksu w Haskell, analogicznie do tego kodu C?

int a[] = { 34, 45, 56 };
return a[1];
eonil
źródło

Odpowiedzi:

154

Spójrz tutaj , użyty operator to !!.

Czyli [1,2,3]!!1daje 2, ponieważ listy są 0-indeksowane.

phimuemue
źródło
86
Osobiście nie mogę pojąć, w jaki sposób akcesor at-index, który nie zwraca typu może, jest akceptowalny jako idiomatyczny Haskell. [1,2,3]!!6wyświetli błąd wykonania. Gdyby !!miał taki typ, bardzo łatwo można by tego uniknąć [a] -> Int -> Maybe a. Powodem, dla którego mamy Haskell, jest unikanie takich błędów w czasie wykonywania!
worldsayshi
9
To kompromis. Symbol, który wybrali, jest prawdopodobnie najbardziej niepokojącym symbolem, jaki mogli mieć. Myślę więc, że chodziło o to, aby zezwolić na to w skrajnych przypadkach, ale wyróżnić jako nie idiomatyczne.
cdosborn
3
itemOf :: Int -> [a] -> Maybe a; x `itemOf` xs = let xslen = length xs in if ((abs x) > xslen) then Nothing else Just (xs !! (x `mod` xslen)). Uwaga, na nieskończonej liście zakończy się to katastrofalnym skutkiem.
djvs
2
!!jest funkcją częściową, a zatem niebezpieczną. Spójrz na poniższy komentarz i użyj lens stackoverflow.com/a/23627631/2574719
goetzc
90

Nie mówię, że jest coś nie tak z Twoim pytaniem lub udzieloną odpowiedzią, ale może chcesz wiedzieć o wspaniałym narzędziu, jakim jest Hoogle, aby zaoszczędzić czas w przyszłości: Dzięki Hoogle możesz wyszukiwać standardowe funkcje biblioteki pasujące do danego podpisu. Tak więc, nie wiedząc nic o tym !!, w twoim przypadku możesz wyszukać „coś, co pobiera Inti listę wszystkich możliwych odpowiedzi i zwraca jedno takie cokolwiek”, a mianowicie

Int -> [a] -> a

Lo i behold , !!jako pierwszy wynik (chociaż sygnatura typu w rzeczywistości ma dwa argumenty w odwrotnej kolejności w porównaniu z tym, czego szukaliśmy). Schludnie, co?

Ponadto, jeśli twój kod opiera się na indeksowaniu (zamiast pobierać od początku listy), listy mogą w rzeczywistości nie być właściwą strukturą danych. W przypadku dostępu opartego na indeksach O (1) istnieją bardziej wydajne alternatywy, takie jak tablice lub wektory .

gspr
źródło
4
Hoogle jest absolutnie wspaniały. Każdy programista Haskell powinien to wiedzieć. Istnieje alternatywa o nazwie Hayoo ( holumbus.fh-wedel.de/hayoo/hayoo.html ). Wyszukuje podczas pisania, ale nie wydaje się być tak sprytny jak Hoogle.
musiKk
61

Alternatywą dla używania (!!)jest użycie zestawu soczewek i jego elementfunkcji oraz powiązanych operatorów. Obiektyw zapewnia jednolity interfejs dostępu do różnorodnych struktur i struktur zagnieżdżonych wykraczające poza list. Poniżej skupię się na przedstawieniu przykładów i omówię zarówno oznaczenia typu, jak i teorię stojącą za opakowaniem soczewek . Jeśli chcesz dowiedzieć się więcej o teorii, dobrym miejscem do rozpoczęcia jest plik readme w repozytorium github .

Dostęp do list i innych typów danych

Uzyskanie dostępu do pakietu soczewek

W wierszu poleceń:

$ 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


Dostęp do list

Dostęp do listy z operatorem infix

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

W przeciwieństwie do (!!)this nie zgłosi wyjątku podczas uzyskiwania dostępu do elementu poza granicami i Nothingzamiast tego zwróci . Często zaleca się unikanie funkcji częściowych, takich jak (!!)lub, headponieważ mają one więcej przypadków narożnych i częściej powodują błąd w czasie wykonywania. Możesz przeczytać trochę więcej o tym, dlaczego unikać częściowych funkcji na tej stronie wiki .

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

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

Możesz wymusić na technice soczewki funkcję częściową i zgłosić wyjątek, gdy jest poza zakresem, używając (^?!)operatora zamiast (^?)operatora.

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


Praca z typami innymi niż listy

Nie ogranicza się to jednak tylko do list. Na przykład ta sama technika działa na drzewach ze standardowego pakietu kontenerów .

 > 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

Możemy teraz uzyskać dostęp do elementów drzewa w kolejności w pierwszej kolejności:

> 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

Możemy również uzyskać dostęp do sekwencji z pakietu kontenerów :

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

Możemy uzyskać dostęp do standardowych tablic indeksowanych int z pakietu wektorów , tekstu ze standardowego pakietu tekstowego , bajtów ze standardowego pakietu bajtowego i wielu innych standardowych struktur danych. Tę standardową metodę dostępu można rozszerzyć na struktury danych osobowych, czyniąc je instancją typeklasy Taversable , zobacz dłuższą listę przykładów Traversables w dokumentacji Obiektywu. .


Struktury zagnieżdżone

Zagłębianie się w zagnieżdżone struktury jest proste dzięki hakowaniu soczewki . Na przykład dostęp do elementu na liście list:

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

Ta kompozycja działa nawet wtedy, gdy zagnieżdżone struktury danych są różnych typów. Na przykład gdybym miał listę drzew:

> :{
 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

Możesz zagnieżdżać dowolnie głęboko z dowolnymi typami, o ile spełniają one Traversablewymagania. Zatem dostęp do listy drzew z sekwencjami tekstu to nie problem.


Zmiana n-tego elementu

Powszechną operacją w wielu językach jest przypisanie do indeksowanej pozycji w tablicy. W Pythonie możesz:

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

Obiektyw pakiet daje tę funkcjonalność z (.~)operatorem. Chociaż w przeciwieństwie do pythona oryginalna lista nie jest mutowana, zwracana jest raczej nowa lista.

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

element 3 .~ 9to tylko funkcja, a (&)operator, część zestawu soczewek , jest po prostu odwrotnym zastosowaniem funkcji. Tutaj jest z bardziej powszechną aplikacją funkcji.

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

Przypisanie znowu działa doskonale z arbitralnym zagnieżdżeniem Traversables.

> [[1,2,3],[4,5,6]] & element 0 . element 1 .~ 9
[[1,9,3],[4,5,6]]
Davorak
źródło
3
Czy mogę zasugerować tworzenie linków do Data.Traversablezamiast ponownego eksportu w lens?
dfeuer
@dfeuer - dodałem link do Data.Traversable w bazie. Zachowałem również stary link i zwróciłem uwagę, że w dokumentacji obiektywu jest dłuższa lista przykładowych traverable. Dzieki za sugestie.
Davorak
11

Prosta odpowiedź została już udzielona: użyj !!.

Jednak początkujący często nadużywają tego operatora, który jest drogi w Haskell (ponieważ pracujesz na pojedynczych połączonych listach, a nie na tablicach). Istnieje kilka przydatnych technik, aby tego uniknąć, z których najłatwiejszym jest użycie zip. Jeśli napiszesz zip ["foo","bar","baz"] [0..], otrzymasz nową listę z indeksami „dołączonymi” do każdego elementu w parze:, [("foo",0),("bar",1),("baz",2)]co często jest dokładnie tym, czego potrzebujesz.

Landei
źródło
2
Tam też musisz uważać na swoje typy. W większości przypadków nie chcesz, aby indeksy były wolnymi liczbami całkowitymi, a nie szybkimi maszynowymi Ints. W zależności od tego, co dokładnie robi twoja funkcja i jak wyraźne jest twoje wpisanie, Haskell może wywnioskować, że typ [0 ..] to [Integer] zamiast [Int].
chrisdb,
4

Możesz użyć !!, ale jeśli chcesz to zrobić rekurencyjnie, poniżej jest jeden ze sposobów, aby to zrobić:

dataAt :: Int -> [a] -> a
dataAt _ [] = error "Empty List!"
dataAt y (x:xs)  | y <= 0 = x
                 | otherwise = dataAt (y-1) xs
Abgo80
źródło
4

Standardowy typ danych listy Haskell forall t. [t]w implementacji bardzo przypomina kanoniczną listę połączoną z C i ma podobne właściwości. Połączone listy bardzo różnią się od tablic. Przede wszystkim dostęp przez indeks jest operacją liniową O (n), zamiast operacji O (1) w czasie stałym.

Jeśli potrzebujesz częstego losowego dostępu, rozważ Data.Arraystandard.

!!jest niebezpieczną, częściowo zdefiniowaną funkcją, wywołującą awarię dla indeksów poza zakresem. Należy pamiętać, że biblioteka standardowa zawiera takie częściowe funkcje (head , lastetc.). Ze względów bezpieczeństwa użyj typu opcji Maybelub Safemodułu.

Przykład w miarę wydajnej, solidnej funkcji indeksowania sumy (dla indeksów ≥ 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

Praca z połączonymi listami często jest wygodna:

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

źródło
Te funkcje powtarzają się w nieskończoność odpowiednio dla ujemnych i niepozytywnych Intów.
Bjartur Thorlacius