On Tue, Oct 28, 2003 at 11:56:21AM +0100, Josef Svenningsson wrote:
> On Mon, 27 Oct 2003, Josef Svenningsson wrote:
> > This is a very nice technique. As an exercise to the reader I suggest the
> > following program:
> >
> > \being{code}
> > data Tree a = Branch a (Tree (a,a)) | Leaf
> >
> > cross f (a,b) = (f a,f b)
> >
> > main1 =
> > let mapTree :: (a -> b) -> Tree a -> Tree b
> > mapTree = \f tree -> case tree of
> > Branch a t -> Branch (f a) (mapTree (cross f) t)
> > Leaf -> Leaf
> > in mapTree id (Branch 42 Leaf)
> > \end{code}
> >
> I realise I was perhaps a bit dense in my previous mail. It was not my
> intention to try to sound smart. Sorry for that.
>
> Does anyone know how to apply the transformation suggested by Paul Hudak
> to my program and make it typecheck? Does there exist a type system where
> the transformed program typechecks? I suppose so but I don't quite know
> what it would look like.
Polymorphic recursion implies a fix with a rank 3 type. GHC can handle
those, but each one needs its own declaration, as in
type MapTree = forall a b. (a -> b) -> Tree a -> Tree b
fixMT :: (MapTree -> MapTree) -> MapTree
fixMT f = f (fixMT f)
mapTree' = fixMT (\ (mapTree :: MapTree) -> \f tree -> case tree of
Branch a t -> Branch (f a) (mapTree (cross f) t)
Leaf -> Leaf)
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
