haskell - 模式匹配 Data.Sequence 类似列表

Question

我正在使用 Data.Sequence 而是列出以获得更好的性能。使用列表，我们可以执行以下操作

foo :: [Int] -> Int
foo [] m = m
foo (x:xs) m = ...

如何使用 Data.Sequence 来实现？ .我尝试了以下方法:

foo:: S.Seq Int -> Int
foo S.empty m = m
foo (x S.<: xs) m = ...

我认为解决方案涉及使用 S.viewl和 S.viewr ，但似乎无法弄清楚如何。

Answer 1

从 GHC 7.8 开始，您可以使用 pattern synonyms连同 view patterns以此目的:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}

import qualified Data.Sequence as Seq

pattern Empty   <- (Seq.viewl -> Seq.EmptyL)
pattern x :< xs <- (Seq.viewl -> x Seq.:< xs)
pattern xs :> x <- (Seq.viewr -> xs Seq.:> x)

从 GHC 7.10 开始，您还可以将其设为双向模式同义词，以便 Empty , (:<)和 (:>)也可以用作“构造函数”:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}

import qualified Data.Sequence as Seq

pattern Empty   <- (Seq.viewl -> Seq.EmptyL)  where Empty = Seq.empty
pattern x :< xs <- (Seq.viewl -> x Seq.:< xs) where (:<)  = (Seq.<|) 
pattern xs :> x <- (Seq.viewr -> xs Seq.:> x) where (:>)  = (Seq.|>)