[Haskell-beginners] type variables

[Daniel Fischer]

On Tuesday 24 August 2010 13:45:10, Daniel Fischer wrote:
> On Tuesday 24 August 2010 13:09:56, Thomas wrote:
> > Hello!
> >
> > I have a question about type variables.
> > The following works:
> >
> > type XMLCallback a = (XMLTreeNode -> a -> [Int] -> [XMLTreeNode] -> a)
> >
> > xmlTreeFold :: XMLCallback a -> a -> Maybe XMLTreeNode -> Maybe a
> > xmlTreeFold _ _ Nothing = Nothing
> > xmlTreeFold func acc (Just tree) =
> >    Just (xmlTreeWalkerWithContext func acc tree [] [])
> >
> > testFold :: XMLCallback [(XMLTreeNode, [Int], [XMLTreeNode])]
> > testFold node a is ns =
> > 	if (length is) > 1 then ((node, is, ns):a) else a
>
> Do not use `if length list > 1', if the list is long, that takes long
> too. Use `if not (null $ drop 1 list)'.
>
> > => xmlTreeFold testFold [] tree
> >
> > But if I change the type declaration of 'testFold' to:
> > testFold :: XMLCallback a
> > it will not compile.
> >
> > I thought that 'a' is a type /variable/ thus able to hold any type,
> > for example, but not limited to '[(XMLTreeNode, [Int],
> > [XMLTreeNode])]'.
>
> Right. However, the definition of testFold says a can't be *any* type.
> In the then-branch, the result is
> (node, is, ns) : a,
> which is a list, and forces a to be a list too, so the type of testFold
> cannot be more general than
>
> XMLCallback [a]
>
> (and that should compile).

Arrgh. Remember not to post before the third cup of tea.
Firstly, the fact that (node, is, ns) is consed to the front of a, forces 
the list type to be [(x,y,z)] for some x, y, z, with

node :: x
is :: y
ns :: z

Then use of length (or some other list function) forces y = [u].

So the type of testFold has to be

testFold :: x -> [(x,[u],z)] -> [u] -> z -> [(x,[u],z)]

If it is to be XMLCallback var, that has to be

testFold :: XMLTreeNode -> var -> [Int] -> [XMLTreeNode] -> var

So,

x = XMLTreeNode
[u] = [Int]
z = [XMLTreeNode]

var = [(x,[u],z)] = [(XMLTreeNode,[Int],[XMLTreeNode])]

>
> > Why do I need to be that much more specific in the declaration for
> > 'testFold'? Especially since in the declaration of 'xmlTreeFold' the
> > 'XMLCallback a' is well received.
>
> In the definition of xmlTreeFold, nothing restricts the type of the
> accumulator argument, so it can be anything.
>
> > Thanks for any insights,
> > Thomas