[Haskell-cafe] "Least common supertype"?
noteed at gmail.com
Wed Nov 11 15:36:53 EST 2009
Least Common Generalization.
2009/11/11 Eugene Kirpichov <ekirpichov at gmail.com>:
> Is the name of the concept.... "Most general unifier" (MGU) ? (See:
> Hindley-Milner type inference)
> 2009/11/11 Sean Leather <leather at cs.uu.nl>:
>> 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.
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
> Eugene Kirpichov
> Web IR developer, market.yandex.ru
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe