... | @@ -534,36 +534,51 @@ guaranteed. |
... | @@ -534,36 +534,51 @@ guaranteed. |
|
|
|
|
|
---
|
|
---
|
|
|
|
|
|
## More examples
|
|
## Use cases and examples
|
|
|
|
|
|
### Erlang-style parsing
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
The expression to the left of the `->` can mention variables bound in earlier patterns.
|
|
### Sequences
|
|
For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ([ "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07](http://user.it.uu.se/~kostis/Papers/index.html#Conference)). Suppose we had a parsing function thus:
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
```wiki
|
|
```wiki
|
|
bits :: Int -> ByteString -> Maybe2 Word ByteString
|
|
data ViewL a
|
|
-- (bits n bs) parses n bits from the front of bs, returning
|
|
= EmptyL
|
|
-- the n-bit Word, and the remainder of bs
|
|
| (:<) a (Seq a)
|
|
```
|
|
|
|
|
|
|
|
|
|
viewl :: Seq a -> ViewL a
|
|
|
|
|
|
Then we could write patterns like this:
|
|
data ViewR a
|
|
|
|
= EmptyR
|
|
|
|
| (:>) (Seq a) a
|
|
|
|
|
|
```wiki
|
|
viewr :: Seq a -> ViewR a
|
|
parsePacket :: ByteString -> ...
|
|
|
|
parsePacket (bits 3 -> n (bits n -> val bs)) = ...
|
|
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
This parses 3 bits to get the value of `n`, and then parses `n` bits to get
|
|
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.
|
|
the value of `val`.
|
|
|
|
|
|
|
|
|
|
The observations from [ Okasaki: Breadth-First Numbering - Lessons ... ](http://citeseer.ist.psu.edu/356396.html) suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of.
|
|
|
|
|
|
|
|
### Designing data structures
|
|
|
|
|
|
### Sets as lists
|
|
|
|
|
|
|
|
|
|
The abstractional power views offer can also be put to good use when designing data structures, as the following papers show
|
|
|
|
|
|
Here is a module implementing sets as lists:
|
|
- [ R.Hinze: A fresh look on binary search trees](http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz).
|
|
|
|
- [ R.Hinze: A Simple Implementation Technique for Priority Search Queues](http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf)
|
|
|
|
|
|
|
|
### Sets and Inductive Graphs
|
|
|
|
|
|
|
|
|
|
|
|
Having the value input feature, even set like data structures come in reach for pattern matching. In fact, the key idea of [ M.Erwig: Inductive Graphs and Functional Graph Algorithms](http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz) is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch.
|
|
|
|
|
|
|
|
|
|
|
|
Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby.
|
|
|
|
|
|
```wiki
|
|
```wiki
|
|
module Set( Set, empty, insert, delete, has) where
|
|
module Set( Set, empty, insert, delete, has) where
|
... | @@ -584,8 +599,31 @@ module Set( Set, empty, insert, delete, has) where |
... | @@ -584,8 +599,31 @@ module Set( Set, empty, insert, delete, has) where |
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence,
|
|
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.
|
|
but the second is merely an argument to `has` and is a bound occurrence.
|
|
|
|
|
|
### Erlang-style parsing
|
|
|
|
|
|
|
|
|
|
|
|
The expression to the left of the `->` can mention variables bound in earlier patterns.
|
|
|
|
For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ([ "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07](http://user.it.uu.se/~kostis/Papers/index.html#Conference)). Suppose we had a parsing function thus:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
bits :: Int -> ByteString -> Maybe2 Word ByteString
|
|
|
|
-- (bits n bs) parses n bits from the front of bs, returning
|
|
|
|
-- the n-bit Word, and the remainder of bs
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
Then we could write patterns like this:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
parsePacket :: ByteString -> ...
|
|
|
|
parsePacket (bits 3 -> n (bits n -> val bs)) = ...
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
This parses 3 bits to get the value of `n`, and then parses `n` bits to get
|
|
|
|
the value of `val`.
|
|
|
|
|
|
### N+k patterns
|
|
### N+k patterns
|
|
|
|
|
... | | ... | |