dje*_*lin 2 haskell functional-programming pattern-matching
模式匹配很奇怪.它涉及寻找事物表征的看似简单的数学问题.
例如,对于给定的整数b,每个整数a可以以a = bq + r的形式表示,其中0 <= r <b,唯一.要找到q和r,需要除法算法.关键词是"算法".
因此,当您在Haskell中执行模式匹配表达时,如将元组表示为(a,b),是在幕后运行的算法吗？
算法总是必须简单,即O(1)或至少以某种方式在某处记录？
您如何保证代表的独特升力？
我可能误解了你在说什么,但有一种模式匹配算法.来自语言报告:
3.17.2模式匹配的非正式语义
模式与值匹配.尝试匹配模式可能有三个结果之一:它可能会失败; 它可能会成功,为模式中的每个变量返回一个绑定; 或者它可能分歧(即返回⊥).根据以下规则,模式匹配从左到右,从外到内进行:
- 将模式var与值v匹配总是成功并将var绑定到v.
将模式~apat与值v匹配总是成功.apat中的自由变量绑定到适当的值,如果匹配的是针对v的apat否则会成功,如果匹配的针对v的apat失败或发散,则绑定到⊥.(绑定并不意味着评估.)在操作上,这意味着在使用apat中的一个变量之前,不会对~apat模式进行匹配.此时整个模式与值匹配,如果匹配失败或发散,整体计算也是如此.
将通配符模式_与任何值匹配总是成功,并且不进行任何绑定.
匹配模式conpat一个值,其中con是由newtype定义的构造函数,取决于值:如果值的形式为con v,则pat与v匹配.如果值为⊥,则pat匹配反对⊥.也就是说,与newtype关联的构造函数仅用于更改值的类型.
将模式con pat1 ... patn与值匹配,其中con是由数据定义的构造函数,取决于值:如果值的形式为con v1 ... vn,则子模式从左到右与组件匹配数据值; 如果所有匹配成功,则整体匹配成功; 第一个失败或分歧导致整体匹配失败或分歧.如果值的形式为con'v1 ... vm,其中con是与con'不同的构造函数,则匹配失败.如果值为⊥,则匹配发生偏差.
- 使用带标签的字段与构造函数匹配与匹配普通构造函数模式相同,只是字段按照它们在字段列表中的命名顺序进行匹配.列出的所有字段必须由构造函数声明; 字段可能不会被多次命名.未被模式命名的字段将被忽略(与_匹配).
如果v == k,则将数字,字符或字符串文字模式k与值v匹配成功,其中==基于模式的类型重载.如果此测试发生分歧,则匹配会发生变化.数字文字的解释完全如第3.2节所述; 也就是说,重载函数fromInteger或fromRational应用于Integer或Rational文字(resp)以将其转换为适当的类型.
将as-pattern var @ apat与值v匹配是将apat与v匹配的结果,使用var与v的绑定进行扩充.如果apat对v的匹配失败或发散,那么整体匹配也是如此.
在我链接的文件中,后面还提到了更正式的描述.
你似乎对模式匹配实际上做了什么感到困惑.
机器以固定的表示形式存储所有数据.模式匹配仅允许您查询表示的内容.
您不能使用模式匹配(例如)确定两个任意表达式是否相等.这将需要解决暂停问题,这是不可能的.您只能对数据进行模式匹配,而不是表达式.
例如,模式匹配可以告诉您列表是空还是非空.它可以告诉您列表是否按顺序包含数字1,2,3.例如,它无法告诉您是否sort . map fst产生相同的结果map fst . sort.
所以没有"保证独特代表性"的问题; 无论你是否匹配模式,计算机已经这样做了.模式匹配是模式大小的O(n)时间.(忽略您可能触发的任何延迟评估,这是生成数据的代码的属性,而不是消耗它的代码.)