Haskell: Почему ++ не разрешен в сопоставлении с образцом?
Предположим, мы хотим написать наш собственный sum функция в Haskell:
sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
Почему мы не можем сделать что-то вроде:
sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (xs++[x]) = x + sum' xs
Другими словами, почему мы не можем использовать ++ в сопоставлении с образцом?
4 ответа
Вы можете сопоставлять паттерны только с конструкторами, но не с общими функциями.
Математически конструктор является инъективной функцией: каждая комбинация аргументов дает одно уникальное значение, в данном случае список. Поскольку это значение уникально, язык может снова деконструировать его в исходные аргументы. То есть, когда вы образец совпадения на : вы по существу используете функцию
uncons :: [a] -> Maybe (a, [a])
который проверяет, имеет ли список форму, которую вы могли бы построить : (то есть, если он не пустой), и если да, возвращает вам голову и хвост.
++ не инъективен, хотя, например
Prelude> [0,1] ++ [2]
[0,1,2]
Prelude> [0] ++ [1,2]
[0,1,2]
Ни одно из этих представлений не является правильным, так как же следует снова деконструировать список?
Однако вы можете определить новый, "виртуальный" конструктор, который действует как : тем, что он всегда отделяет ровно один элемент от остальной части списка (если это возможно), но делает это справа:
{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
pattern (:>) :: [a] -> a -> [a]
pattern (xs:>ω) <- (unsnoc -> Just (xs,ω))
where xs:>ω = xs ++ [ω]
unsnoc :: [a] -> Maybe ([a], a)
unsnoc [] = Nothing
unsnoc [x] = Just x
unsnoc (_:xs) = unsnoc xs
затем
sum' :: Num a => [a] -> a
sum' (xs:>x) = x + sum xs
sum' [] = 0
Обратите внимание, что это очень неэффективно, потому что :> паттерн-синоним на самом деле нужно копаться по всему списку, поэтому sum' имеет квадратичную, а не линейную сложность.
Контейнер, который позволяет эффективно сопоставлять шаблоны с левой и правой стороны, Data.Sequence, с этими :<| а также :|> шаблонные синонимы.
Это заслуживающий внимания вопрос, и он до сих пор получил разумные ответы (допускаются только бормотатели, невнятность бормотания, неоднозначность бормотания), но все еще есть время, чтобы все это изменить.
Мы можем сказать, что это за правила, но большинство объяснений, почему правила являются такими, какими они являются, начинаются с чрезмерного обобщения вопроса, касающегося того, почему мы не можем сопоставить шаблоны с какой-либо старой функцией (бормоча Пролог). Это игнорировать тот факт, что ++ это не какая-то старая функция: это (пространственно) линейная функция "соединение-сборка", индуцированная структурой списков на молнии. Сопоставление с образцом - это то, что разбирает вещи на части, и, действительно, отмечает процесс с точки зрения подключаемых устройств и переменных шаблона, обозначающих компоненты. Его мотивация - ясность. Так что я хотел бы
lookup :: Eq k => k -> [(k, v)] -> Maybe v
lookup k (_ ++ [(k, v)] ++ _) = Just v
lookup _ _ = Nothing
и не только потому, что это напомнило бы мне о веселье, которое я имел тридцать лет назад, когда я реализовал функциональный язык, сопоставление с образцом которого предлагало именно это.
Возражение, что это неоднозначно, является законным, но не нарушителем. Плагин-любители, как ++ предлагать только конечное число разложений конечного ввода (и если вы работаете с бесконечными данными, это ваш собственный поиск), так что в данном случае речь идет о худшем поиске, а не о волшебстве (изобретении произвольных входных данных, которые могли бы отбросить произвольные функции). Поиск требует некоторых средств определения приоритетов, но также и наши упорядоченные правила соответствия. Поиск также может привести к сбою, но, опять же, может совпадение.
У нас есть разумный способ управлять вычислениями, предлагая альтернативы (неудача и выбор) через Alternative абстракция, но мы не привыкли думать о сопоставлении с образцом как о форме такого вычисления, поэтому мы используем Alternative структура только на языке выражений. Благородное, если нехорошее, исключение - неудача в совпадении do -нот, который называет соответствующий fail а не обязательно вылетает. Сопоставление с образцом - это попытка вычислить среду, подходящую для оценки выражения "с правой стороны"; Неспособность вычислить такую среду уже решена, так почему бы не сделать выбор?
(Изменить: я должен, конечно, добавить, что вам действительно нужен поиск, только если у вас есть более чем одна растянутая вещь в шаблоне, поэтому предлагаемый xs++[x] шаблон не должен вызывать никаких выборов. Конечно, требуется время, чтобы найти конец списка.)
Представьте, что есть какая-то забавная скобка для письма Alternative вычисления, например, с (|) имея в виду empty, (|a1|a2|) имея в виду (|a1|) <|> (|a2|) и обычный старый (|f s1 .. sn|) имея в виду pure f <*> s1 .. <*> sn, Можно очень хорошо представить (|case a of {p1 -> a1; .. pn->an}|) выполнение разумного перевода поисковых шаблонов (например, с участием ++) с точки зрения Alternative комбинаторы. Мы могли бы написать
lookup :: (Eq k, Alternative a) => k -> [(k, v)] -> a k
lookup k xs = (|case xs of _ ++ [(k, v)] ++ _ -> pure v|)
Мы можем получить разумный язык шаблонов поиска для любого типа данных, генерируемого точками фиксирования дифференцируемых функторов: символическое дифференцирование - это именно то, что превращает кортежи структур в выбор возможных подструктур. Старый добрый ++ Это просто пример списка подсписков (который сбивает с толку, потому что список со списком под дыру очень похож на список, но то же самое нельзя сказать о других типах данных).
Весело, с пятном LinearTypes мы можем даже удерживать данные дырки за их дыры, а также за корень, а затем разрушительно уничтожать их в постоянном времени. Это скандальное поведение, только если вы не замечаете, что делаете это.
Вы можете сопоставлять шаблоны только с конструкторами данных, и ++ это функция, а не конструктор данных.
Конструкторы данных являются постоянными; значение как 'c':[] не может быть упрощено в дальнейшем, потому что это фундаментальное значение типа [Char], Выражение как "c" ++ "d" Однако может заменить его эквивалентным "cd" в любое время, и, таким образом, нельзя надежно рассчитывать на присутствие для сопоставления с образцом.
(Вы можете утверждать, что "cd" всегда можно заменить "c" ++ "d", но в общем случае нет однозначного сопоставления между списком и разложением через ++, Является "cde" эквивалентно "c" ++ "de" или же "cd" ++ "e" для сопоставления с образцом?)
++ не конструктор, это просто простая функция. Вы можете соответствовать только конструкторам.
Ты можешь использовать ViewPatterns или же PatternSynonyms чтобы увеличить вашу способность к сопоставлению с образцом (спасибо @luqui).