[Haskell-cafe] A practical Haskell puzzle

[Brandon Moore]

> From: Yitzchak Gale <gale at sefer.org>

> Brandon Moore wrote:
> > This code produces and uses a table of all
> >  allowed combinations. I think this makes it easier
> > to understand why the  code works (and is H98).
> > It's just as easy to make a direct version  that
> > produces one requested composition in linear time,
> > so I  haven't worried whether lazy evaluation of this
> > table works  nicely.
> 
> Given that you are allowing serializing and deserializing
> at  every step, you're right that it's not hard to do it
> in Haskell 98. I'm not  convinced that you gain
> anything by building that big table  though.
> 
> Anyway, my idea was to try to find a solution that
> does not  require the runtime cost of serializing and
> deserializing at every step just  to solve a type problem.
> Sorry I didn't make that more clear in my  statement
> of the problem.

My solution does not serialize and deserialize between every
pair of layers. The functions in the table have the form

  show . layer4 . layer3 . layer2 . read

not

  show . layer4 . read . show . layer3 . read . show . layer2 . read

I assume the first is fine, otherwise why mention serialization functions.

The code can also be transformed to avoid the table construction and
produce the requested function in linear time, but the intermediate
types seem much more confusing.

Brandon