Pattern matching Data.Sequence like lists

Question

I am using Data.Sequence instead lists for better performance. With lists we can do the following

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

How can this be accomplished with Data.Sequence. I have tried the following:

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

I think the solution involves using S.viewl and S.viewr, but cannot seem to figure out how.

Answer 1

As of GHC 7.8, you can use pattern synonyms together with view patterns for this purpose:

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

As of GHC 7.10, you can also make it into a bidirectional pattern synonym, so that Empty, (:<) and (:>) can be used as "constructors" as well:

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