413 | | == More examples == |
414 | | |
415 | | === Erlang-style parsing === |
416 | | |
417 | | The expression to the left of the `->` can mention variables bound in earlier patterns. |
418 | | For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ([http://user.it.uu.se/~kostis/Papers/index.html#Conference "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07]). Suppose we had a parsing function thus: |
419 | | {{{ |
420 | | bits :: Int -> ByteString -> Maybe2 Word ByteString |
421 | | -- (bits n bs) parses n bits from the front of bs, returning |
422 | | -- the n-bit Word, and the remainder of bs |
423 | | }}} |
424 | | Then we could write patterns like this: |
425 | | {{{ |
426 | | parsePacket :: ByteString -> ... |
427 | | parsePacket (bits 3 -> n (bits n -> val bs)) = ... |
428 | | }}} |
429 | | This parses 3 bits to get the value of `n`, and then parses `n` bits to get |
430 | | the value of `val`. |
431 | | |
432 | | === Sets as lists === |
433 | | |
434 | | Here is a module implementing sets as lists: |
| 413 | == Use cases and examples == |
| 414 | |
| 415 | Whether views are really worth it can only be decide on the base of examples. Some are situations where you programmed and thought "I wish I had a view for that". Some are those snippets of code that unexpectedly use views to good effect. |
| 416 | |
| 417 | === Sequences === |
| 418 | |
| 419 | Lists, queues, ByteStrings and 2-3-finger trees are all implementations of sequences, but only ordinary lists can be deconstructed using pattern matching. The need for list patterns on arbitrary sequence data structures is desperate. As if to ease the pain, Data.Sequence even defines the views from the left and from the right |
| 420 | {{{ |
| 421 | data ViewL a |
| 422 | = EmptyL |
| 423 | | (:<) a (Seq a) |
| 424 | |
| 425 | viewl :: Seq a -> ViewL a |
| 426 | |
| 427 | data ViewR a |
| 428 | = EmptyR |
| 429 | | (:>) (Seq a) a |
| 430 | |
| 431 | viewr :: Seq a -> ViewR a |
| 432 | }}} |
| 433 | |
| 434 | Thus, the presence of views has a direct impact on existing Haskell libraries. Arguably, a view proposal that wants to be effective for abstract data types likely has to have the transparent ordinary patterns feature. |
| 435 | |
| 436 | The observations from [http://citeseer.ist.psu.edu/356396.html Okasaki: Breadth-First Numbering - Lessons ... ] suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of. |
| 437 | |
| 438 | === Designing data structures === |
| 439 | |
| 440 | The abstractional power views offer can also be put to good use when designing data structures, as the following papers show |
| 441 | |
| 442 | * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. |
| 443 | * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze: A Simple Implementation Technique for Priority Search Queues] |
| 444 | |
| 445 | === Sets and Inductive Graphs === |
| 446 | |
| 447 | Having the value input feature, even set like data structures come in reach for pattern matching. In fact, the key idea of [http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz M.Erwig: Inductive Graphs and Functional Graph Algorithms] is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch. |
| 448 | |
| 449 | Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby. |
452 | | Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence, |
453 | | but the second is merely an argument to `has` and is a bound occurrence. |
| 467 | Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence, but the second is merely an argument to `has` and is a bound occurrence. |
| 468 | |
| 469 | === Erlang-style parsing === |
| 470 | |
| 471 | The expression to the left of the `->` can mention variables bound in earlier patterns. |
| 472 | For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ([http://user.it.uu.se/~kostis/Papers/index.html#Conference "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07]). Suppose we had a parsing function thus: |
| 473 | {{{ |
| 474 | bits :: Int -> ByteString -> Maybe2 Word ByteString |
| 475 | -- (bits n bs) parses n bits from the front of bs, returning |
| 476 | -- the n-bit Word, and the remainder of bs |
| 477 | }}} |
| 478 | Then we could write patterns like this: |
| 479 | {{{ |
| 480 | parsePacket :: ByteString -> ... |
| 481 | parsePacket (bits 3 -> n (bits n -> val bs)) = ... |
| 482 | }}} |
| 483 | This parses 3 bits to get the value of `n`, and then parses `n` bits to get |
| 484 | the value of `val`. |