本章我们将用第十章开发的图像分析库来制作一个条形码识别应用。只要用手机的摄像头拍下书的封底，我们就能用这个程序来提取这本书的ISBN编号。
市售绝大多数带有外包装的量产消费品上都有一个条形码。尽管有很多种不同的条形码系统在多个专业领域中被使用，但是在消费品中最典型的条形码系统还是UPC-A和EAN-13两种。UPC-A由美国开发，而EAN-13最初由欧洲开发。
EAN-13发表于UPC-A之后，它是UPC-A的超集。（事实上，尽管UPC-A现在在美国依然被广泛使用，但该标准早在在2005年已经被官方宣布作废了。)任何可以识别EAN-13条形码的硬件都可以兼容UPC-A条形码。这样我们只介绍EAN-13一种标准就可以了。
正如其名字所暗示的，EAN-13描述了一个由13个数字组成的序列，该序列可以分为四组：
[译注1：确切的讲，此处的“生产商所在国”实际上是指“为该生产商分配生产商代码的编码管理局所属国家”]
[译注2：事实上，码制的长度可能为两位甚至更多位，但目前GS1GeneralSpecifications中给出的最长的码制也只有3位。例如某条形码的类别是ISBN码的话，那么它的码制部分应该为978(后文中给出的实际图中也可以看到)；如果类别是ISSN(InternationalStandardSerialNumber，国际标准连续出版物号)，则码制为977。其他部分的长度也比本章介绍的要更有弹性，但这些差异并不会影响对本章内容的理解。事实上，这一部分的内容在本章后面的内容中也完全用不到，因为我们在从条码的图形中提取出数字序列后，并没有进一步分离出各个分组乃至查询每个分组表示的具体信息。]
EAN-13条形码与UPC-A条形码的唯一不同在于后者只用一位数字表示码制。EAN-13条形码通过将码制的第一位数字置零实现对UPC-A的兼容。
在考虑怎样解码EAN-13条形码之前，我们还是得先了解它是怎样被编码出来的。EAN-13的编码规则有一点复杂。我们先从计算校验码——即数字串的最后一位开始。
--file:ch12/Barcode.hscheckDigit::(Integrala)=>[a]->acheckDigitds=productSum`mod`10`mod`10whereproductSum=sumproducts(mapEveryOther(*3)(reverseds))mapEveryOther::(a->a)->[a]->[a]mapEveryOtherf=zipWith($)(cycle[f,id])[译注1：原文对checkDigit函数的实现有问题，翻译时用了比较直接的方法修正了代码，并相应的修改了下面一段正文中对代码的描述]
[译注2：你可能觉得如果把mapEveryOther中的f和id两个列表元素的位置对调的话，就可以省略掉checkDigit的where块中的reverse过程。事实上这个reverse过程是必须的，而且f和id也不能对调。因为EAN-13的标准规定，“将序列中的最右侧的数字规定为奇数位，从最右侧开始，其余数字被交替记为偶数位和奇数位，而只有奇数位的数字会被乘以3。如果采取最开始说的方法，那么假如输入的序列包含偶数个元素的话，那么整个计算过程就是错误的。这一点的重要性在后文会有体现。]
直接看代码应该比文字描述更有助于理解校验码的计算方法。函数从数字串的最右一位数字开始，每隔一位就将该数字乘以3，其余保持原状。接下来对处理后的列表求和，校验码就是将这个列表的和对10取模两次得到的结果。
条形码是一系列定宽的条纹，其中黑色的条纹表示二进制的“1”，白色的条纹表示二进制的“0”。表示相同二进制的条纹值连续排列看起来就是宽一些的条纹。
条形码中的各个二进制位的顺序如下：
左右两个分组中的数字有不同的编码。左侧分组的数字编码包含了校验位(paritybit)，而校验位编码了条形码的第13个数字。
[译注：请注意区分此处所提到的校验位(paritybit)以及后面会经常提及的校验码(checkdigit)，在本文中，只需要将这个校验位理解为一种只由二进制编码模式(pattern)来区分(而不是“计算”)的信息，并且了解它只包含奇和偶两种取值即可，没必要深究“哪一位是校验位”。]
在继续前，我们先来看看在本章接下来会用到的所有导入模块。
最简单的数组类型位于Data.Array模块，它正是我们要此处要用到的类型。该类型可以表示由任何Haskell类型的值构成的数组。与普通的Haskell类型一样，该类型的数组都是不可变的。不可变的数组的值只能在它被创建的时候填充一次，之后它的内容就无法被修改了。(标准库也提供了其他的数组类型，其中有一部分是可变的，但我们暂时还不会涉及到它们。)
Data.Array模块中的listArray函数使用列表来填充数组。第一个参数是数组的边界，第二个参数是用来填充数组的列表。
数组有一个独特的性质，它的类型由它所包含数据的类型以及索引的类型共同决定。举例来说，String组成的一维数组的类型为ArrayIntString，而二维String数组的类型则是Array(Int,Int)String。
ghci>:m+Data.Arrayghci>:typelistArraylistArray::(Ixi)=>(i,i)->[e]->Arrayie创建数组很简单。
我们这里用到的数组类型对数组的元素采用了非严格求值。如果我们想用一个包含三个元素的列表填充一个多于三个元素的数组，那么其余的元素将是未定义的。但是只有我们试图访问超过第三个元素的时候才会发生错误。
bounds函数返回在创建数组时用来指定边界的元组。indices函数返回数组中各个索引值组成的列表。我们可以用它们来定义实用的折叠函数，因为Data.Array模块本身并没有提供用于数组的折叠函数。
上述这些相似性对于二维数组就已经不再成立了。首先，在二维数组上有意义的折叠方式有很多种。我们也许仍然想要逐个元素地进行折叠，但是对二维数组，还可以逐行折叠或者逐列折叠。其次，就算同样是逐个元素折叠，在二维数组中也不再是只有两种遍历方式了。
换句话讲，对于二维数组来说，有意义操作组合太多了，可也没什么足够的理由选取其中一部分添加到标准库。这个问题只存在于多维数组，所以最好还是让开发人员自己编写合适的折叠函数。从上面的例子也可以看出，这其实没什么难度。
尽管存在用来“修改”不可变数组的函数，但其实都不怎么实用。以accum函数为例，它接受一个数组和一个由(索引，元素值)值对构成的列表，返回一个新数组，其中所有在指定索引位置的元素都被替换为指定的元素值。
由于数组是不可变的，所以哪怕只是修改一个元素，也需要拷贝整个数组。哪怕对于中等规模的数组，这种性能开销也可能很快变得难以承受。
Data.Array.Diff模块中的另一个数组类型DiffArray，尝试通过保存数组的连续版本之间的变化量来减少小规模修改造成的开销。遗憾的是，在编写本书的时候它的实现还不是很高效，对于实际应用来说，它还是太慢了。
Note
不要失望
事实上，在Haskell中高效地修改数组是可能的——使用STmonad即可。我们以后会在第二十六章中讨论这个话题。
让我们简单的探索一下用元组替代数组的可行性
尽管我们的目标是对条形码进行解码，但要是能有一个编码器做参考还是很方便的。这样我们就可以检查decode.encode的输出是否与输入相同，以此来验证代码的逻辑是否正确。
输入编码器的字符串包含12个数字，encodeDigits函数会添加第13位数字，即校验码。
[译注：这里所指的“编码器”指的是encodeEAN13函数。]
条形码的编码分为两组，每组各6个数字，两个分组的中间和“外侧”各有一个保护序列。现在里面的两组共12个数字已经编码好了，那么剩下的那一个数字哪儿去了？
左侧分组中的每个数字都使用奇校验(oddparity)或偶校验(evenparity)进行编码，具体使用的编码方式取决于数字串中的第一个数字的二进制表示。如果第一个数字中某一位为0，则左侧分组中对应位置的数字采用偶数校验编码；如果该位为1，则该对应数字采用奇校验编码。这是一种优雅的设计，它使EAN-13条形码可以向前兼容老式的UPC-A标准。
在讨论如何解码之前，我们先对可处理的条形码图片的种类做一些实际约束。
手机镜头和电脑摄像头通常会生成JPEG图像，但要写一个JPEG的解码器又要花上好几章的篇幅，因此我们将图片的解析工作简化为只需要处理netpbm文件格式。为此，我们会用到第十章中开发的解析组合子。
我们希望这个解码器能处理用低端手机上那种劣质的定焦镜头拍摄出来的图像。这些图像往往丢焦严重、噪点多、对比度低，分辨率也很低。万幸，解决这些问题的代码并不难写。我们已经实际验证过本章中的代码，保证它能够识别用货真价实的中低端摄像头拍摄出的实体书上的条形码。
我们会绕过所有的涉及复杂的图像处理的内容，因为那又是一个需要整章篇幅来介绍的课题。我们不会去校正拍摄角度，也不会去锐化那些由于拍摄距离过近导致较窄的条纹模糊不清，或者是拍摄距离过远导致相邻的条纹都糊到一起的图像。
[译注：上面三幅图分别展示了非正对条形码拍摄、拍摄距离过近、拍摄距离过远的情况]
我们的任务是从摄像头拍摄的图像中提取出有效的条形码。这个描述不是特别明确，我们很难以此规划如何一步步展开行动。然而，我们可以先把一个大问题拆分为一系列的独立且易处理的子问题，随后再逐个击破。
我们接下来会看到，上述的子问题中有些还可以进一步分解。
在编写本章给出的代码时你可能会问，这种分而治之的实现方式与最终方案的吻合程度有多高呢？答案是——我们远不是什么图像处理的专家，因此在开始撰写这一章的时候我们也不是很确定最终的解决方案会是什么样子。
关于到底什么样的方案才是可行的，我们事先也做了一些合理的猜测，最后就得到了上面给出的子任务列表。接下来我们就可以开始着手于那些知道如何解决的部分，而在空闲时考虑那些我们没有实际经验的内容。我们当时肯定是不知道有什么既存的算法可用，也没有提前做过什么总体规划。
像这样分解问题有两大优点。首先，通过在熟悉的领域开展实施，可以让人产生“已经开始切实解决问题”的积极情绪，哪怕现在做的以后不见得用得上也是一样。其次，在处理某个子问题时，我们可能会发现可以将它进一步分解为多个我们熟悉解决思路的子问题。我们可以继续专注于其中简单的部分，而把那些还没来得及彻底想通的部分延后，一个一个的处理上面子问题列表中的项。最后，等我们把不熟悉的和未解决的问题都搞定了，对最终的解决方案也就能心中有数了。
这个解码器处理的对象是条形码，条形码的本质就是连续的黑白条纹序列，而我们还想让这个解码器尽可能的简单，那么最容易处理的表示形式就是黑白图像——它的每个像素都是非黑即白的。
[译注：原文此处提到的图像是monochromeimage(单色图像)，其中monochrome(单色的)一词虽然经常被当作blackandwhite或grayscale的同义词使用(在图像领域)，但实际上这个词表达比了“黑白”更广泛的颜色范围，单色图像可选的颜色并不限于黑和白，例如夜视设备生成的图像，它同样是一种单色图像，但是它生成的图像通常采用绿色为前景色。换句话说，黑白图像只是单色图像的一种。详情参见英文维基词条monochrome。由于本章节中对图像的处理的确是要将图像处理为只有黑白两种颜色像素的图像(也确实不该考虑其他的颜色组合)，因此本章中的monochromeimage都译为黑白图像。]
我们之前说过，我们的解码器将只支持netpbm图像。netpbm彩色图像格式只稍微比第十章中处理的灰度图像格式复杂一点点。其头部的识别串为“P6”,头部的其余部分都和灰度格式完全一样。在图像文件的主体部分，每个像素都由3个字节表示，分别对应红、绿、蓝3个颜色分量。
我们将图像数据表示为像素构成的二维数组。为了帮我们积累数组的使用经验，此处将完全采用数组实现。但实际上对于这个应用来说，我们用“列表的列表”代替数组也可以。因为数组在这里的优势不明显，它的唯一的好处就是很方便取整行。
--file:ch12/Barcode.hstypePixel=Word8typeRGB=(Pixel,Pixel,Pixel)typePixmap=Array(Int,Int)RGB我们定义了一些类型的同义词来提高类型签名的可读性。
Haskell为数组提供了相当高的自由度，我们必须维数组选择一种合适的表示形式。这里我们将采取保守的方案，并遵守一个普遍的约定：索引值从0开始。我们不需要显式的存储图像的尺寸，因为用bounds函数可以从数组直接提取尺寸。
最终的解析器实现相当的简短，这都多亏了我们在第十章中开发的组合子。
--file:ch12/Barcode.hstypeGreymap=Array(Int,Int)PixelpixmapToGreymap::Pixmap->GreymappixmapToGreymap=fmapluminance上面给出来的pixmapToGreymap函数只是拿来举个例子，因为我们只需要检查图片的部分行来提取可能存在的条形码，也就没必要在以后用不到的数据上做多余的转换工作了。
接下来要处理的子问题是如何将灰度图像转换为二值图像，二值图像的每个像素都只处于“打开”或“关闭”两种状态之一。
..FIXME:此处的digit做value译..FIXME:本段里的bit应该是指pixel
在一个图像处理程序中通常需要同时处理大量的数值，有时为了方便，可能会把同一种数值类型用于不同的目的。例如，我们只要约定数字1表示一个像素处于“打开”状态，而0表示一个像素处于“关闭”状态，就可以直接使用Pixel类型表示像素的开/关状态了。
然而，这种做法有潜在的迷惑性。如果想知道某个特定的Pixel类型的值究竟是代表一个数值还是一个“开”/“关”状态，就不能靠类型签名轻易确定了。在某些场景中，我们可能很轻易的就使用了错误类型的数值，而且编译器也不会检查到错误，因为这个值的类型与签名指定的类型是吻合的。
编译器将把Pixel和Bit当做完全相同的类型，所以就算把Pixel类型的值253传给一个接受Bit类型的值(0或1)的函数，编译器也不会报错。
如果另外定义一个单色(monochrome)类型，编译器就会阻止我们像上述的例子那样意外混用不同类型。
[译注：针对这段代码，需要指出一个关于RGB颜色模式的注意点。在前面我们通过luminance函数将要给彩色图片中的像素中的三个颜色分量转换为了一个灰度值，这个灰度值可以理解为“当一个RGB颜色的三个分量同时取该值的时候该像素的颜色”。在这个定义下，纯白色的灰度值为255，随着灰度值越来越小，这个颜色将会呈现为越来越深的灰色，直到灰度值为0，此时该像素为纯黑色。可见这里有一个比较反直觉的地方，即“灰度值越大，颜色越浅”。这个特征反映到二值化函数threshold的返回值中就是“深色的像素返回值为Zero，浅色的像素返回值为One”。]
让我们暂时回过头来想一想，在我们把图像从彩色转换为黑白的过程中，到底对它做了哪些处理。下面是一张用VGA分辨率的摄像头捕获的图像。我们做的就是把这个图像“压缩”到只剩下足够识别条形码的内容。
这之中编码的数字序列，9780132114677，被打印在了条形码的下方。左侧分组编码了数字串780132，第一位数字9也被隐含在该组每个数字编码的奇偶性中。右侧分组编码了数字串114677，其中最后一个7为校验码。下面是这个条形码的清晰版本，是我们在一个提供免费条形码图片生成服务的网站得到的。
[译注：本段中所说的“奇偶性”指的是“左侧分组中的某个数字是采用的奇校验编码还是偶校验编码”，为了避免啰嗦，在后文中都会采用这个说法；本章中并没有涉及自然数中“奇偶性”的概念，请注意与之区分。]
我们从捕获的图像中选择了一个行。为了便于观察，我们将这一行垂直拉伸，然后把它放在“完美图像”的上方并且做了拉伸让两幅图像对齐。
图中用深灰色标出的是经过亮度转换处理的行。可以看到，这部分图像对比度低，清晰度也很差，有多处模糊和噪点。浅灰色标出的部分来自于同一行，但是对比度经过了调整。
更靠下的一小段的显示了对亮度转换过的行进行二值化后的效果。你会发现有些条纹变得更粗了而有些更细了，有些条纹还稍微左移或者右移了一点距离。
[译注：“亮度转换”即上面的luminance函数进行的处理，将彩色图像转换为灰度图像；“二值化”即上面的threshold函数进行的处理，将灰度图像中的像素进行二值化。]
可见，要在具有这些缺陷的图像中找出匹配结果显然不是随随便便就能做到的。我们必须让代码足够健壮以应对过粗、过细或者位置有偏差的条纹。而且条纹的宽度取决于摄像头与书的距离，我们也不能对它做任何假设。
我们首先要面对的问题，是如何在某个可能编码了数字的位置把这个数字找出来。在此，我们要做一些简单的假设。第一个假设是我们处理的对象是图像中的单一行，第二个假设是我们明确知道条形码左边缘位置，这个位置即条形码的起始位置。
我们如何解决线条宽度的问题呢。答案就是对图像数据进行游程编码(runlengthencode)。
--file:ch12/Barcode.hstypeRun=InttypeRunLengtha=[(Run,a)]runLength::Eqa=>[a]->RunLengtharunLength=maprle.groupwhererlexs=(lengthxs,headxs)group函数会把一个列表中所有连续的相同元素分别放入一个子列表中。
group[1,1,2,3,3,3,3][[1,1],[2],[3,3,3,3]]我们的runLength函数将(group返回的列表中的)每个子列表表示为子列表长度和首个元素组成的对。
ghci>letbits=[1,1,0,0,1,1,0,0,1,1,1,1,1,1,0,0,1,1,1,1]ghci>runLengthbitsLoadingpackagearray-0.1.0.0...linking...done.Loadingpackagecontainers-0.1.0.1...linking...done.Loadingpackagebytestring-0.9.0.1...linking...done.[(2,1),(2,0),(2,1),(2,0),(6,1),(2,0),(4,1)][译注：上述ghci输出的最后一行的列表中，每一个“长度-值”对就是一个“游程”]
由于我们进行游程编码的数据只包含0和1，因此编码的数字只会在0和1两个值之间变化。既然这样，我们就可以只保留长度而丢弃被编码数字，而不会丢失任何有用的信息。
--file:ch12/Barcode.hsrunLengths::Eqa=>[a]->[Run]runLengths=mapfst.runLengthghci>runLengthsbits[2,2,2,2,6,4,4]上面给出的位模式并不是我们随便编出来的；而是上面我们捕获的图像中的某一行里面的编码的左侧保护序列和第一个编码数字。如果我们丢弃表示保护序列的条纹，游程编码后的值就是[2,6,4,4]。我们怎样在“引入数组”一节中的编码表中找到匹配的位模式呢？
[译注2：如果你实在看不出这个游程编码的值是如何表示之前捕获的图像中数字的，这里我们来详细解释一下。前文说过，由于条纹在照片中的实际宽度受到拍摄距离等因素的影响，因此我们不能对其有任何假设。而且一般来说，条形码中表示每1位的条纹所占的宽度几乎不可能只有1个像素，而是会由纵向上的复数个像素表示一位。比方说上面给出的序列，很明显就是用了两个像素来表示每个1个二进制位，其实际表示的二进制序列为“01010001100”(0为黑色，1为白色)，当”以1为黑色，0为白色”时，该序列即“10101110011”。这样就可以看出，该序列就是由“101”(左侧保护序列)和“0111001”(倒数第2位识别错误的“7”的奇校验编码)以及下一位数字的第一个二进制位”0”组成的了。]
一个合理的方法是缩放这些游程编码值，让它们的和为1。我们将使用RatioInt类型替代一般的Double类型来保存这些缩放后的值，因为Ratio值在ghci的输出中可读性更好。这点可以为交互式调试与开发提供方便。
我们可以用scalarToOne函数来缩放我们所要寻找的数字序列。我们解决了拍摄距离所导致的条纹宽度不能确定的问题。现在，在缩放后的游程编码表和从图像中的提取出游程编码序列间应该有十分接近的匹配。
接下来的问题是如何将直观感觉上的“十分接近”转化为对“足够接近”的度量。给出两个缩放过的长度序列，我们可以像下面这样计算出一个大概的“差异度”(distance)。
精确匹配的两个值之间的差异度是0，匹配程度越低，差异度的值就越大。
ghci>letgroup=scaleToOne[2,6,4,4]ghci>distancegroup(headleftEvenSRL)13%28ghci>distancegroup(headleftOddSRL)17%28对给定的一个经过缩放的游程编码表，我们从中选择与输入序列最接近的几个匹配结果。
我们还可以在列表推导式的右侧为生成器指定guard。guard是一个Bool表达式。如果guard的值为False,则该元素被跳过。
ghci>[(a,b)|a<-[1..6],b<-[5..7],even(a+b^2)][(1,5),(1,7),(2,6),(3,5),(3,7),(4,6),(5,5),(5,7),(6,6)]其中还可以用let表达式绑定本地变量(localvariable)。
ghci>letvowel=(`elem`"aeiou")ghci>[x|a<-"etaoin",b<-"shrdlu",letx=[a,b],allvowelx]["eu","au","ou","iu"]如果生成器表达式中的某个模式匹配失败了，那么也不会有错误发生，只会跳过未匹配的列表元素。
--file:ch12/Barcode.hsdataParitya=Evena|Odda|Noneaderiving(Show)fromParity::Paritya->afromParity(Evena)=afromParity(Odda)=afromParity(Nonea)=aparityMap::(a->b)->Paritya->ParitybparityMapf(Evena)=Even(fa)parityMapf(Odda)=Odd(fa)parityMapf(Nonea)=None(fa)instanceFunctorParitywherefmap=parityMap我们将匹配到的数字包装在该数字的实际编码所采用的奇偶性内，并且使它成为一个Functor实体，这样我们就可以方便的操作奇偶编码值(parity-encodedvalues)了。
[译注：此处所说的“奇偶编码值”可以理解为“对同一个数字同时具有奇校验编码和偶校验编码两种形式的编码值”(即左分组中所有的编码值都是“奇偶编码值”)，为了简化描述，后文也会采用这种简称，请读者留意。]
我们可能需要对奇偶编码值按它们包含的数字进行排序。Data.Function模块提供的一个好用的组合子on可以帮助我们实现这个功能。
--file:ch12/Barcode.hson::(a->a->b)->(c->a)->c->c->bonfgxy=gx`f`gycompareWithoutParity=compare`on`fromParity它的作用可能不是很明确，你可以试着去想象这样一个函数：它接受两个参数f和g，返回值是一个函数，这个返回的函数也有两个参数，分别为x和y。on将g分别对x和y应用，然后将f应用于这两个结果(所以它的名字叫on)。
把匹配数字装入奇偶性的方法一目了然。
--file:ch12/Barcode.hstypeDigit=Word8bestLeft::[Run]->[Parity(Score,Digit)]bestLeftps=sortBycompareWithoutParity ((mapOdd(bestScoresleftOddSRLps))++ (mapEven(bestScoresleftEvenSRLps)))bestRight::[Run]->[Parity(Score,Digit)]bestRight=mapNone.bestScoresrightSRL一旦在奇校验表或偶校验表里找到了左侧分组某个编码的几个最佳匹配，我们就可以将他们按照匹配的质量排序。
定义Parity类型时,我们可以使用haskell的记录(record)语法来避免手写formParity函数。也就是说，可以这么写：
--file:ch12/Barcode.hsdataAltParitya=AltEven{fromAltParity::a} |AltOdd{fromAltParity::a} |AltNone{fromAltParity::a} deriving(Show)那我们为什么没这么做呢？答案说起来有些丢人，而且与ghci的交互调试有关。当我们告诉GHC让它自动把一个类型派生为Show的实体时，GHC会根据我们是否使用记录语法来定义这个类型而生成不同的代码。
ghci>show$Even1"Even1"ghci>show$AltEven1"AltEven{fromAltParity=1}"ghci>length.show$Even16ghci>length.show$AltEven127使用记录语法定义生成的Show实体明显很“啰嗦”，同时这也会给调试带来很大的干扰。比方说在我们检查ghci输出的奇偶编码值列表的时候，这样的输出结果会特别长以至于我们不得不一行行地扫读输出结果。
当然我们可以手动实现干扰更少的Show实体。避开记录语法写起来也更简洁，而且通过编写我们自己的formParity函数可以让GHC帮我们派生输出更简洁的Show实例。其实也并不是非这么做不可，但是程序员的惰性有时也的确会为代码引入一些特别的做法。
使用列表时常常需要对它进行分块(chunk)。例如，条形码中的每个数字都由四个连续的数字编码而成。我们可以将表示一个行的列表转换为如下这种包含四个元素的列表组成的列表。
--file:ch12/Barcode.hschunkWith::([a]->([a],[a]))->[a]->[[a]]chunkWith_[]=[]chunkWithfxs=let(h,t)=fxs inh:chunkWithftchunksOf::Int->[a]->[[a]]chunksOfn=chunkWith(splitAtn)像这种需要手写泛型的列表操作函数的情况比较罕见。因为一般在Data.List模块里翻一翻就能找到完全符合要求或者基本满足需要的函数。
这几个辅助函数一旦就绪，为每个数字分组生成候选匹配的函数也就很容易搞定了。首先，我们先得做一些前期的检查，来确定这些匹配是否都是有意义的。只有以黑色(Zero)条纹开始，并且条纹数量足够多的游程列表才是有意义的。下面是这个函数中的前几个等式。
--file:ch12/Barcode.hscandidateDigits::RunLengthBit->[[ParityDigit]]candidateDigits((_,One):_)=[]candidateDigitsrle|lengthrle<59=[][译注：代码中的59表示条形码中的条纹数，它是这样求出的：3(左侧保护序列101)+4x6(每个数字的条纹数目4x左侧分组的数字数)+5(两个分组中间的保护序列10101)+4x6(同左分组)+3(右侧保护序列)=59。]
只要任意一次bestLeft或bestRight的应用得到一个空列表，我们都不能返回有效结果。否则，我们将丢弃Score值，返回一个由标记了编码奇偶性的候选数字列表组成的列表。外部的列表有12个元素，每个元素都代表条形码中的一个数字。子列表中的每个数字都根据匹配质量排序。
下面给出这个函数的其余部分
--file:ch12/Barcode.hscandidateDigitsrle|anynullmatch=[]|otherwise=map(map(fmapsnd))matchwherematch=mapbestLeftleft++mapbestRightrightleft=chunksOf4.take24.drop3$runLengthsright=chunksOf4.take24.drop32$runLengthsrunLengths=mapfstrle我们看一看从上面图像中提取出的每个线条分组(表示一个数字的四个线条算作一组)对应的候选数字。
ghci>:typeinputinput::[(Run,Bit)]ghci>take7input[(2,Zero),(2,One),(2,Zero),(2,One),(6,Zero),(4,One),(4,Zero)]ghci>mapM_print$candidateDigitsinput[Even1,Even5,Odd7,Odd1,Even2,Odd5][Even8,Even7,Odd1,Odd2,Odd0,Even6][Even0,Even1,Odd8,Odd2,Odd4,Even9][Odd1,Odd0,Even8,Odd2,Even2,Even4][Even3,Odd4,Odd5,Even7,Even0,Odd2][Odd2,Odd4,Even7,Even0,Odd1,Even1][None1,None5,None0][None1,None5,None2][None4,None5,None2][None6,None8,None2][None7,None8,None3][None7,None3,None8]
在命令式语言中，数组的地位就像是Haskell中的列表或元组，不可或缺。命令式语言中的数组通常是可变的，即我们随时可以修改数组中的元素值，我们对这点也习以为常。
正如我们在“修改数组元素”一节中提到的一样，Haskell数组并不是可变的。这意味着如果要“修改”数组中的单个元素，整个数组都要被复制一次，被修改的元素将在复制的过程中被设置为新的值。显然，以这种方法“修改”数组不可能在性能比拼中获胜。
可变数组还被用来构建另一种命令式语言常见数据结构——散列表(hashtable)。在散列表的典型实现中，数组扮演了“脊柱”的角色：数组中的每个元素都是一个列表。在散列表中添加一个元素时，我们通过对元素进行散列(hash)，确定这个元素在数组中的偏移，然后修改位于这个偏移的列表，把这个元素添加进去。
如果构造散列表所使用的数组不是可变的，那么如果要更新一个散列表的话，我们就不得不创建一个新的数组——先复制原数组，然后把一个新的列表放到由散列值确定的偏移位置上。我们不需要复制其他偏移位置上的列表，但是由于必须复制这个“脊柱”，性能方面已经遭到了致命打击。
不可变的数组一下就让我们的工具箱中两种命令式语言中的典型数据结构直接下岗。可见数组在纯Haskell代码中的确不像在许多别的语言中那么有用。不过，有很多涉及数组的代码都只是在构建阶段更新数组，构建完成后都将其当作只读的数组来使用。
[译注：此处的“构建阶段(buildphase)”并不仅限于用listArray函数或者直接调用构造器函数，还包括“原始的”数组生成完毕，进行后续的值设置的过程，这些过程中可能包含对数组的修改(以及底层的复制)操作。]
但事实上，用不了可变的数组和散列表并没有想象中那么悲剧。数组和散列表经常被用作由键索引的值的集合，而在Haskell中，我们使用树来实现这个功能。
在Haskell中实现一个简单的树类型非常简单。不仅如此，更实用的树类型实现起来也是出奇的简单。比方说红黑树。红黑树这种自平衡结构，就是因为其平衡算法出了名的难写，才让几代CS在校生闻风丧胆。
对函数式程序员来说，树的吸引力在于修改代价低。我们不用打破不可变原则：树就和其他东西一样不可变。然而，我们修改一棵树的时候，可以在新旧两棵树之间共享大部分的结构。举例来说，有一颗有10000个节点的树，我们可能想要在里面添加或者移除一个节点，这种情况下，新旧两棵树能够共享大约9985个节点。换句话说，每次更新树的时候所需要修改的元素数目取决于树的高度，或者说是节点数的对数。
Haskell标准库提供了两种采用平衡树实现的集合类型：Data.Map用于键/值对，Data.Set用于集合。鉴于在下一节会用到Data.Map，我们就先简要地介绍一下这个模块。Data.Set与Data.Map很相似，相信你应该也能很快掌握。
关于性能
一个具有良好实现的纯函数式树结构与散列表在性能上应该是可以一较高下的。你不应该在你的代码会付出性能代价的假设下实现树类型。
Data.Map模块提供了参数化类型Mapka,将键类型k映射到关联值类型a。尽管其内部为一个size-balancedtree，但是它的实现对我们是不可见的。
[译注1：Size-BalancedTree（SBT）是一种通过大小(Size)域来保持平衡的二叉搜索树，因此得名。]
[译注2：原文对于value的使用有些混乱。为了明确表达，从此处开始，key都译为“键”，而value在表达“map中由key所映射到的值”时都译为“映射值”]
Map的键是严格求值的，但是映射值却是非严格求值。换句话说，map的脊柱，或者说结构，是一直在更新的，但是map中映射的值还是要等到我们强迫对它们求值的时候才被计算出来。
记住这点很重要，因为对于不期望内存泄漏的程序员来说，Map类型对映射值采用的惰性求值策略往往是内存泄漏的源头。
由于Data.Map模块包含几个与Prelude模块中冲突的名字，所以它通常用限定形式导入。本章靠前的部分中，我们再导入它时添加了一个前缀M。
Map类型并不对键值的类型做任何显式的约束，但是该模块中多数实用函数都要求键类型为Ord类型类的实体。需要强调的是，这里体现了Haskell中一个常见设计模式：类型约束的设置应该推迟到最终应用的地方，而不需要库作者为这种事情做额外劳动。
Map类型和该模块中的函数都没有对映射值的类型设置约束。
由于某些原因，Data.Map模块中的某些函数的类型签名并不便于部分应用。函数操作的map总是作为最后一个参数，但是它们是第一个参数才更便于局部应用。结果造成使用部分应用Map函数的代码几乎总得通过适配函数(adapterfunction)来调整参数顺序。
Data.Map模块有一个巨大的“暴露区”(surfacearea)：它导出了很多函数。而其中只有为数不多的几个函数算得上是该模块中最常用的核心部分。
如果需要创建一个空的map,可以使用empty函数。如果要创建包含一个键/值对的map，则应该使用singleton函数。
ghci>M.emptyLoadingpackagearray-0.1.0.0...linking...done.Loadingpackagecontainers-0.1.0.1...linking...done.fromList[]ghci>M.singleton"foo"TruefromList[("foo",True)]由于Map的实现对我们是透明的，我们就无法对Map类型的值进行模式匹配。不过，该模块提供了一些查找函数可供我们使用，其中有两个函数应用特别广泛。查找函数有一个稍微复杂的类型签名，但是不要着急，这些很快在第14章中都会弄明白的。
ghci>:typeM.lookupM.lookup::(Ordk,Monadm)=>k->M.Mapka->ma返回值中的类型参数m通常是Maybe类型。话句话说，如果map中包含具有给定键的映射值，lookup函数会把映射值装入Just返回。否则返回Nothing。
ghci>letm=M.singleton"foo"1::M.MapStringIntghci>caseM.lookup"bar"mof{Justv->"yay";Nothing->"boo"}"boo"findWithDefault函数额外指定一个参数值，如果map中不包含查找的键，则返回该指定值。
小心部分应用函数！
有一个(!)运算符会查找键并且返回与该键关联的原始值（即，不是返回装在Maybe或者其他什么东西里的值)。不幸的是，这并不是一个全函数：如果该键在map中不存在的话，它会调用error。
要在map中添加一个键值对，最有用的函数是insert和insertWith’。insert函数就是简单的在map中插入键/值对，如果该键已经存在，则覆盖其关联的任何值。
delete函数从map中删除指定键。如果键不存在的话，delete会将map原封不动返回。
ghci>:typeM.deleteM.delete::(Ordk)=>k->M.Mapka->M.Mapkaghci>M.delete"foo"mfromList[]最后，还有几个常用的函数用于在maps上进行类似集合的操作。例如，我们接下来会用到的union。这个函数是“左偏”(leftbiased)的：如果两个map包含相同的键，返回map中将包含左侧map中对应的关联值。
ghci>m`M.union`M.singleton"quux"1fromList[("foo",1),("quux",1)]ghci>m`M.union`M.singleton"foo"0fromList[("foo",1)]到此我们仅仅讲到了Data.Map中百分之十的API。在第13章中我们会更加广泛深入的讲解其中的API。我们鼓励你自行浏览模块的文档，相信你会从中获得更多启发。这个模块滴水不漏的设计一定会让你印象深刻。
[Okasaki99]一书将教我们如何优雅且严密地实现纯函数式数据结构，其中包括多种平衡树。该书还中还包含了作者对于纯函数式数据结构和惰性求值的宝贵思考。
我们把Okasaki这本书列为为函数式程序员的必读书目。如果你不方便翻阅Okasaki这本书，可以去看Okasaki的博士论文，[Okasaki96]是该书的一个不很完整的精简版本，在网上可以免费获得。
我们现在又有了新的问题要解决。后十二个数字还只是一堆候选数字；此外，我们需要根据这12个数字中的前6个数字的奇偶性信息来计算第一个数字。最后，我们还需要确认求出的校验码的有效性。
这看起来很有挑战！这一大堆不确定的数据；该拿它们怎么办？采用暴力搜索是一个很合理的提议。那么，如果候选数字就是上面的ghci会话中给出的那些，我们需要测试多少种组合？
ghci>product.maplength.candidateDigits$input34012224可见暴力搜索要检查的组合太多了。我们还是先着眼于一个知道如何解决的子问题，晚些时候在考虑剩下的的。
--file:ch12/Barcode.hstypeMapa=M.MapDigit[a]在这个map中，键值是一个校验码，映射值是一个可以计算出这个校验码的序列。以它为基础，我们进一步定义两种map类型。
我们将把这两种类型的map统称为“答案map”(solutionmap)，因为它们包含了“求解”每个校验码对应的各个数字序列。
给定一个数字，我们可以按如下方法更新一个给定的答案map
这部分内容可能有点不太好消化，看一个例子应该会更明白。我们假设现在要查找数字是4，它是序列[1,3]对应的校验码，我们想要添加到map的数字是8。4+8，模10得2，那么2就是要插入到map中的键。能计算出新校验码2的序列就是[8,1,3]，这个序列就是要插入的映射值。
对候选数字序列中的每一个数字，我们都会通过当前数字和之前的map生成一个新的答案map。
--file:ch12/Barcode.hsuseDigit::ParityMap->ParityMap->ParityDigit->ParityMapuseDigitoldnewdigit=new`M.union`M.foldWithKey(updateMapdigit)M.emptyold我们再通过一个例子演示这段代码的实际功能。这次，我们用ghci交互演示。
ghci>letsinglen=M.singletonn[Evenn]::ParityMapghci>useDigit(single1)M.empty(Even1)fromList[(2,[Even1,Even1])]ghci>useDigit(single1)(single2)(Even2)fromList[(2,[Even2]),(3,[Even2,Even1])][译注：这个函数的参数中，old代表上一候选数字应用此函数时产生的map，而old代表“条形码中的上一个数字位置”通过不断折叠应用此函数所产生的map，digit表示当前考察的候选数字。这个函数的实际作用是在某个候选数字列表中遍历的过程中，当前考察的这个候选数字插入到给定map的每个映射值的最前方，并求得新的临时校验码，然后将这个临时校验码和插入后的序列作为键值对插入到map中，并与前一候选数字应用此函数的结果map做“并集”操作(M.union)，由于候选数字序列是按照匹配程度降序排列的，因此如果当前序列中的键值与前一候选数字产生的某个键值发生冲突，那么它就会被``M.Union``的“左偏”性质覆盖掉，而保留前一候选数字所产生的新序列。]
传给useDigits函数的新答案map(即参数new对应的map)最开始是空的。其值将通过在输入数字的序列上折叠useDigits函数来填充。
ghci>incorporateDigits(M.singleton0[])[Even1,Even5]fromList[(1,[Even1]),(5,[Even5])][译注：incorporate函数中，参数old代表条码中上一个位置的数字组成的可能的数字逆序序列以及他们对应的临时校验码组成的map，参数digits表示该位置上的候选数字列表。]
最终，我们必须构造完整的答案map。我们先创建一个空的map，然后在条形码的数字序列上依次折叠。我们为每个位置生成一个包含截止到该位置的猜测序列的newmap。这个map将作为下一位置上的折叠过程的oldmap出现。
finalDigits函数接受的列表有多少个元素呢？我们还不知道数字序列的第一个数字是什么，所以很明显第一位数字不能计入，并且在调用``finalDigits``时校验码还只是猜测值，我们也不该把它计入。所以这个输入列表应该有11个元素。
从finalDigits返回后，答案map必然还不完整，因为我们还没有确定首位数字是什么。
我们还没说过如何从左侧分组的奇偶编码类型中提取出首位数字。其实只要直接重用我们前面编写的代码就可以了。
--file:ch12/Barcode.hsfirstDigit::[Paritya]->DigitfirstDigit=snd.head.bestScoresparitySRL.runLengths.mapparityBit.take6whereparityBit(Even_)=ZeroparityBit(Odd_)=One现在这个不完整的答案map中的每个元素都包含一个由数字和编码奇偶性信息组成的逆序的列表。接下来的任务就是通过计算每个序列的首位数字来创建一个完整的答案map，并通过它创建最终的答案map(即键值都是正确的校验码，映射值都是完整的12位正序列表的map)。
--file:ch12/Barcode.hsaddFirstDigit::ParityMap->DigitMapaddFirstDigit=M.foldWithKeyupdateFirstM.emptyupdateFirst::Digit->[ParityDigit]->DigitMap->DigitMapupdateFirstkeyseq=insertMapkeydigit(digit:renormalizeqes)whererenormalize=mapEveryOther(`div`3).mapfromParitydigit=firstDigitqesqes=reverseseq[译注：mapKeys将第一个参数指定的函数逐一应用于map中的每个key，并用结果替换掉原key值。]
如此往复，我们最终消去了Parity类型，并撤销了之前乘以3的操作。最后一步，就是完成校验码的计算。
--file:ch12/Barcode.hssolve::[[ParityDigit]]->[[Digit]]solve[]=[]solvexs=catMaybes$map(addCheckDigitm)checkDigitswherecheckDigits=mapfromParity(lastxs)m=buildMap(initxs)addCheckDigitmk=(++[k])<$>M.lookupkm[译注：catMaybes接受一个Maybe类型元素组成的列表，返回一个只由Just构造器的参数值构成的列表(即参数列表中的Nothing值会被直接忽略)。
我们用从照片上取下来的那一行来试验，看看能否得到正确的结果。
ghci>listToMaybe.solve.candidateDigits$inputJust[9,7,8,0,1,3,2,1,1,4,6,7,7]太棒了！这正是照片中编码的数字序列。
我们反复强调“处理的是图像中的一行”。下面是“处理一行”的具体的做法
--file:ch12/Barcode.hswithRow::Int->Pixmap->(RunLengthBit->a)->awithRowngreymapf=f.runLength.elems$posterizedwhereposterized=threshold0.4.fmapluminance.rown$greymapwithRow函数接受图像中的一行，将该行转换为黑白图像，然后对游程编码后的行数据应用指定函数。该函数通过row函数来获取行数据。
row::(Ixa,Ixb)=>b->Array(a,b)c->Arrayacrowja=ixmap(l,u)projectawhereprojecti=(i,j)((l,_),(u,_))=boundsa这个函数需要稍作解释。我们知道fmap用来变换数组中的元素值，而此处的ixmap则用来变换数组中的索引值。这个强大的函数使我们可以任意地从数组取出“切片”。
ixmap的第一个参数是新数组的边界。边界可以与原数组有不同的维。比方说，我们可以从一个二维数组中取出一个一维数组表示的行。
[译注：此处所说的“有不同的维”包括维数不同、“维的类型”不同、以及两种都有的情况。]
第二个参数是一个映射函数。其参数为新数组的索引值，返回值为原数组的索引值。映射索引的值接下来会变为新数组原索引值处的值。例如，如果我们把2传给映射函数，它返回(2,2)。这表示新数组中索引值为2的元素值将取自源数组中索引值为(2,2)的元素。
candidateDigits只要不是从条形码序列的起始处调用,就会返回一个空结果。使用下面的函数，我们可以轻松的扫描一整行，并得到匹配结果。
--file:ch12/Barcode.hsfindMatch::[(Run,Bit)]->Maybe[[Digit]]findMatch=listToMaybe.filter(not.null).map(solve.candidateDigits).tails..FIXME:应该是指的candidateDigits的惰性求值
这里，我们利用了惰性求值的优点。tails前面的map函数只会在产生非空列表的时候参会真正求值。
--file:ch12/Barcode.hsfindEAN13::Pixmap->Maybe[Digit]findEAN13pixmap=withRowcenterpixmap(fmaphead.findMatch)where(_,(maxX,_))=boundspixmapcenter=(maxX+1)`div`2最后，我们做了一个简单的封装，用来打印从命令行传入的netpbm图像文件中提取的条形码。
注意到在我们本章定义的超过30个函数中，只有main是涉及IO的。
你可能发现了，本章中给出的许多函数都是些放在源码顶部的小函数。这并非偶然。正如我们早些时候提到过的，当我们开始本章的撰写时，我们并不知道要怎样构造这个解决方案。
一旦我们对这些函数的功能和行为满意了，我们就开始将它们黏合在一起，继续通过ghci观察执行的结果。这就是添加类型签名的好处——如果某些函数没法组合到一起，我们可以通过类型签名尽早发现。
使用强静态类型的语言工作不会影响增量的流式的问题解决模式。我们发现这种“先编写函数”，再“用**ghci**测试，获取有用信息”的模式非常快速；这为我们快速编写优质代码提供了巨大帮助。