Changes between Version 31 and Version 32 of PatternFamilies
 Timestamp:
 Mar 21, 2017 10:03:50 AM (3 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

PatternFamilies
v31 v32 5 5 The simplest use case is checking whether a set contains a value: 6 6 7 {{{ 8 9 10 11 12 13 14 15 16 17 7 {{{#!hs 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." 18 18 }}} 19 19 20 20 With this extension we could define patterns that check for containment: 21 21 22 {{{ 23 24 25 26 27 28 29 22 {{{#!hs 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." 30 30 }}} 31 31 … … 36 36 Let's consider a similar example with a `Map` where we want to look up a value based on some key: 37 37 38 {{{ 39 40 41 42 43 38 {{{#!hs 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." 44 44 }}} 45 45 46 46 With 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: 47 47 48 {{{ 49 50 51 52 53 54 55 48 {{{#!hs 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." 56 56 }}} 57 57 … … 62 62 Now 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: 63 63 64 {{{ 65 66 67 68 69 70 64 {{{#!hs 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" 71 71 }}} 72 72 73 73 Another simple example is the `Between` pattern that matches a particular range (a feature built into [http://doc.rustlang.org/master/tutorial.html#patternmatching Rust]): 74 74 75 {{{ 76 77 78 79 80 81 82 83 84 75 {{{#!hs 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 85 85 }}} 86 86 87 87 that gets transformed into: 88 88 89 {{{ 90 91 92 89 {{{#!hs 90 isTeen :: Age > Bool 91 isTeen (inRange (13, 19) > True) = True 92 isTeen _ = False 93 93 }}} 94 94 95 95 `Between` will work on any indexable type (`Ix a => a`): 96 96 97 {{{ 98 99 100 101 102 103 97 {{{#!hs 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 104 104 }}} 105 105 … … 107 107 The syntax from PatternSynonyms can be reused for simplicity: 108 108 109 {{{#!hs 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 {{{#!hs 118 fn :: Map String Int > Int 119 fn (Lookup "five" n) = n 120 }}} 109 121 {{{ 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 122 ghci> fn (Map.fromList [("four", 4), ("five", 5)] 123 5 123 124 }}} 124 125 … … 147 148 For the simple example of the pattern family `Take` this (where 3 is ''expr,,1,,'' and `xs` is ''pval,,1,,''): 148 149 149 {{{ 150 150 {{{#!hs 151 foo (Lookup "five" n) = n + n 151 152 }}} 152 153 153 154 would get translated to: 154 155 155 {{{ 156 .foo (lookup "five" > Just n) = n + n156 {{{#!hs 157 foo (lookup "five" > Just n) = n + n 157 158 }}} 158 159 159 160 which is the same as: 160 161 161 {{{ 162 163 162 {{{#!hs 163 foo ys = case lookup "five" n of 164 Just n > n + n 164 165 }}} 165 166 … … 172 173 Example from ViewPatternsAlternative: 173 174 174 {{{ 175 {{{#!hs 175 176 module Set(Set, empty, insert, delete, has) where 176 177 177 178 newtype Set a = S [a] 178 179 179 180 181 180 has :: Eq a => a > Set a > Maybe (Set a) 181 has x (S xs)  x `elem` xs = Just (S (xs \\ [x])) 182  otherwise = Nothing 182 183 }}} 183 184 184 185 Using patterns indexed by an element of `Set a`: 185 186 186 {{{ 187 188 187 {{{#!hs 188 pattern Has x set < (has x > Just set) 189 pattern HasNot x set < (has x &&& id > (Nothing, set)) 189 190 }}} 190 191 191 192 One can write: 192 193 193 {{{ 194 195 196 197 198 199 200 194 {{{#!hs 195 delete :: Eq a => a > Set a > Set a 196 delete x (Has x set) = set 197 delete x set = set 198 199 insert :: Eq a => a > Set a > Set a 200 insert x (HasNot x (S xs)) = S (x:xs) 201 insert x set = set 201 202 }}} 202 203 203 204 Compare that to the the ViewPatternsAlternative proposal: 204 {{{ 205 206 207 205 {{{#!hs 206 delete :: Eq a => a > Set a > Set a 207 delete x (r  Just s < has r) = set 208 delete x set = set 208 209 209 210 211 210 insert :: Eq a => a > Set a > Set a 211 insert x (s  Just _ < has x s) = set 212 insert x (S xs) = S (x:xs) 212 213 }}} 213 214 … … 217 218 Another example stolen from ViewPatternsAlternative where the benefits are more apparent. Given a parsing function: 218 219 219 {{{ 220 bits :: Int > ByteString > Maybe (Word, ByteString) 221  (bits n bs) parses n bits from the front of bs, returning 222  the nbit Word, and the remainder of bs 220 {{{#!hs 221  (bits n bs) parses n bits from the front of bs, returning 222  the nbit Word, and the remainder of bs 223 224 bits :: Int > ByteString > Maybe (Word, ByteString) 223 225 }}} 224 226 225 227 and using the following pattern family: 226 228 227 {{{ 228 229 {{{#!hs 230 pattern Bits n val bs < (bits n > Just (val, bs)) 229 231 }}} 230 232 231 233 one can write a pattern like this: 232 234 233 {{{ 234 235 235 {{{#!hs 236 parsePacket :: ByteString > _ 237 parsePacket (Bits 3 n (Bits n val bs)) = _ 236 238 }}} 237 239 238 240 Where we can nest pattern families, more examples of nesting follow in the more advanced examples below. Compare that to the more verbose ViewPatternsAlternative version: 239 241 240 {{{ 241 242 242 {{{#!hs 243 parsePacket :: ByteString > _ 244 parsePacket (p1  Just (n, (p2  Just (val, bs) < bits n p2)) < bits 3 p1) = _ 243 245 }}} 244 246 … … 246 248 Another one from ViewPatternsAlternative using the following view and pattern family: 247 249 248 {{{ 249 250 251 252 253 250 {{{#!hs 251 np :: Num a => a > a > Maybe a 252 np k n  k <= n = Just (nk) 253  otherwise = Nothing 254 255 pattern NP k n < (np k > Just n) 254 256 }}} 255 257 256 258 Used as follows: 257 259 258 {{{ 259 260 261 262 260 {{{#!hs 261 fib :: Num a > a > a 262 fib 0 = 1 263 fib 1 = 1 264 fib (NP 2 n) = fib (n + 1) + fib n 263 265 }}} 264 266 265 267 Compare ViewPatternsAlternative version: 266 268 267 {{{ 268 269 270 271 269 {{{#!hs 270 fib :: Num a > a > a 271 fib 0 = 1 272 fib 1 = 1 273 fib (n2  let n = n22, n >= 0) = fib (n + 1) + fib n 272 274 }}} 273 275 … … 275 277 From [http://itu.dk/people/drc/tutorials/bidirectional.pdf Bidirectional Typing Rules: A Tutorial]: 276 278 277 {{{ 278 279 280 281 282 283 279 {{{#!hs 280 inferType 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 284 286 }}} 285 287 286 288 could be rewritten using pattern families as: 287 289 288 {{{ 289 290 291 292 293 294 290 {{{#!hs 291  Here ‘Inf’ is a family indexed by ‘ctx’ 292 pattern Inf ctx ty < (inferType ctx > Just ty) 293 294 inferType ctx (If (Inf ctx BoolT) (Inf ctx ty1) (Inf ctx ty2)) 295  ty1 == ty2 = Just ty1 296 inferType ctx If{} = Nothing 295 297 }}} 296 298 297 299 allowing 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: 298 300 299 {{{ 300 301 302 301 {{{#!hs 302 inferType ctx (If (inferType ctx > Just BoolT) (inferType ctx > Just ty1) (inferType ctx > Just ty2)) 303  ty1 == ty2 = Just ty1 304 inferType ctx If{} = Nothing 303 305 }}} 304 306 … … 307 309 Again one could use operators (`:⇒ = Inf`) in which case it the examples follow notation in type theory more closely: 308 310 309 {{{ 310 311 {{{#!hs 312 inferType γ (If (γ :⇒ BoolT) (γ :⇒ τ₁) (γ :⇒ τ₂)) = ... 311 313 }}} 312 314 … … 314 316 Given a regular expression operator `(~=) :: String > String > Maybe [String]` we can define a pattern: 315 317 316 {{{ 317 318 {{{#!hs 319 pattern Match x regexp < ((~= regexp) > Just x) 318 320 }}} 319 321 320 322 where `regexp` is indexes the `Match` pattern family: 321 323 322 {{{ 323 324 324 {{{#!hs 325 firstWord (Match words "[azAZ]+") = words 326 firstWord _ = error "No words found" 325 327 }}} 326 328 327 329 or 328 330 329 {{{ 330 331 {{{#!hs 332 vowels (Match vwls "[aeiou]") = length vwls 331 333 }}} 332 334 333 335 As an operator: 334 336 335 {{{ 336 337 {{{#!hs 338 pattern x :~= regexp < ((~= regexp) > Just x) 337 339 }}} 338 340 … … 342 344 Indexing patterns with prisms from [http://hackage.haskell.org/package/lens4.2/docs/ControlLensPrism.html Control.Lens.Prism]: 343 345 344 {{{ 345 346 347 346 {{{#!hs 347 import Control.Lens.Prism 348 349 pattern Match prism a < (preview prism > Just a) 348 350 }}} 349 351 350 352 one can write 351 353 352 {{{ 353 354 355 354 {{{#!hs 355 bar :: Either c (Either a b) > a 356 bar (Match (_Right._Left) a) = a 357 bar _ = error "..." 356 358 }}} 357 359 … … 359 361 Pattern 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/lens4.2/docs/DataAesonLens.html Data.Aeson.Lens]: 360 362 361 {{{ 362 363 {{{#!hs 364 jsonBlob = "[{\"someObject\": {\"version\": [1,0,3]}}]" 363 365 364 365 366  val = Number 0.0 367 val = jsonBlob ^?! nth 0 . key "someObject" . key "version" . nth 1 366 368 }}} 367 369 368 370 Pattern families allow us to say we want to fetch the same value as `val` using patterns: 369 371 370 {{{ 371 372 {{{#!hs 373 foo (Match (nth 0) (Match (key "someObject") (Match (key "version") (Match (nth 1) a)))) = a 372 374 }}} 373 375 374 376 Which is terribly verbose, but can be improved by introducing: 375 377 376 {{{ 377 378 379 380 378 {{{#!hs 379 pattern Get i a < (preview (nth i) > Just a) 380 pattern Key str a < (preview (key str) > Just a) 381 382 baz (Get 0 (Key "someObject" (Key "version" (Get 1 a)))) = a 381 383 }}} 382 384 383 385 or by writing it infix: 384 386 385 {{{ 386 387 {{{#!hs 388 baz (0 `Get` "someObject" `Key` "version" `Key` 1 `Get` a) = a 387 389 }}} 388 390 389 391 or by defining operators `:→ = Get i a` and `:⇒ = Key`: 390 392 391 {{{ 392 393 }}} 393 {{{#!hs 394 baz (a :→ "someObject" :⇒ "version" :⇒ 1 :→ a) = a 395 }}}