Le moyen le plus rapide d'obtenir le dernier élément d'une liste dans Haskell

Quel est le moyen le plus rapide d'obtenir le dernier élément d'une liste dans Haskell. Aussi dans la prochaine itération, je veux supprimer le premier et le dernier élément de la liste. Quelle est la façon la plus élégante de le faire? J'essaie de comprendre la liste, mais cela ne semble pas très efficace!

22
demandé sur Tim Matthews 2011-09-11 11:38:26

6 réponses

last et init fera le travail très bien pour un one-off. Cependant, ils sont tous les deux O (N) , donc si vous avez besoin de manipuler les deux extrémités d'une liste souvent, comme vous semblez l'impliquer, vous pouvez envisager d'utiliser Data.Sequence au lieu de cela, qui prend en charge O (1) l'insertion et la suppression des éléments aux deux extrémités.

33
répondu hammar 2015-02-04 11:23:30

Vous pouvez utiliser le last function pour obtenir le dernier élément d'une liste.

Quant à la façon de supprimer les premier et dernier éléments, vous pouvez utiliser (init . tail), mais je ne sais pas à quel point c'est efficace.

Je pense que cette image de Vous apprend un Haskell montre assez bien les fonctions de liste:

illustration des fonctions de liste

74
répondu icktoofay 2017-02-08 14:33:07

Je posterai L'implémentation de Prelude car elle n'a pas encore été postée:

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!"

Notez que j'ai changé le nom de la fonction en listLast afin qu'il puisse être exécuté sans entrer en conflit avec Prelude normal. Vous pourriez, bien sûr, faire import Prelude hiding(last).

5
répondu user1429980 2013-04-18 04:37:11

Pour supprimer le premier et Le Dernier:

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

Ou peut-être

init (drop 1 l)

Il en résulte également un code presque optimal.

0
répondu nulvinge 2011-09-11 09:21:15

Cette réponse se concentre sur le traitement des conditions étranges (comme les listes vides) d'une manière maximale flexible, et sur la construction de plus grandes fonctions à partir de plus petites en utilisant certaines fonctions de bibliothèque. C'est Pas la meilleure réponse pour quelqu'un qui apprend d'abord les listes, mais plutôt quelques pas après cela.

Pour ce qui suit, vous aurez besoin de

import Control.Monad ((>=>))

Et vous devrez soit utiliser GHC 7.10 et importer Data.List (uncons) ou Définir

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

Vous pouvez écrire une forme sûre de init comme ceci:

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

Une version de tail peut être écrit

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

Alors vous pouvez obtenir un maybefied

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

Le >=> est une sorte de composition monadique à l'envers. init' >=> tail' est une fonction qui s'applique init' à son argument pour obtenir un Maybe [a]. S'il obtient Nothing, il renvoie cela. S'il obtient Just xs, Il applique tail' à xs et le renvoie.

À partir de là, vous pouvez facilement créer une tondeuse qui réduit les listes avec 0, 1 ou 2 éléments en listes vides:

trim :: [a] -> [a]
trim = maybe [] id . trim'
0
répondu dfeuer 2015-02-04 18:08:57
(head.reverse) [1..100]

Est une alternative à last pour obtenir le dernier élément.

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

Supprime le premier et le dernier élément de liste. La source de drop et take semble être plus rapide que (init . tail).

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

Est une autre variante. Mais je suppose plus lent à cause du double renversement.

-2
répondu orkoden 2015-02-03 16:47:47