Соответствие шаблону 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 это, вероятно, способ пойти сюда. Ваш код не работает, потому что вам нужно позвонить viewl или же viewr на ваше Seq сначала получить что-то типа 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, вы можете использовать синонимы шаблонов вместе с шаблонами представления для этой цели:

{-# 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, (:<) а также (:>) также могут быть использованы в качестве "конструкторов":

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