Changes between Version 15 and Version 16 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 10:47:23 AM (8 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---------------------------