[Haskell-cafe] Checking a value against a passed-in constructor?
wren ng thornton
wren at freegeek.org
Tue Jun 2 21:48:17 EDT 2009
Ryan Ingram wrote:
> Dan <danielkcook at gmail.com> wrote:
> > I figured there would be a clever Haskell idiom that would give me a
> > similarly concise route. Does it really require Template Haskell? I can
> > barely parse regular Haskell as it is..
>
[...]
> Alternatively, you can define a fold[1] once:
>
> myval :: MyVal -> (Bool -> a) -> (String -> a) -> a
> myval (Bool b) bool atom = bool b
> myval (Atom s) bool atom = atom s
>
> f x = myval bool atom where
> bool b = ...
> atom s = ...
In terms of boilerplate, this is often far and away the cleanest
solution. I highly recommend if for Write Yourself A Scheme.
The one place where it falls down is when, for whatever reason, you end
up having collections of MyVals which can't sensibly use some set of
constructors. One common example is for type-checking compilers where
you guarantee that ill-typed MyVals cannot be constructed (rather than
doing a verification pass after construction to ensure they're well-typed).
If your type has this problem, using the fold approach often means
writing dummy functions to throw errors on invalid inputs, which in turn
means sacrificing much of the type safety you'd like (even if you use
something like the Maybe or Error monads instead of _|_). A canonical
Haskell trick here is to use GADTs to maintain your type invariants,
rather than using plain ADTs. This technique isn't really suitable for a
first pass at learning Haskell though.
> [1] "fold" here is the general term for this type of function. Examples are
> foldr: http://haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-Base.html#foldr
> maybe: http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Maybe.html#maybe
> either: http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Either.html#either
Two more good resources for folds are:
* http://knol.google.com/k/edward-kmett/catamorphisms/
This has an implementation in Control.Morphism.Cata from
category-extras[1], though the documentation is scarce. If you're
interested in the theory of why folds look and work the way they do,
then this knol is the best starting point. If you're familiar with OOP,
a catamorphism is extremely similar to the recursive Visitor pattern.
The big difference you'll see between this generic solution and
specialized catamorphisms (foldr, maybe, either,...) is that the
specialized versions unpack the Algebra into separate arguments. Also,
this generic solution defines MyVal types with open-recursive functors
and explicit fixed-point operators, whereas the specialized versions
just use Haskell's regular ability to define recursive types (since the
result of |fmap (cata f)| is consumed immediately). Don't let these
trees obscure the forest.
* http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf
This paper presents an innovative solution to the "expression problem"
of defining an open set of constructors for a type. It uses the same
open-recursive functor trick as above and may provide some illustration
of why we may want to bother with it. If you're hungry for more details,
there's an interesting discussion of the paper at [2].
[1] http://hackage.haskell.org/packages/archive/category-extras/
[2] http://wadler.blogspot.com/2008/02/data-types-la-carte.html
--
Live well,
~wren
More information about the Haskell-Cafe
mailing list