Changes between Version 19 and Version 20 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 12:19:32 PM (7 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 ===