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.

Distressed

Answer 1

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

Tiphane

Answer 2

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

Cerebroside

Excellent, I had no idea this made it into 7.10. Why is the GHC ticket still open for it though? – Shelah

@AndrásKovács: erhmm... I've left it open because the matcher vs builder type context issues in that ticket haven't been completely addressed yet. – Cerebroside

Note, per the wiki, that "[t]he exhaustiveness checker currently chokes on pattern synonyms." We can reassure the compiler that our patterns are exhaustive using the COMPLETE pragma. See also this answer. – Spacetime