7

我正在通过Learn You A Haskell来学习 Haskell的基础知识。我对函数式编程和模式匹配都非常满意，但后者更喜欢Mathematica是如何做到的。

head本着与第 4.1 章中的幼稚实现相同的精神，我继续进行last如下的幼稚实现：

last1 :: [a] -> a
last1 (_:x:[]) = x

但是，调用last1 [1,2,3,4]给出了错误Exception: ... Non-exhaustive patterns in function last1。我知道这个错误意味着指定的模式不涵盖所有可能的输入，通常需要一个包罗万象的模式（我没有提供）。但是，我不确定为什么我的输入会出现此错误。

问题 1：我的理解（我的错误方法）是第一个元素被捕获，_其余的被分配给x，这不是我想要的。但是，这不应该给出类型错误吗，因为我指定了[a] -> a, but xnow is a list？

请注意，这不是关于如何编写一个工作last函数——我知道我可以把它写成（以及其他可能性）

last2 :: [a] -> a
last2 [x] = x
last2 (_:x) = last2 x

问题 2：在更好地理解 Haskell 中的模式匹配的同一主题下，我如何使用模式匹配来挑选最后一个元素或更一般地，n从给定列表中挑选出第 th 个元素，比如说，[1..10]？

这个答案表明您可以使用与ViewPatterns扩展名匹配的模式来绑定最后一个元素，但似乎很奇怪没有类似的“简单”模式head

在Mathematica中，我可能会将其写为：

Range[10] /. {Repeated[_, {5}], x_, ___} :> x
(* 6 *)

挑选出第 6 个元素和

Range[10] /. {___, x_} :> x
(* 10 *)

挑选出非空列表的最后一个元素。

如果本文稍后会涉及到这一点，我深表歉意，但我试图将遇到的每个主题和概念与我知道的其他语言的处理方式联系起来，以便我能够理解差异和相似之处。

4

4 回答 4

8

要理解第一次尝试的结果，您需要查看列表数据是如何定义的。列表有一种特殊的语法，但你可以这样写。

data List a = (:) a (List a)
            | []

因此，您的列表 [1 .. 10] 实际上的结构为

(1 : (2 : (3 : (4 : []))))

此外，由于 (:) 运算符的正确关联性，您的 last1 模式实际上看起来像

last1 :: [a] -> a
last1 (_:(x:[])) = x

这就是为什么 'x' 与列表中的元素具有相同类型的原因；它是 (:) 构造函数的第一个参数。

模式匹配允许您解构列表等数据结构，但您需要知道它们必须这样做的“形状”。这就是为什么您不能直接指定将提取列表的最后一个元素的模式，因为列表可以有无限多的长度。这就是为什么工作解决方案（last2）使用递归来解决问题的原因。您知道长度为 one 的列表具有什么模式以及在哪里可以找到最终元素；对于其他所有内容，您可以丢弃第一个元素并提取结果更短列表的最后一个元素。

如果你愿意，你可以添加更多的模式，但它不会被证明是有帮助的。你可以把它写成

last2 :: [a] -> a
last2 (x:[])     = x
last2 (_:x:[])   = x
last2 (_:_:x:[]) = x
        ...
last2 (x:xs) = last2 xs

但是如果没有无限多的情况，您永远无法完成所有长度的输入列表的功能。当您考虑到列表实际上可以无限长的事实时，它就更加可疑了。你会用什么模式来匹配它？

于 2012-09-28T23:08:26.157 回答
2

如果不使用视图模式，就无法让模式匹配获得“最后一个”元素。那是因为不使用递归（至少隐式地）就无法获取列表的最后一个元素，而且，没有可确定的方法来获取最后一个元素。

你的代码

last1 (_:x:[]) = x

应该像这样解析

last1 (_:(x:[])) = x

可以脱糖成

last1 a = case a of
               (_:b) -> case b of
                             (x:c) -> case c of
                                           [] -> x

完成本练习后，我们将看到您的代码做了什么：您编写了一个匹配列表的模式，如果列表的最外层构造函数是 cons 单元格且下一个构造函数是 cons 且第三个构造函数是 nil。

所以在这种情况下

last1 [1,2,3,4]

我们有

last1 [1,2,3,4] 
= last1 (1:(2:(3:(4:[]))))
= case (1:(2:(3:(4:[])))) of
       (_:b) -> case b of
                     (x:c) -> case c of
                                   [] -> x
= case (2:(3:(4:[]))) of
       (x:c) -> case c of
                     [] -> x
= let x = 2 in case (3:(4:[])) of
                    [] -> x
= pattern match failure
于 2012-09-28T23:06:19.257 回答
2

你的例子

last1 (_:x:[]) = x

只匹配包含两个元素的列表，即表单的列表a:b:[]。_匹配没有绑定的链表头，x匹配后面的元素，空链表匹配自身。

当模式匹配列表时，只有最右边的项目代表一个列表 - 匹配列表的尾部。

您可以使用以下函数从列表中获取第 n 个元素：

getNth :: [a] -> Int -> a
getNth [] _ = error "Out of range"
getNth (h:t) 0 = h
getNth (h:t) n = getNth t (n-1)

这个内置使用!!运算符，例如[1..10] !! 5

于 2012-09-28T23:07:15.240 回答
2

您确实可以使用ViewPatterns在列表末尾进行模式匹配，所以让我们这样做：

{-# LANGUAGE ViewPatterns #-}

并在我们进行模式匹配之前通过反转列表来重新定义您的last1and 。last2这使它成为O(n)，但这对于列表是不可避免的。

last1 (reverse -> (x:_)) = x

语法

mainFunction (viewFunction -> pattern) = resultExpression

是语法糖

mainFunction x = case viewFunction x of pattern -> resultExpression

所以你可以看到它实际上只是反转列表然后模式匹配它，但感觉更好。 viewFunction就是你喜欢的任何功能。（扩展的目的之一是允许人们干净、轻松地使用访问器函数进行模式匹配，这样他们在定义函数时就不必使用其数据类型的底层结构。）

如果last1列表为空，则会出现错误，就像原始列表一样last。

*Main> last []
*** Exception: Prelude.last: empty list
*Main> last1 []
*** Exception: Patterns.so.lhs:7:6-33: Non-exhaustive patterns in function last1

好吧，好吧，不完全是，但我们可以通过添加来改变它

last1 _ = error "last1: empty list"

这给了你

*Main> last1 []
*** Exception: last1: empty list

我们当然可以使用相同的技巧last2：

last2 (reverse -> (_:x:_)) = x
last2 _ = error "last2: list must have at least two elements"

但是定义会更好

maybeLast2 (reverse -> (_:x:_)) = Just x
maybeLast2 _ = Nothing

您可以使用例如以下方式进行last4：

last4 (reverse -> (_:_:_:x:_)) = x

你可以看到，使用reverse视图模式，我们改变了(_:_:_:x:_)from (ignore1st,ignore2nd,ignore3rd,get4th,ignoreTheRestOfTheList)to 的语义(ignoreLast,ignore2ndLast,ignore3rdLast,get4thLast,ignoreTheRestOfTheList)。

您注意到在 Mathematica 中，下划线的数量用于表示被忽略的元素数量。在 Haskell 中，我们只使用 one _，但它可以用于任何被忽略的值，并且在存在非对称列表构造函数的情况下:，语义取决于你在哪一边，所以在 中a:b，a必须表示一个元素，而b必须是一个列表（这本身可能是c:d因为:它是正确的关联 -a:b:c意味着 a:(b:c)）。这就是为什么任何列表模式中的最后一个下划线都会重新表示ignoreTheRestOfTheList，并且在存在reverse视图函数的情况下，这意味着忽略列表的前面元素。

隐藏在 Mathematica 中的递归/回溯在这里通过 viewFunction reverse（它是一个递归函数）是明确的。

于 2012-09-29T02:18:26.880 回答