Самый быстрый способ получить последний элемент списка в Haskell

Question

Какой самый быстрый способ получить последний элемент списка в Haskell. Также в следующей итерации я хочу удалить первый и последний элемент списка. Какой самый элегантный способ сделать это? Я пытаюсь понять список, но это выглядит не очень эффективно!

Answer 1

Вы можете использовать функцию last , чтобы получить последний элемент списка.

Что касается удаления первого и последнего элементов, вы можете использовать (init . tail),но я не знаю, насколько это эффективно.

Мне кажется, это изображение из Learn You A Haskell довольно хорошо показывает функции списка:

Answer 2

last и init отлично справятся с работой за раз.Однако они оба O (n) , поэтому, если вам нужно часто манипулировать обоими концами списка, как вы, вероятно, подразумеваете, вы можете рассмотреть возможность использования Data.Sequence вместо, который поддерживает O (1) вставку и удаление элементов на обоих концах.

Answer 3

Я опубликую реализацию Prelude, поскольку она еще не была опубликована:

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

Обратите внимание, что я изменил имя функции на listLast, чтобы ее можно было запускать без конфликта с обычной Prelude,Вы могли бы, конечно, сделать import Prelude hiding(last).

Answer 4

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

Для следующего вам понадобится

import Control.Monad ((>=>))

и вам нужно будет либо использовать GHC 7.10 и импортировать Data.List (uncons), либо определить

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

Вы можете написать безопасную форму init, например:

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

Версия tail может быть написана

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

Итак, вы можете получить, возможно,

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

>=> является своего рода отсталой монадической композицией. init' >=> tail' - это функция, которая применяет init' к своему аргументу для получения Maybe [a]. Если он получает Nothing, он возвращает это. Если он получает Just xs, он применяет tail' к xs и возвращает его.

Исходя из этого, вы можете легко создать триммер, который обрезает списки с 0, 1 или 2 элементами до пустых списков:

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

Answer 5

(head.reverse) [1..100]

Является альтернативой last для получения последнего элемента.

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

удаляет первый и последний элемент списка.Источник для drop и take выглядит так, как будто он может быть быстрее, чем (init . tail).

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

- другой вариант.Но я думаю, медленнее из-за двойного обращения.

Answer 6

Для удаления первого и последнего:

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

или, может быть,

init (drop 1 l)

Это также приводит к почти оптимальному коду.