Сопоставление со списком, за исключением последнего элемента списка

Как мне лучше всего отобразить все элементы списка, кроме последнего элемента списка?

Скажем, у нас есть список let l = [1,2,3,4] и мы хотим получить [2,3,4,4].

У меня есть решение, но оно не похоже на «функциональный» способ сделать это (в ghci):

let l = [1,2,3,4]
let len = toIntegral $ length l -- to avoid a type mismatch Integer <-> Int
let l1 = zip l [1..]
let l2 = map (\(x,y) -> if y < len then (x + 1,y) else (x,y)) l1
let l3 = map (fst) l2

Не очень приятно... Надеюсь, есть лучший способ! Поскольку я новичок в функциональном программировании, я не знаю, с чего начать поиск.


list functional-programming map-function haskell
person mort    schedule 15.09.2014    source источник

Ответы (5)


arrow_upward
14
arrow_downward

Просто перепишите map, но сделайте особый случай, когда есть только один элемент:

mapBut1 :: (a -> a) -> [a] -> [a]
mapBut1 f [] = []
mapBut1 f [x] = [x]
mapBut1 f (x:xs) = f x : mapBut1 f xs

Теперь это будет работать даже для бесконечных списков, это намного быстрее, чем вычисление длины, и делает его более читабельным. Обратите внимание, что это ограничивает вашу функцию типом a -> a вместо a -> b.

В качестве альтернативы вы можете сделать

mapBut1 f (x:y:xs) = f x : mapBut1 f (y:xs)
mapBut1 f other = other

Это эквивалентные определения, но последнее использует на 1 совпадение с образцом меньше. Однако я бы предпочел первое, поскольку сразу видно, какие дела рассматриваются.

person bheklilr    schedule 15.09.2014
comment
Очень хорошо! Только одно небольшое замечание: разве xs в самой последней строке вашего кода не должно быть x, поскольку мы сопоставляем список длиной 1? - person mort; 15.09.2014
comment
@mort, во-первых, Haskell не волнует, как мы называем переменные, поэтому переименование xs в x не изменит смысла кода. Во-вторых, эта строка соответствует всему, что не соответствует шаблону (x:xs), который может быть [_] или [] ([_] указывает список из одного элемента). Так что это говорит о том, что все, кроме шаблона (x:xs), будет соответствовать, а не один элемент. Однако вы заставили меня заметить небольшую ошибку в этом коде. - person bheklilr; 15.09.2014

arrow_upward
10
arrow_downward

Это работа для притворного параморфизма, как обычно:

import Data.List (tails)

mapButLast :: (a -> a) -> [a] -> [a]
mapButLast f = foldr g [] . tails where
  g (x:_:_) r = f x : r
  g xs      _ = xs

Или с правильным para мы просто напишем

mapButLast f = para g [] where
  g x [] r = [x]
  g x _  r = f x : r

куда

para f z (x:xs) = f x xs (para f z xs)
para f z []     = z
person Will Ness    schedule 15.09.2014
comment
Это хороший узор! - person J. Abrahamson; 15.09.2014
comment
@ J.Abrahamson Я отредактировал еще кое-что со ссылкой. ;) - person Will Ness; 15.09.2014
comment
para — это очевидный способ, но мне нравится идея использовать tails для получения притворного пара. Хотя, когда они оба рядом, я менее уверен, что на самом деле это намного более понятно, чем само para. - person J. Abrahamson; 15.09.2014
comment
@ J.Abrahamson, в конечном счете, они одинаковы - доступ к tails - это то, что делает para (до одного пропущенного удара). с tails он даже может повторно использовать структуру. Иногда нестандартный para f z [] = z; para f z xs@(x:t) = f x xs (para f z t) может быть предпочтительнее, и это именно вариант foldr ... tails. - person Will Ness; 15.09.2014
comment
да, и ничто не ново. - person Will Ness; 15.09.2014
comment
Ага, согласен. Я просто не видел, чтобы это было написано в такой форме раньше. - person J. Abrahamson; 16.09.2014

arrow_upward
4
arrow_downward

Вы также можете использовать init и last из стандартных библиотек (без специального импорта), если вас не волнует производительность.

ты можешь написать

map f (init list) ++ [last list]

куда

  • f : функция, которую вы хотите сопоставить.
  • list : список, который вы хотите сопоставить
person Rvion    schedule 15.09.2014
comment
Это не что плохо с точки зрения производительности, так как init ленив, а last list expr. находится в WHNF перед оценкой. Могу поспорить, что это соответствует принятому ответу O (n) перехода к последнему элементу, который может быть хорошо оптимизирован ghc. - person David Unric; 15.09.2014
comment
@DavidUnric, у него довольно плохие характеристики. В частности, это не очень хороший стример: он будет хранить весь входной список в памяти до тех пор, пока не будет оценен последний элемент. - person luqui; 15.09.2014
comment
Мне нравится это решение, потому что оно читабельно даже для новичков;) - person mort; 15.09.2014

arrow_upward
1
arrow_downward

Что делает этот последний элемент таким особенным?

Я знаю, что это не отвечает на ваш вопрос, но я бы рассмотрел такой тип, как

data Foo a = Foo a [a]

и соответствующий функтор.

person Jean-Baptiste Potonnier    schedule 15.09.2014

arrow_upward
0
arrow_downward

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

reverse $ last l : [f x | x <- tail (reverse l)]

Это медленнее, чем большинство других решений (см. ссылку на отчет ниже).

Вот пример программы (allbutlast.hs). В нем есть все вышеперечисленные решения, простой тест quickcheck и эталонный тест. с использованием критерия.

Предварительные условия для запуска: QuickCheck и критерий

cabal update
cabal install QuickCheck
cabal install -j --disable-tests criterion

Исполнение

ghc -O2 --make allbutlast.hs
./allbutlast --output allbutlast.html

Образец отчета: отчет по критериям для allbutlast

person monk    schedule 17.09.2014