funpat

A generalization of pattern matching

Latest on Hackage:0.1

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by Gergely Devai
Maintained by deva@inf.elte.hu

This library provides pattern matching with restricted function patterns (RFPs). An expression is an RFP iff exists an equivalent valid Haskell pattern. For example ("abc" ++ xs) is an RFP, because ('a' : 'b' : 'c' : xs) is an equivalent valid Haskell pattern. On the other hand, (xs ++ "abc") is not an RFP. Details are discussed in the paper Restricted Function Patterns presented at TFP 2011.

Example 1. Here is a function to chop off the prefix "prefix" of strings:

unprefix :: String -> String
unprefix s = match s $ do
   with $ \z ->   "prefix" ++ z ~> z
   with $ \z ->   z             ~> z

Example 2. Let's have a small embedded language:

data Expr = Symbol String | Expr :$ Expr
    deriving (Eq,Show,Typeable)

instance Num Expr where
    fromInteger n = Symbol $ show n
    a + b = Symbol "+" :$ a :$ b
    a * b = Symbol "*" :$ a :$ b
    ...

In order to allow pattern matching on expressions of type Expr, the following Matchable instance is needed:

instance Matchable Expr where
    Symbol s .=. Symbol z   = Just [s :=: z]
    (e :$ f) .=. (g :$ h)   = Just [e :=: g, f :=: h]
    _ .=. _                 = Nothing

Now we can pattern match on expressions even if the constructors of the Expr type were hidden:

transform :: Expr -> Expr
transform e = match e $ do
    with $ \a ->        0 + a       ~> a
    with $ \a b c ->    a * (b + c) ~> a * b + a * c
    with $ \a ->        a           ~> a
Depends on:
Used by 1 package:
comments powered byDisqus