| 256 | --------------------------- |
| 257 | == Features views can have == |
| 258 | |
| 259 | The 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 | |
| 263 | This 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 | }}} |
| 270 | Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc. |
| 271 | |
| 272 | Of 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 | |
| 278 | In 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 | }}} |
| 284 | then you could use it in patterns thus: |
| 285 | {{{ |
| 286 | f :: String -> String |
| 287 | f (regexp "[a-z]*" -> (name, rest)) = ... |
| 288 | }}} |
| 289 | Of course, the argument does not need to be a constant as it is here. |
| 290 | |
| 291 | The (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 | |
| 303 | With 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 | }}} |
| 308 | Here the first argument `p` can be thought of as a pattern passed to `g`, which |
| 309 | is used to match the second argument of `g`. |
| 310 | |
| 311 | === Implicit `Maybe` feature === |
| 312 | |
| 313 | In 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 | |
| 319 | Some 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 | |
| 321 | By 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 | |
| 337 | Projection 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 | |
| 349 | While 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 | }}} |
| 354 | represents 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 | }}} |
| 361 | These three properties are expensive to calculate but all three only |
| 362 | depend on the result of a single depth first search. By projecting the |
| 363 | disjoint sum to several `Maybe`s, the depth first search has to be |
| 364 | repeated every time. More importantly, there is *no way* for the compiler to optimize this because that would mean common subexpression elimination across |
| 365 | functions. |
| 366 | |
| 367 | === Transparent ordinary Patterns === |
| 368 | The 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 | }}} |
| 376 | This certainly discourages ordinary pattern matching. In other words, |
| 377 | implementing the proposal has considerable impact on ordinary pattern |
| 378 | matching (not in semantics but in use). |
| 379 | |
| 380 | The problem that needs to be solved is to introduce abstraction "after the fact". |