Mẫu khớp với Data.Sequence như danh sách

Question

Tôi đang sử dụng Data.Sequence để thay thế danh sách cho hiệu suất tốt hơn. Với danh sách, chúng tôi có thể làm như sau

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

Làm cách nào để hoàn thành điều này với Data.Sequence. Tôi đã thử những điều sau đây:

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

Tôi nghĩ rằng giải pháp liên quan đến việc sử dụng S.viewl và S.viewr, nhưng dường như không thể tìm ra cách.

Answer 1

ViewPatterns có lẽ là cách để đến đây. Mã của bạn không hoạt động vì bạn cần gọi số viewl hoặc viewr trên số Seq đầu tiên của bạn để nhận một số loại ViewL hoặc ViewR. ViewPatterns có thể xử lý mà khá độc đáo:

{-# LANGUAGE ViewPatterns #-} 

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

Đó là tương đương với một cái gì đó như:

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

Answer 2

Tính đến GHC 7.8, bạn có thể sử dụng pattern synonyms cùng với view patterns cho mục đích này:

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

Kể từ GHC 7.10, bạn cũng có thể biến nó thành một từ đồng nghĩa mẫu hai chiều, sao cho Empty, (:<) và (:>) có thể được sử dụng như "nhà xây dựng" cũng như:

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