Not sure if this question fits here, but I'm looking to implement (or try to) Hakell's type classes into my own language, however I don't understand how resolution works on recursive types like the one below;
data Bush a = Leaf a | Nest (Bush (a, a))
I then implemented a show method on it in a single definition like this:
instance (Show a) => Show (Bush a) where
show (Leaf x) = show x
show (Nest x) = show x
It works fine, but I can't understand how the show method would be passed at runtime.
Consider we have a (Bush Int); it might be a leaf (in that case it'd call show on Int) or it could be a nest (Bush (Int, Int)), then it'd require a different show, which could then require yet another one, and so on. Is the resolution done at runtime, or how is that possible?
Don't know if it helps, but I did find a raw definiton given that a is a semigroup (hence a combine argument). I find it weird how the first approach, using instances, works without it.
showx :: Bush a -> ((a, a) -> a) -> a
showx (Leaf x) _ = x
showx (Nest bx) combine = combine (showx bx (\(pair1, pair2) -> (combine pair1, combine pair2)))
1 Answer 1
The instance essentially works the same way as your last example. Implicit is the fact that there is an:
instance (Show a, Show b) => Show (a, b) where
...
This specializes to Show a => Show (a, a).
In the case:
show (Nest x) = show x
We need Show (Branch (a, a)), which requires Show (a, a), which using the pair instance reduces to Show a.
Perhaps the other aspect to note is that the Show (Branch a) instance is—like showx—polymorphically recursive. So when you recursively refer to show, it might be using the Show (Branch a) instance at a different a.
As for how this works, it's true that there is no fixed, finite amount of 'dictionaries' that covers all the Show constraints necessary, so they must be built at runtime (assuming that's how you're implementing type classes). However, those dictionaries are all generated by a finite amount of instance schemas, namely:
Show a => Show (a , a)
Show a => Show (Branch a)
Each of these is defined uniformly for all a, and we're just progressively using different instantiations of them that delegate to dictionaries we've previously built. So we can statically resolve the instance schemas required to build the arbitrary dictionaries at runtime, and generate code for that. This is the same as how your combine for arbitrarily nested tuples is built by repeatedly applying a fixed way of building it out of the smaller combine.