[Haskell-cafe] A practical Haskell puzzle

[Heinrich Apfelmus]

Yitzchak Gale wrote:
> You have written a large software system in Haskell. Wishing to
> play to Haskell's strength, you have structured your system
> as a series of composable layers. So you have data types
> 
> Layer1, Layer2, ...
> 
> and functions
> 
> layer2 :: Layer1 -> Layer2
> layer3 :: Layer2 -> Layer3
> ....
> 
> etc.
> 
> Of course you'll want to be able to run any range
> of the layers separately, at least for testing and debugging
> purposes if not for the functionality itself.
> 
> So your UI module (command line or whatever) that launches
> your application provides a data type
> 
> data Layers = Layers Int Int
> 
> that indicates which layers to run, and functions
> 
> deserialize1 :: L.ByteString -> Layer1
> deserialize2 :: L.ByteString -> Layer2
> ....
> 
> serialize1 :: Layer1 -> L.ByteString
> serialize2 :: Layer2 -> L.ByteString
> ....
> 
> etc.
> 
> Now you need a function
> 
> runLayers :: Layers -> L.ByteString -> L.ByteString
> 
> so that the effect is for example
> 
> runLayers (Layers 4 6) = serialize6 . layer6 . layer5 . deserialize4
> 
> [..]
> 
> What is the best way to write runLayers? Feel free to change
> the details of the above design, as long as it meets the
> functionality requirements expressed.

Solution: compose all the functions, but do not use the standard 
function composition (.) to do that. Instead, make a new data type with 
composition as constructor. This way, you can inspect the composition 
afterwards and run only parts of it.

Solution, put differently: Make a type-safe list of the whole chain of 
functions. Then, the  runLayers  function throws away everything outside 
the range and composes what is left.

Here a rough sketch of what I have in mind:

    data Compoz a b where
        Id   :: Compoz a a
        Cons :: (Serialize a,b,c) => (b -> c) -> Compoz a b -> Compoz a c

    -- this value needs to be written out
    chain = layer20 `Cons` layer 19 ...

    runLayers (Layer a b) =
        deserialize . (run . takeC (b-a) . dropC a $ chain) . serialize

    takeC :: Int -> Compoz a b -> (exists c. Compoz a c)
    dropC :: Int -> Compoz a b -> (exists c. Compoz c b)

    run :: Compoz a b -> (a -> b)

Of course, you will have to wrestle with the existential types for 
takeC  and  dropC  a bit, but that shouldn't be much of a problem. For 
instance, you can fuse these functions into  runLayers  and hide the 
existential types somewhere in the recursion.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com