[Haskell-cafe] Checking a value against a passed-in constructor?

[wren ng thornton]

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