模式匹配 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

ViewPatterns 可能是去这里的方法。您的代码不起作用，因为您需要先在 Seq 上调用 viewl 或 viewr 才能获得 ViewL 或 ViewR 类型的内容。 ViewPatterns 可以很好地处理：

{-# LANGUAGE ViewPatterns #-}

foo (S.viewl -> S.EmptyL)    = ... -- empty on left
foo (S.viewl -> (x S.:< xs)) = ... -- not empty on left

相当于：

foo seq = case S.viewl seq of
    S.EmptyL    -> ...
    (x S.:< xs) -> ...

Answer 2

从 GHC 7.8 开始，您可以使用 pattern synonyms together with 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、(:<)和(:>)就可以像"constructors"那样使用了嗯：

{-# 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.|>)

模式匹配 Data.Sequence 喜欢列表

Pattern matching Data.Sequence like lists

haskell

abstract-data-type

pattern-matching

pattern-synonyms