Haskell:为什么++不允许模式匹配？

Question

假设我们想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

换句话说,为什么我们不能++在模式匹配中使用？

Answer 1

您只能在构造函数上进行模式匹配,而不能在一般函数上进

在数学上,构造函数是一个内射函数:每个参数组合都给出一个唯一值,在本例中是一个列表.因为该值是唯一的,所以该语言可以将其再次解构为原始参数.即,当你模式匹配时:,你基本上使用该功能

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,以其:<|和:|>图案同义词.

Answer 2

这是一个值得考虑的问题,到目前为止它已经得到了明智的答案(只允许构造函数,嘀咕的注入,笨拙的模糊),但仍有时间改变这一切.

我们可以说规则是什么,但大多数解释为什么规则是他们从过度推广问题开始,解决为什么我们不能模式匹配任何旧函数(mutter Prolog).这是为了忽略++不是任何旧函数的事实:它是由列表的拉链结构引起的(空间)线性插件 - 填充函数.模式匹配就是将事物分开,实际上,根据插件 - 注意器和模块变量来表示组件的过程.它的动机是清晰.所以我想

lookup :: Eq k => k -> [(k, v)] -> Maybe v
lookup k (_ ++ [(k, v)] ++ _) = Just v
lookup _ _                    = Nothing

而且这不仅仅是因为它让我想起三十年前我实现了一种功能语言的乐趣,而这种功能语言的模式匹配就是这样.

它含糊不清的异议是合法的,但不是破坏者.Plugger-togetherers ++只提供有限输入的有限多次分解(如果你正在处理无限数据,这是你自己的监视),那么所涉及的是最糟糕的搜索,而不是魔法(发明任意函数可能抛出的任意输入)远).搜索调用某些优先级的方法,但我们的有序匹配规则也是如此.搜索也可能导致失败,但同样可以匹配.

我们有一种合理的方法来管理通过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,我们甚至可以通过他们的洞和根来保持多孔的数据,然后在不断的时间内破坏性地插入.只有你没注意到你这样做,这才是可耻的行为.

Answer 3

您只能在数据构造++函数上进行模式匹配,并且是一个函数,而不是数据构造函数.

数据构造函数是持久的; 类似的值'c':[]不能进一步简化,因为它是类型的基本值[Char]."c" ++ "d"然而,类似的表达式"cd"在任何时候都可以用它的等价物替换,因此不能可靠地指望它存在用于模式匹配.

(您可能会认为"cd"总是可以替换为"c" ++ "d",但一般情况下,列表和分解之间没有一对一的映射++."cde"等同于"c" ++ "de"或"cd" ++ "e"用于模式匹配目的吗？)

Answer 4

++它不是一个构造函数,它只是一个简单的函数.您只能在构造函数上匹配.

您可以使用ViewPatterns或PatternSynonyms增强模式匹配的能力(感谢@luqui).