= Solution
Use the symmetric <tree fold> equations for the other <algebraic data type>:
``
foldZag (fZag,eZag) (fZig,eZig) Nal = eZag
foldZag (fZag,eZag) (fZig,eZig) (Cans x z) =
fZag x (foldZig (fZig,eZig) (fZag,eZag) z)
``
The most general <type signatures>, using the same schematic variable names independently for each function, are
``
foldZig :: (a -> s -> r, r) -> (b -> r -> s, s)
-> Zig a b -> r
foldZag :: (a -> s -> r, r) -> (b -> r -> s, s)
-> Zag a b -> r
``
For `foldZig`, the first empty value has type `r`, so the first combining function must return `r`. Its label argument has type `a`. The recursively folded tail has some independent result type `s`, giving `a -> s -> r`. The second combining function consumes a `b` label and an `r` result and returns `s`, giving `b -> r -> s`. The second empty value has type `s`. Swapping the two handler pairs and the label types makes the recursive call well-typed. The identical argument applies to `foldZag`.
\b[The two result types need not coincide.] For example, one handler can return an <integer> and the other a <list>; forcing both results to have one type would lose <parametric polymorphism> allowed by the definitions.
Back to article page
