scoped type vars, how to manage without?

Zuurbier, E. - AMSXE Erik.Zuurbier@KLM.NL
Fri, 19 Mar 1999 09:14:33 +0100


Richard,
The first thing I think of is making loop a global function and adding p
as a parameter. I think that is what the compiler does anyway.
Regards Erik Zuurbier

paths :: (a -> Bool) (Tree a) -> *[*Path]                  //1
paths p t = loop p t []

loop :: (a -> Bool)(Tree a) *[*Path] -> *[*Path]              //2
loop p (Leaf x) h | p x  = [[]:h]  // one empty path
                  | True = h    // no paths
loop p (Fork l r) h = prefix Left (loop p l [])
                     (prefix Right (loop p r []) h)

prefix :: Choice *[*Path] *[*Path] -> *[*Path]
prefix _ [] h = h
prefix c [x:xs] h = [[c:x]:prefix c xs h]


> Here's a function that shows a pattern I would like to use from time
> to time.
> 
>     :: Tree t = Leaf t | Fork (Tree t) (Tree t)
> 
>     :: Choice = Left | Right
> 
>     :: Path :== [Choice]
> 
>     paths :: (a -> Bool) (Tree a) -> *[*Path]                  //1
>     paths p t = loop t []
>       where loop :: (Tree a) *[*Path] -> *[*Path]              //2
>             loop (Leaf x) h | p x  = [[]:h]  // one empty path
>                             | True = h    // no paths
>             loop (Fork l r) h = prefix Left (loop l [])
>                                  (prefix Right (loop r []) h)
>             prefix :: Choice *[*Path] *[*Path] -> *[*Path]
>             prefix _ [] h = h
>             prefix c [x:xs] h = [[c:x]:prefix c xs h]
> 
> 
> If I try to compile that, I'm told
> specified type is too polymorphic (contains monomorphic type variables)
> and the message directs me to the line labelled //2.
> 
> The reason is obvious:  the type variable 'a' in that line is a DIFFERENT
> type variable from the type variable 'a' in line //1.  In Haskell, they've
> fixed that by letting type variables have a wider scope; without scoped
> type variables there is *NO* way I can specify the type of //2 loop.
> 
> There are several functions that I've recently had to rewrite because
> the compiler wasn't inferring that 'loop :: ... *x -> *x' and I 
> couldn't give it a helping hand because the type was inexpressible.
> Oddly enough, the trick in each case has involved adding a function
> like 'prefix' which I _could_ type.
> 
> What do other people do?
> Are there any plans to add scoped type variables to Clean?
>