Почему хвосты функций Haskell включают весь список?
Введение и контекст
В Haskell у нас есть функция tail, которая предоставляет суффикс списка.
Например:
tail [1,2,3]
дает
[2, 3]
Вместо этого функция Tails выдаст все суффиксы:
tails [1,2,3]
дает
[[1,2,3],[2,3],[3],[]]
Вопрос
Почему он возвращает весь список в качестве первого аргумента? Я ожидал вернуть все настоящие суффиксы, т. е. ожидал
tails [1,2,3]
давать
[[2,3],[3],[]]
или, может быть, даже
[[2,3],[3]]
без пустого списка.
Есть ли формальная/логическая причина, по которой хвосты ведут себя таким образом, или это просто случайно, то есть просто так, как это работало в исходной реализации и никогда не менялось?
Я искал этот вопрос и не нашел этому достойного объяснения.
Что вы предлагаете вернуть за пустой список?
Спорить можно было в любом случае. Почему бы не привести весь список? Легко вычислить «исключающий» вариант tails из «включающего» и наоборот, так что это не составляет большого труда. Тем не менее, любое множество является подмножеством самого себя, поэтому имеет смысл включить и в списки. Также приятно иметь возможность разделить список по всем пунктам как [ .. | (y:ys) <- tails xs ]. Кстати, вы бы тоже поспорили насчет исключения пустого хвоста?
@Chi Я считаю эту часть твоего комментария очень значимой: «любой набор является подмножеством самого себя»
@n.m.couldbeanAI tails [] = [] кажется совершенно разумным выбором, если идти в этом направлении.
@DanielWagner, тогда у вас будет закон, согласно которому каждый список имеет пустой суффикс, за исключением пустого списка, который внезапно кажется неочевидным и произвольным.
Ответы 2
Как сказано в документации Tails :: [a] -> [[a]] [Hackage]:
Функция Tails возвращает все последние сегменты аргумента, начиная с самого длинного.
итак, все суффиксы. Список всегда является суффиксом самого себя. tails по существу реализуется как:
tails :: [a] -> [[a]]
tails [] = [[]]
tails xs@(_:xs') = xs : tails xs'
таким образом, он возвращает сам список и tails его хвоста, если таковой имеется. Если вас интересуют только строгие хвосты, мы можем поработать с хвостом сказки:
tail . tails
который гарантированно будет работать, поскольку для пустого списка tails [] вернет одноэлементный список и, таким образом, (tail . tails) [] затем вернет пустой список.
inits и tails были добавлены в отчет Haskell 98 в разделе «Список» отчета библиотеки. У меня возникли проблемы с поиском хороших цитат, поскольку они, похоже, не упоминались в архивах списков рассылки. Однако я считаю, что было несколько оригинальных мотивов.
Я буду называть текущие версии inits и tailsinits0 и tails0; и определите tails1 = drop 1 . tails0 (опуская полный суффикс) и inits1 = drop 1 . inits0 (опуская пустой префикс).
Вопрос в том, должно ли inits быть inits0 или inits1, и то же самое касается tails.
По возможности нам следует отдавать предпочтение более общим функциям. Однако в этом случае каждое из них может быть выражено через другое, поэтому ни одно из них не является более общим.
zipWith (++) (inits list) (tails list)должен изготовить копии оригиналаlist. Это означает либо(inits, tails) = (inits0, tails0), либо(inits, tails) = (inits1, tails1), но не смесь этих двух.initsвсехtailsдолжны создавать все смежные сегменты входного списка, например.(inits <=< tails) [1, 2, 3]=[[],[1],[1,2],[1,2,3],[],[2],[2,3],[],[3],[]](включая[]один раз для каждого сегмента хвоста). Для(inits1, tails1)это не так.Кроме того, результаты как
inits, так иtailsдолжны быть непустыми, чтобы поддерживать использование частичных функций, таких какmaximum, которые не определены в пустых списках, поскольку это было до того, какData.List.NonEmptyстало стандартом. Опять же,(inits1, tails1)не удовлетворяет этому требованию, например.tails0 [] == [[]]ноtails1 [] == [].
Итак, похоже, нам стоит выбирать (inits, tails) = (inits0, tails0).
Это также согласуется с другими функциями списка, например map sum . inits = scanl' (+) 0 для вычисления префиксной суммы.
Именование немного неудачное, поскольку init и tail всегда отбрасывают один элемент, а inits и tails — нет. Возможно, takes и drops было бы лучше.
«включая [] один раз для каждого сегмента хвоста» — это кажется произвольным. Хотя мне нравятся другие аргументы!
@Bergi: Да, эта часть не является целью, а просто примечанием к примеру. Что ж, это правда, что в списке есть только 1 + length list смещения, из которых можно взять срез нулевой длины, но я не уверен, когда это будет полезно.
Я думаю, что естественным аналогом вашего drop 1 . tails (т. е. только строгие суффиксы, возможно, включая пустой суффикс) является не drop 1 . inits, а скорее reverse . drop 1 . reverse . inits (т. е. только строгие префиксы, возможно, включая пустой префикс) (или, ну, лучше определенное, но не фрагмент -длинная версия того, что не имеет reverse дважды, что-то вроде liftA2 (zipWith const) inits (drop 1 . inits)).
Он возвращает все суффиксы = «настоящие суффиксы» ≠ строгие суффиксы.