Changes between Version 31 and Version 32 of PatternFamilies


Ignore:
Timestamp:
Mar 21, 2017 10:03:50 AM (3 years ago)
Author:
Iceland_jack
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • PatternFamilies

    v31 v32  
    55The simplest use case is checking whether a set contains a value:
    66
    7 {{{
    8     -- Normal Haskell
    9     answer :: Set Int -> String
    10     answer set = case member 42 set of
    11       True  -> "We know the answer"
    12       False -> "Never mind."
    13 
    14     -- Using view patterns
    15     answer :: Set Int -> String
    16     answer (member 42 -> True)  = "We know the answer"
    17     answer (member 42 -> False) = "Never mind."
     7{{{#!hs
     8-- Normal Haskell
     9answer :: Set Int -> String
     10answer set = case member 42 set of
     11  True  -> "We know the answer"
     12  False -> "Never mind."
     13
     14-- Using view patterns
     15answer :: Set Int -> String
     16answer (member 42 -> True)  = "We know the answer"
     17answer (member 42 -> False) = "Never mind."
    1818}}}
    1919
    2020With this extension we could define patterns that check for containment:
    2121
    22 {{{
    23     pattern IsMember  val <- (member val -> True)
    24     pattern NotMember val <- (member val -> False)
    25 
    26     -- With extension
    27     answer :: Set Int -> String
    28     answer (IsMember  42) = "We know the answer"
    29     answer (NotMember 42) = "Never mind."
     22{{{#!hs
     23pattern IsMember  val <- (member val -> True)
     24pattern NotMember val <- (member val -> False)
     25
     26-- With extension
     27answer :: Set Int -> String
     28answer (IsMember  42) = "We know the answer"
     29answer (NotMember 42) = "Never mind."
    3030}}}
    3131
     
    3636Let's consider a similar example with a `Map` where we want to look up a value based on some key:
    3737
    38 {{{
    39     -- Normal Haskell
    40     addressAlice :: Map Name Address -> Either String Address
    41     addressAlice people = case lookup "Alice" people of
    42       Just address -> Right address
    43       Nothing      -> Left "Alice's address not found."
     38{{{#!hs
     39-- Normal Haskell
     40addressAlice :: Map Name Address -> Either String Address
     41addressAlice people = case lookup "Alice" people of
     42  Just address -> Right address
     43  Nothing      -> Left "Alice's address not found."
    4444}}}
    4545
    4646With the extension we define a pattern that only succeeds if `lookup` returns a value wrapped in `Just` which feeds that value back into the pattern:
    4747
    48 {{{
    49     pattern Lookup     key val <- (lookup key -> Just val)
    50     pattern LookupFail key     <- (lookup key -> Nothing)
    51 
    52     -- With extension
    53     addressAlice :: Map Name Address -> Either String Address
    54     addressAlice (Lookup "Alice" address) = Right address
    55     addressAlice _                        = Left "Alice's address not found."
     48{{{#!hs
     49pattern Lookup     key val <- (lookup key -> Just val)
     50pattern LookupFail key     <- (lookup key -> Nothing)
     51
     52-- With extension
     53addressAlice :: Map Name Address -> Either String Address
     54addressAlice (Lookup "Alice" address) = Right address
     55addressAlice _                        = Left "Alice's address not found."
    5656}}}
    5757
     
    6262Now we don't have to unnecessarily give a name to an argument (like `people`) like with view patterns but unlike view patterns we don't need to mention to `Bool` and `Maybe` success result values of member and lookup. These kinds of patterns also nest arbitrarily without too much noise:
    6363
    64 {{{
    65     foo :: Map Person (Map Receptacle (Set Items)) -> Status
    66     foo = \case
    67       Lookup "Bob" (Lookup Pocket (IsMember  Keys)) -> HasKeys
    68       Lookup "Bob" (Lookup Pocket (NotMember Keys)) -> NoKeys
    69       Lookup "Bob" (LookupFail Pocket)              -> NoPocket
    70       LookupFail "Bob"                              -> Failure "No Bob"
     64{{{#!hs
     65foo :: Map Person (Map Receptacle (Set Items)) -> Status
     66foo = \case
     67  Lookup "Bob" (Lookup Pocket (IsMember  Keys)) -> HasKeys
     68  Lookup "Bob" (Lookup Pocket (NotMember Keys)) -> NoKeys
     69  Lookup "Bob" (LookupFail Pocket)              -> NoPocket
     70  LookupFail "Bob"                              -> Failure "No Bob"
    7171}}}
    7272
    7373Another simple example is the `Between` pattern that matches a particular range (a feature built into [http://doc.rust-lang.org/master/tutorial.html#pattern-matching Rust]):
    7474
    75 {{{
    76     import Data.Ix
    77 
    78     pattern Between from to <- (inRange (from, to) -> True)
    79 
    80     -- A teenager is between thirteen and nineteen.
    81     -- `Between 13 19` would be `13..19` in Rust.
    82     isTeen :: Age -> Bool
    83     isTeen (Between 13 19) = True
    84     isTeen _               = False
     75{{{#!hs
     76import Data.Ix
     77
     78pattern Between from to <- (inRange (from, to) -> True)
     79
     80-- A teenager is between thirteen and nineteen.
     81-- `Between 13 19` would be `13..19` in Rust.
     82isTeen :: Age -> Bool
     83isTeen (Between 13 19) = True
     84isTeen _               = False
    8585}}}
    8686
    8787that gets transformed into:
    8888
    89 {{{
    90     isTeen :: Age -> Bool
    91     isTeen (inRange (13, 19) -> True) = True
    92     isTeen _                          = False
     89{{{#!hs
     90isTeen :: Age -> Bool
     91isTeen (inRange (13, 19) -> True) = True
     92isTeen _                          = False
    9393}}}
    9494
    9595`Between` will work on any indexable type (`Ix a => a`):
    9696
    97 {{{
    98     generalCategory' :: Char -> GeneralCategory
    99     generalCategory' = \case
    100       Between '\x00' '\x16' -> Control
    101       Between 'a'    'z'    -> LowercaseLetter
    102       Between 'A'    'Z'    -> UppercaseLetter
    103       Between '0'    '9'    -> DecimalNumber
     97{{{#!hs
     98generalCategory' :: Char -> GeneralCategory
     99generalCategory' = \case
     100  Between '\x00' '\x16' -> Control
     101  Between 'a'    'z'    -> LowercaseLetter
     102  Between 'A'    'Z'    -> UppercaseLetter
     103  Between '0'    '9'    -> DecimalNumber
    104104}}}
    105105
     
    107107The syntax from PatternSynonyms can be reused for simplicity:
    108108
     109{{{#!hs
     110pattern Lookup key value <- (lookup key -> Just value)
     111}}}
     112
     113here `value` is a normal variable as in PatternSynonyms but `key` is some term the view pattern is indexed by: this can be inferred from it appearing in the ViewPatterns expression (`lookup key`) rather than in the pattern (`Just value`).
     114
     115The function `fn`:
     116
     117{{{#!hs
     118fn :: Map String Int -> Int
     119fn (Lookup "five" n) = n
     120}}}
    109121{{{
    110     pattern Lookup key value <- (lookup key -> Just value)
    111 }}}
    112 
    113 here `value` is a normal variable as in PatternSynonyms but `key` is some term the view pattern is indexed by: this can be inferred from it appearing in the ViewPatterns expression (`lookup key`) rather than in the pattern (`Just value`).
    114 
    115 The function `fn`:
    116 
    117 {{{
    118     fn :: Map String Int -> Int
    119     fn (Lookup "five" n) = n
    120 
    121     ghci> fn (Map.fromList [("four", 4), ("five", 5)]
    122     5
     122ghci> fn (Map.fromList [("four", 4), ("five", 5)]
     1235
    123124}}}
    124125
     
    147148For the simple example of the pattern family `Take` this (where 3 is ''expr,,1,,'' and `xs` is ''pval,,1,,''):
    148149
    149 {{{
    150     foo (Lookup "five" n) = n + n
     150{{{#!hs
     151foo (Lookup "five" n) = n + n
    151152}}}
    152153
    153154would get translated to:
    154155
    155 {{{
    156 .    foo (lookup "five" -> Just n) = n + n
     156{{{#!hs
     157foo (lookup "five" -> Just n) = n + n
    157158}}}
    158159
    159160which is the same as:
    160161
    161 {{{
    162     foo ys = case lookup "five" n of
    163       Just n -> n + n
     162{{{#!hs
     163foo ys = case lookup "five" n of
     164  Just n -> n + n
    164165}}}
    165166
     
    172173Example from ViewPatternsAlternative:
    173174
    174 {{{
     175{{{#!hs
    175176module Set(Set, empty, insert, delete, has) where
    176177
    177     newtype Set a = S [a]
     178newtype Set a = S [a]
    178179 
    179     has :: Eq a => a -> Set a -> Maybe (Set a)
    180     has x (S xs) | x `elem` xs = Just (S (xs \\ [x]))
    181                  | otherwise   = Nothing
     180has :: Eq a => a -> Set a -> Maybe (Set a)
     181has x (S xs) | x `elem` xs = Just (S (xs \\ [x]))
     182             | otherwise   = Nothing
    182183}}}
    183184
    184185Using patterns indexed by an element of `Set a`:
    185186
    186 {{{
    187     pattern Has    x set <- (has x        -> Just set)
    188     pattern HasNot x set <- (has x &&& id -> (Nothing, set))
     187{{{#!hs
     188pattern Has    x set <- (has x        -> Just set)
     189pattern HasNot x set <- (has x &&& id -> (Nothing, set))
    189190}}}
    190191
    191192One can write:
    192193
    193 {{{
    194     delete :: Eq a => a -> Set a -> Set a
    195     delete x (Has x set) = set
    196     delete x set         = set
    197 
    198     insert :: Eq a => a -> Set a -> Set a
    199     insert x (HasNot x (S xs)) = S (x:xs)
    200     insert x set               = set
     194{{{#!hs
     195delete :: Eq a => a -> Set a -> Set a
     196delete x (Has x set) = set
     197delete x set         = set
     198
     199insert :: Eq a => a -> Set a -> Set a
     200insert x (HasNot x (S xs)) = S (x:xs)
     201insert x set               = set
    201202}}}
    202203
    203204Compare that to the the ViewPatternsAlternative proposal:
    204 {{{
    205     delete :: Eq a => a -> Set a -> Set a
    206     delete x (r | Just s <- has r) = set
    207     delete x set                   = set
     205{{{#!hs
     206delete :: Eq a => a -> Set a -> Set a
     207delete x (r | Just s <- has r) = set
     208delete x set                   = set
    208209 
    209     insert :: Eq a => a -> Set a -> Set a
    210     insert x (s | Just _ <- has x s) = set
    211     insert x (S xs)                  = S (x:xs)
     210insert :: Eq a => a -> Set a -> Set a
     211insert x (s | Just _ <- has x s) = set
     212insert x (S xs)                  = S (x:xs)
    212213}}}
    213214
     
    217218Another example stolen from ViewPatternsAlternative where the benefits are more apparent. Given a parsing function:
    218219
    219 {{{
    220     bits :: Int -> ByteString -> Maybe (Word, ByteString)
    221     -- (bits n bs) parses n bits from the front of bs, returning
    222     -- the n-bit Word, and the remainder of bs
     220{{{#!hs
     221-- (bits n bs) parses n bits from the front of bs, returning
     222-- the n-bit Word, and the remainder of bs
     223
     224bits :: Int -> ByteString -> Maybe (Word, ByteString)
    223225}}}
    224226
    225227and using the following pattern family:
    226228
    227 {{{
    228     pattern Bits n val bs <- (bits n -> Just (val, bs))
     229{{{#!hs
     230pattern Bits n val bs <- (bits n -> Just (val, bs))
    229231}}}
    230232
    231233one can write a pattern like this:
    232234
    233 {{{
    234     parsePacket :: ByteString -> _
    235     parsePacket (Bits 3 n (Bits n val bs)) = _
     235{{{#!hs
     236parsePacket :: ByteString -> _
     237parsePacket (Bits 3 n (Bits n val bs)) = _
    236238}}}
    237239
    238240Where we can nest pattern families, more examples of nesting follow in the more advanced examples below. Compare that to the more verbose ViewPatternsAlternative version:
    239241
    240 {{{
    241     parsePacket :: ByteString -> _
    242     parsePacket (p1 |  Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = _
     242{{{#!hs
     243parsePacket :: ByteString -> _
     244parsePacket (p1 |  Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = _
    243245}}}
    244246
     
    246248Another one from ViewPatternsAlternative using the following view and pattern family:
    247249
    248 {{{
    249     np :: Num a => a -> a -> Maybe a
    250     np k n | k <= n    = Just (n-k)
    251            | otherwise = Nothing
    252 
    253     pattern NP k n <- (np k -> Just n)
     250{{{#!hs
     251np :: Num a => a -> a -> Maybe a
     252np k n | k <= n    = Just (n-k)
     253       | otherwise = Nothing
     254
     255pattern NP k n <- (np k -> Just n)
    254256}}}
    255257
    256258Used as follows:
    257259
    258 {{{
    259     fib :: Num a -> a -> a
    260     fib 0        = 1
    261     fib 1        = 1
    262     fib (NP 2 n) = fib (n + 1) + fib n
     260{{{#!hs
     261fib :: Num a -> a -> a
     262fib 0        = 1
     263fib 1        = 1
     264fib (NP 2 n) = fib (n + 1) + fib n
    263265}}}
    264266
    265267Compare ViewPatternsAlternative version:
    266268
    267 {{{
    268     fib :: Num a -> a -> a
    269     fib 0 = 1
    270     fib 1 = 1
    271     fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n
     269{{{#!hs
     270fib :: Num a -> a -> a
     271fib 0 = 1
     272fib 1 = 1
     273fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n
    272274}}}
    273275
     
    275277From [http://itu.dk/people/drc/tutorials/bidirectional.pdf Bidirectional Typing Rules: A Tutorial]:
    276278
    277 {{{
    278     inferType ctx (If t1 t2 t3) = case (inferType ctx t1, inferType ctx t2, inferType ctx t3) of
    279       (Just BoolT, Just ty2, Just ty3) ->
    280         if ty2 = ty3
    281         then Just ty2
    282         else Nothing
    283       _ -> Nothing
     279{{{#!hs
     280inferType ctx (If t1 t2 t3) = case (inferType ctx t1, inferType ctx t2, inferType ctx t3) of
     281  (Just BoolT, Just ty2, Just ty3) ->
     282    if ty2 = ty3
     283    then Just ty2
     284    else Nothing
     285  _ -> Nothing
    284286}}}
    285287
    286288could be rewritten using pattern families as:
    287289
    288 {{{
    289     -- Here ‘Inf’ is a family indexed by ‘ctx’
    290     pattern Inf ctx ty <- (inferType ctx -> Just ty)
    291 
    292     inferType ctx (If (Inf ctx BoolT) (Inf ctx ty1) (Inf ctx ty2))
    293        | ty1 == ty2 = Just ty1
    294     inferType ctx If{} = Nothing
     290{{{#!hs
     291-- Here ‘Inf’ is a family indexed by ‘ctx’
     292pattern Inf ctx ty <- (inferType ctx -> Just ty)
     293
     294inferType ctx (If (Inf ctx BoolT) (Inf ctx ty1) (Inf ctx ty2))
     295   | ty1 == ty2 = Just ty1
     296inferType ctx If{} = Nothing
    295297}}}
    296298
    297299allowing the user to pattern match ''directly'' on the inferable types without manually checking for `Just`s — note the use of the previous argument `ctx` to index later. This could currently be written somewhat awkwardly using view patterns:
    298300
    299 {{{
    300     inferType ctx (If (inferType ctx -> Just BoolT) (inferType ctx -> Just ty1) (inferType ctx -> Just ty2))
    301        | ty1 == ty2 = Just ty1
    302     inferType ctx If{} = Nothing
     301{{{#!hs
     302inferType ctx (If (inferType ctx -> Just BoolT) (inferType ctx -> Just ty1) (inferType ctx -> Just ty2))
     303  | ty1 == ty2 = Just ty1
     304inferType ctx If{} = Nothing
    303305}}}
    304306
     
    307309Again one could use operators (`:⇒ = Inf`) in which case it the examples follow notation in type theory more closely:
    308310
    309 {{{
    310     inferType γ (If (γ :⇒ BoolT) (γ :⇒ τ₁) (γ :⇒ τ₂)) = ...
     311{{{#!hs
     312inferType γ (If (γ :⇒ BoolT) (γ :⇒ τ₁) (γ :⇒ τ₂)) = ...
    311313}}}
    312314
     
    314316Given a regular expression operator `(~=) :: String -> String -> Maybe [String]` we can define a pattern:
    315317
    316 {{{
    317     pattern Match x regexp <- ((~= regexp) -> Just x)
     318{{{#!hs
     319pattern Match x regexp <- ((~= regexp) -> Just x)
    318320}}}
    319321
    320322where `regexp` is indexes the `Match` pattern family:
    321323
    322 {{{
    323     firstWord (Match words "[a-zA-Z]+") = words
    324     firstWord _                         = error "No words found"
     324{{{#!hs
     325firstWord (Match words "[a-zA-Z]+") = words
     326firstWord _                         = error "No words found"
    325327}}}
    326328
    327329or
    328330
    329 {{{
    330     vowels (Match vwls "[aeiou]") = length vwls
     331{{{#!hs
     332vowels (Match vwls "[aeiou]") = length vwls
    331333}}}
    332334
    333335As an operator:
    334336
    335 {{{
    336     pattern x :~= regexp <- ((~= regexp) -> Just x)
     337{{{#!hs
     338pattern x :~= regexp <- ((~= regexp) -> Just x)
    337339}}}
    338340
     
    342344Indexing patterns with prisms from [http://hackage.haskell.org/package/lens-4.2/docs/Control-Lens-Prism.html Control.Lens.Prism]:
    343345
    344 {{{
    345     import Control.Lens.Prism
    346 
    347     pattern Match prism a <- (preview prism -> Just a)
     346{{{#!hs
     347import Control.Lens.Prism
     348
     349pattern Match prism a <- (preview prism -> Just a)
    348350}}}
    349351
    350352one can write
    351353
    352 {{{
    353     bar :: Either c (Either a b) -> a
    354     bar (Match (_Right._Left) a) = a
    355     bar _                        = error "..."
     354{{{#!hs
     355bar :: Either c (Either a b) -> a
     356bar (Match (_Right._Left) a) = a
     357bar _                        = error "..."
    356358}}}
    357359
     
    359361Pattern families can be used to match nested data like JSON, ASTs or XML, here is an example of using it to match on [http://hackage.haskell.org/package/lens-4.2/docs/Data-Aeson-Lens.html Data.Aeson.Lens]:
    360362
    361 {{{
    362     jsonBlob = "[{\"someObject\": {\"version\": [1,0,3]}}]"
     363{{{#!hs
     364jsonBlob = "[{\"someObject\": {\"version\": [1,0,3]}}]"
    363365   
    364     -- val = Number 0.0
    365     val = jsonBlob ^?! nth 0 . key "someObject" . key "version" . nth 1
     366-- val = Number 0.0
     367val = jsonBlob ^?! nth 0 . key "someObject" . key "version" . nth 1
    366368}}}
    367369
    368370Pattern families allow us to say we want to fetch the same value as `val` using patterns:
    369371
    370 {{{
    371     foo (Match (nth 0) (Match (key "someObject") (Match (key "version") (Match (nth 1) a)))) = a
     372{{{#!hs
     373foo (Match (nth 0) (Match (key "someObject") (Match (key "version") (Match (nth 1) a)))) = a
    372374}}}
    373375
    374376Which is terribly verbose, but can be improved by introducing:
    375377
    376 {{{
    377     pattern Get i   a <- (preview (nth i)   -> Just a)
    378     pattern Key str a <- (preview (key str) -> Just a)
    379 
    380     baz (Get 0 (Key "someObject" (Key "version" (Get 1 a)))) = a
     378{{{#!hs
     379pattern Get i   a <- (preview (nth i)   -> Just a)
     380pattern Key str a <- (preview (key str) -> Just a)
     381
     382baz (Get 0 (Key "someObject" (Key "version" (Get 1 a)))) = a
    381383}}}
    382384
    383385or  by writing it infix:
    384386
    385 {{{
    386     baz (0 `Get` "someObject" `Key` "version" `Key` 1 `Get` a) = a
     387{{{#!hs
     388baz (0 `Get` "someObject" `Key` "version" `Key` 1 `Get` a) = a
    387389}}}
    388390
    389391or by defining operators `:→ = Get i a` and `:⇒ = Key`:
    390392
    391 {{{
    392     baz (a :→ "someObject" :⇒ "version" :⇒ 1 :→ a) = a
    393 }}}
     393{{{#!hs
     394baz (a :→ "someObject" :⇒ "version" :⇒ 1 :→ a) = a
     395}}}