On Thursday 04 February 2010 16:32:36 Sean Devlin wrote:
> Pattern matching
Ok. Pattern matching is a core construct from the ML family of languages and,
consequently, is now ubiquitous in F#, OCaml, Standard ML and Haskell as well
as Scala. In the MLs, pattern matching is the only way to destructure data.
For example, you can extract the two elements of a pair and bind their values
to the variable names "a" and "b" as follows (OCaml/F# code):
let a, b = a_pair
Pattern matching is a powerful technique that has been generalized in many
ways, so you can also destructure a pair of pairs by nesting patterns:
let (x0, y0), (x1, y1) = two_vectors
Pattern matching is also used for dispatch in those languages (although the
object oriented ones including OCaml and F# also provide method dispatch).
Moreover, patterns can match on more than just objects, e.g. numbers:
let rec factorial = function
| 0 | 1 -> 1
| n -> n * factorial(n-1)
Note the "or-pattern" 0|1 to match either 0 or 1.
A more advanced example including nesting, or-patterns, guarded patterns
(with "when") and named subpatterns is to merge two sorted lists (OCaml/F#
code):
let rec merge = function
| [], xs | xs, [] -> xs
| x::xs', (y::_ as ys) when x <= y -> x::merge(xs', ys)
| xs, y::ys' -> y::merge(xs, ys')
I've written about it here:
http://www.ffconsultancy.com/ocaml/benefits/pattern_matching.html
You may also be interested in this symbolic simplifier challenge:
http://www.lambdassociates.org/studies/study10.htm
Note that the Common Lisp solutions are 50-160% longer and 1.7-7.5x slower
than the OCaml.
Pattern matching is uncommon is Lisps because its core benefits (static
checking and performance) rely upon static type information. However, some
dynamic languages (e.g. Mathematica) do provide and make heavy use of pattern
matching. On the other hand, dynamic languages can do lots of funky things
with pattern matching that static languages do not, most notably allowing
patterns to be generated at run-time (even MetaOCaml does not allow this).
A major disadvantage of pattern matching can be that it requires libraries to
expose their internals in order for a user to be able to pattern match over
them. This problem was solved using view patterns which are bundled with F#
(as "active patterns") and Scala (as "extractors").
I have found pattern matching to be extremely valuable not only because it
permits very clear and concise solutions to many problems but also because
the static checking it provides allows me to leverage a static type system to
prove aspects of correctness that remove major classes of bugs from real
applications.
HTH.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
