
Least Common Generalization.
Cheers,
Thu
2009/11/11 Eugene Kirpichov
Is the name of the concept.... "Most general unifier" (MGU) ? (See: Hindley-Milner type inference)
2009/11/11 Sean Leather
: Is there a name for the following concept? Can you point me to any references on it?
Suppose I have the following two functions ...
swap1 :: (Int, Char) -> (Char, Int) swap2 :: (Char, Int) -> (Int, Char)
... and, for some reason, I think I can unify these into a single function. I think, hmm, given that the structure is that same, let's do a first pass:
swap? :: (a, b) -> (c, d)
But then I go back to the input types to confirm that this will work, and, alas, it will not, because there are similarities that I missed. This is way too general. I need to ensure that what's an Int stays an Int and likewise for Char.
swap! :: (a, b) -> (b, a)
And now I have found a type that is more general than swap1 and swap2 and yet not so general that the shared constraints are left out. This seems somewhat analogous to the least common multiple.
Another example is the following:
showFloat :: Float -> String showBool :: Bool -> String
We could say the more general type is ...
show? :: a -> String
... but then we lose the implied constraint that we must know something about 'a' to produce a string. So, we add back such some such constraint:
show! :: (Show a) => a -> String
Of course, with all of this, it may not be clear what to do about the definitions of the functions, but I'm curious if there's a name for the concept from a type perspective.
Thanks, Sean
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe