Il modo più veloce per ottenere l'ultimo elemento di una lista in Haskell

Question

Qual è il modo più veloce per ottenere l'ultimo elemento di una lista in Haskell. Inoltre nella prossima iterazione, voglio rimuovere il primo e l'ultimo elemento della lista. Qual è il modo più elegante per farlo? Sto provando la comprensione delle liste, ma non sembra molto efficiente!

Answer 1

last e init faranno il lavoro bene per una tantum. Tuttavia sono entrambi O (n), quindi se è necessario manipolare spesso entrambe le estremità di un elenco, come sembra implicitamente, è consigliabile prendere in considerazione l'utilizzo di Data.Sequence, che supporta l'inserimento e la rimozione di O (1) di articoli ad entrambe le estremità.

Answer 2

È possibile utilizzare the last function per ottenere l'ultimo elemento di un elenco.

Per quanto riguarda la rimozione del primo e dell'ultimo elemento, è possibile utilizzare (init . tail), ma non so quanto sia efficiente.

Credo che questa immagine da Learn You A Haskell mostra le funzioni della lista abbastanza bene:

Answer 3

Per rimuovere prima e l'ultima:

take (len(l)-2) (drop 1 l) 

o forse

init (drop 1 l) 

Questo anche risultati in codice quasi ottimale.

Answer 4

vi posterò la realizzazione Preludio in quanto non è stata ancora spedita:

listLast :: [a] -> a 
listLast [x] = x --base case is when there's just one element remaining 
listLast (_:xs) = listLast xs --if there's anything in the head, continue until there's one element left 
listLast [] = error "Can't do last of an empty list!" 

Nota che ho cambiato il nome della funzione di listLast in modo che possa essere eseguito senza entrare in conflitto con il Preludio normale. Potresti, ovviamente, fare import Prelude hiding(last).

Answer 5

(head.reverse) [1..100] 

È un'alternativa a last per ottenere l'ultimo elemento.

drop 1 (take (length [1..100] - 1) [1..100]) 

rimuove il primo e l'ultimo elemento della lista. La fonte per drop e take sembra che potrebbe essere più veloce di (init . tail).

(reverse.drop 1) ((reverse.drop 1) [1..100]) 

è un'altra variante. Ma credo che sia più lento a causa della doppia inversione.

Answer 6

Questa risposta si concentra sulla gestione di condizioni strane (come le liste vuote) in un modo massimamente flessibile e sulla creazione di funzioni più grandi da quelle più piccole utilizzando alcune funzioni della libreria. È non la migliore risposta per qualcuno che prima apprende sulle liste, ma piuttosto un paio di passaggi oltre.

Per quanto segue, è necessario

import Control.Monad ((>=>)) 

e sarà necessario usare sia per GHC 7.10 e importare Data.List (uncons) o definire

uncons :: [a] -> Maybe (a, [a]) 
uncons [] = Nothing 
uncons (x:xs) = Just (x,xs) 

È possibile scrivere una forma sicura di init come questo:

init' :: [x] -> Maybe [x] 
init' = foldr go Nothing 
    where 
    go x mxs = Just (maybe [] (x:) mxs) 

Una versione di tail può essere scritto

tail' :: [a] -> Maybe [a] 
tail' = fmap snd . uncons 

Così allora si può ottenere un forse

trim' :: [a] -> Maybe [a] 
trim' = init' >=> tail' 

Il >=> è una sorta di composizione monadica all'indietro. init' >=> tail' è una funzione che applica init' al suo argomento per ottenere un valore Maybe [a]. Se ottiene Nothing, lo restituisce. Se ottiene Just xs, applica tail' a xs e lo restituisce.

Da questo, si può facilmente fare un trimmer che rifila liste con 0, 1, o 2 elementi verso il basso per le liste vuote:

trim :: [a] -> [a] 
trim = maybe [] id . trim'