列表最后一个元素的模式匹配



我们使用(x:xs)对第一个元素进行模式匹配,如本例所示:

head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"  
                      (x:_) -> x  

有没有办法在最后一个元素上进行模式匹配?

否,因为没有要匹配的 [a] -> a -> [a] 类型的构造函数。

可以使用 []: 进行模式匹配,因为根据定义,它们是列表值的构建基块。 []是创建空列表的方法。 :是从元素和另一个列表构建新列表的方法。像append这样的函数本身不会创建新列表;它们返回:和/或[]创建的列表。


例外情况是,如果您碰巧提前知道列表的长度,在这种情况下,您可以通过显式匹配所有元素来匹配最后一个元素。

lastOfFour :: [a] -> a
lastOfFour (_:_:_:x:[]) = x
lastOfFour (_:_:_:_:_) = error "Too many elements"
lastOfFour _ = error "Too few elements"

如果可以匹配至少 4 个元素,并且剩余列表为空,则会触发第一条错误消息;第二条错误消息由与前两个元素之一不匹配的任何列表触发。

要获取列表的最后一个元素,您需要遍历整个列表。
如果你需要在最后一个元素上进行匹配,你可能需要一个类似列表的数据结构,使这种匹配高效且易于使用,比如 Sequence(其中两端都是 O(1((:

{-# LANGUAGE OverloadedLists #-}
import Data.Sequence
last' :: Seq a -> a
last' Empty = error "Empty sequence"
last' (_:|>a) = a
test = last' [1..5]

在 GHC 中,如果您确实愿意,可以为此定义一个模式同义词。 当然,它仍然是 O(n(。

{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
unsnoc :: [a] -> Maybe ([a], a)
unsnoc [] = Nothing
unsnoc xs = Just (init xs, last xs)
{-# COMPLETE [], (:>) #-}
infixl 5 :>
pattern (:>) :: [a] -> a -> [a]
pattern xs :> x <- (unsnoc -> Just (xs, x))
  where xs :> x = xs ++ [x]
-- example:
last' :: [a] -> a
last' [] = error "last': empty list"
last' (_ :> x) = x

(unsnoc也在Data.List.Extra

如果您使用的是 GHC 6.10 或更高版本,请使用视图模式。

视图模式

允许调用模式内部的视图函数,并且 与结果匹配:

size (view -> Unit) = 1
size (view -> Arrow t1 t2) = size t1 + size t2

也就是说,我们添加了一种新的模式形式,书面

expression -> pattern

这意味着"将表达式应用于我们试图匹配的任何内容 反对,然后将该应用程序的结果与 模式。表达式可以是函数的任何 Haskell 表达式 类型和视图模式可用于当前模式所在的任何位置 使用。

head'定义为

{-# LANGUAGE ViewPatterns #-}
head' :: [a] -> a
head' (last -> l) = l

它按您的预期工作。

λ> head' [3,5,7]
7
λ> head' []
*** Exception: Prelude.last: empty list

你不能直接匹配最后一个元素,因为模式匹配只根据类型的具体构造函数解构事物,并且列表只有两个构造函数:[](:)

但是,您可以反转列表,然后在反转列表的头部匹配:

last' xs = case reverse xs of
  [] -> error "last' []"
  x : _ -> x

使用ViewPatterns,您可以直接在模式中进行反转:

{-# LANGUAGE ViewPatterns #-}
last' (reverse -> xs) = case xs of
  [] -> error "last' []"
  x : _ -> x

或者使用PatternGuards您可以在守卫中进行反转:

{-# LANGUAGE PatternGuards #-}
last' xs
  | x : _ <- reverse xs = x
  | otherwise = error "last' []"

最后,使用PatternSynonyms你可以用一个名字打包它:

{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}
pattern Reversed xs x <- (reverse -> x : xs)
  -- This part is optional, but allows writing:
  --
  --   Reversed [3, 2, 1] 0
  --
  -- As a synonym for:
  --
  --   [0, 1, 2, 3]
  --
  where Reversed xs x = x : reverse xs
last' (Reversed _ x) = x
last' _ = error "last' []"

所有这些解决方案在列表的长度上都是O(n((线性(,这是不可避免的。因此,最好使遍历尽可能明确,而不是隐藏线性成本并无意中遍历列表比预期更多,或者使用具有最后一个元素的 O(1((常量(索引的不同数据结构,例如SeqVector

正如Chepner指出的那样,没有内置的方法可以做到这一点,但是编写自己的方法也不难:

foo :: [Maybe a] -> a
foo [] = error "empty list"
foo xs =
  case last xs
    (Just a) -> a
    Nothing -> error "last element is a Nothing!"

另一种方法是reverse列表,然后在第一个元素上进行模式匹配!

相关内容

  • 没有找到相关文章

最新更新