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

Answer 2

ViewPatterns is probably the way to go here. Your code doesn't work because you need to call viewl or viewr on your Seq first to get something of type ViewL or ViewR. ViewPatterns can handle that pretty nicely:

{-# LANGUAGE ViewPatterns #-}

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

Which is equivalent to something like:

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