Changes between Version 19 and Version 20 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 12:19:32 PM (9 years ago)
Author:
guest
Comment:

abstract data type examples

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatterns

    v19 v20  
    411411
    412412---------------------------
    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
     415Whether 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
     419Lists, 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
     434Thus, 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
     436The 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
     440The 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
     447Having 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
     449Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby.
    435450{{{
    436451module Set( Set, empty, insert, delete, has) where
     
    450465  insert x (S xs)         = S (x:xs)
    451466}}}
    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.
     467Notice 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
     471The expression to the left of the `->` can mention variables bound in earlier patterns.
     472For 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}}}
     478Then we could write patterns like this:
     479{{{
     480  parsePacket :: ByteString -> ...
     481  parsePacket (bits 3 -> n (bits n -> val bs)) = ...
     482}}}
     483This parses 3 bits to get the value of `n`, and then parses `n` bits to get
     484the value of `val`. 
    454485
    455486=== N+k patterns ===