Changes between Version 15 and Version 16 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 10:47:23 AM (9 years ago)
Author:
guest
Comment:

categorizing the different features

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatterns

    v15 v16  
    254254guaranteed.
    255255
     256---------------------------
     257== Features views can have ==
     258
     259The main goal of views is to introduce computations into pattern matches thus introducing abstraction from hard wired constructors. To distinguish between the different proposals, we pick out the key features
     260
     261=== Value input feature ===
     262
     263This features allows to introduce additional parameters into the computation. Perhaps the most basic example are (n+k) patterns
     264{{{
     265  fib :: Int -> Int
     266  fib 0 = 1
     267  fib 1 = 1
     268  fib (n + 2) = fib (n + 1) + fib n
     269}}}
     270Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc.
     271
     272Of course, the real power unfolds when the extra parameter can be given at runtime
     273{{{
     274   f :: Int -> Int -> ...
     275   f n (n + m) = m           -- f a b = (b - a)
     276}}}
     277
     278In the proposed view pattern (''expr'' `->` ''pat''), ''expr'' is an arbitrary Haskell expression. Thus, the lightweight proposal has the '''value input feature'''. For another example, suppose you wrote a regular expression matching function:
     279{{{
     280  regexp :: String -> String -> Maybe (String, String)
     281  -- (regexp r s) parses a string matching regular expression r
     282  --    the front of s, returning the matched string and remainder of s
     283}}}
     284then you could use it in patterns thus:
     285{{{
     286  f :: String -> String
     287  f (regexp "[a-z]*" -> (name, rest)) = ...
     288}}}
     289Of course, the argument does not need to be a constant as it is here.
     290
     291The (n+k) patterns can be implemented (with different syntax, of course) with a view function that tests for values greater than or equal to n:
     292{{{
     293   np :: Num a => a -> a -> Maybe a
     294   np k n | k <= n    = Just (n-k)
     295              | otherwise = Nothing
     296
     297   f :: Num a => a -> Int
     298   f (np 10 -> n) = n           -- Matches values >= 10, f a = (a - 10)
     299   f (np 4  -> n) = 1           -- Matches values >= 4
     300   f other        = 2
     301}}}
     302
     303With the value input feature, in a sense, patterns become first class. For example, one could pass a pattern as an argument to a function thus:
     304{{{
     305  g :: (Int -> Maybe Int) -> Int -> ...
     306  g p (p -> x) = ...
     307}}}
     308Here the first argument `p` can be thought of as a pattern passed to `g`, which
     309is used to match the second argument of `g`.
     310
     311=== Implicit `Maybe` feature ===
     312
     313In functional languages, pattern matching is used to inspect a sum types like `Either Int String` and to proceed with the matching alternative. We can always project a choice between multiple alternatives to choice between one alternative (`Just`) and failure (`Nothing`):
     314{{{
     315   maybeLeft  :: Either a b -> Maybe a
     316   maybeRight :: Either a b -> Maybe b
     317}}}
     318
     319Some proposals build their patterns entirely from from such single alternative de-constructors functions of type `a -> Maybe b`, while some allow projection to multiple alternatives.
     320
     321By restricting de-constructors to be of type `a -> Maybe b`, the Maybe can be made implicit, it doesn't show up in the pattern. Example:
     322{{{
     323    data Product = ....some big data type...
     324    type Size = Int
     325   
     326    smallProd, medProd, bigProd :: Product -> Maybe Size
     327    smallProd p = ...
     328    medProd   p = ...
     329    bigProd   p = ...
     330   
     331    f :: Product -> ...
     332    f (smallProd -> s) = ...
     333    f (medProd   -> s) = ...
     334    f (bigProd   -> s) = ...
     335}}}
     336
     337Projection to multiple alternatives requires a new data type for every group of alternatives introduced.
     338{{{
     339    data Dimensions = Small | Medium | Big      -- View type
     340    prodSize :: Product -> Dimensions
     341    prodSize = ...
     342   
     343    f :: Product -> ...
     344    f (prodSize -> Small)  = ...
     345    f (prodSize -> Medium) = ...
     346    f (prodSize -> Big)    = ...
     347}}}
     348
     349While the implicit `Maybe a` is more compositional and nicely integrates with already existing uses of the `Maybe`-type, it cannot share expensive computations across multiple alternatives. This is a strong argument against the implicit `Maybe a`. To illustrate the problem, suppose that
     350
     351{{{
     352   data Graph
     353}}}
     354represents a graph and that we want a function
     355{{{
     356   g :: Graph -> [...]
     357   g (forest -> xs) = concatMap g xs
     358   g (tree ->)      = ...
     359   g (dag  ->)      = ...
     360}}}
     361These three properties are expensive to calculate but all three only
     362depend on the result of a single depth first search. By projecting the
     363disjoint sum to several `Maybe`s, the depth first search has to be
     364repeated every time. More importantly, there is *no way* for the compiler to optimize this because that would mean common subexpression elimination across
     365functions.
     366
     367=== Transparent ordinary Patterns ===
     368The lightweight view proposal has different syntax for view functions and ordinary pattern matches, they are not interchangeable. To use the abstraction view functions offer, you have to anticipate whether you can stick to ordinary constructors or whether you will switch to abstract constructors at some time. For example, a stack abstraction would have to use view patterns if we want to be able to change the concrete representation of stacks later on.
     369{{{
     370    type Stack a = [a]
     371   
     372    f :: Stack a
     373    f (null?)     = ...
     374    f (pop? x xs) = ...
     375}}}
     376This certainly discourages ordinary pattern matching. In other words,
     377implementing the proposal has considerable impact on ordinary pattern
     378matching (not in semantics but in use).
     379
     380The problem that needs to be solved is to introduce abstraction "after the fact".
    256381
    257382---------------------------