[Haskell-cafe] "Least common supertype"?

[minh thu]

For some reference, I found some definition for the lcg function in
papers from [1].

In fact, I began to implement the type inference algorithm of System
CT (the version of 1999, it has been revised since) and I have an
implementation of lcg in that setting. I plan to upload the code to
github; I can do it earlier than expected if you're interested.

[1] http://homepages.dcc.ufmg.br/~camarao/

Cheers,
Thu

2009/11/11 minh thu <noteed at gmail.com>:
> Least Common Generalization.
>
> Cheers,
> Thu
>
> 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.
>>>
>>> Thanks,
>>> Sean
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>>>
>>
>>
>>
>> --
>> Eugene Kirpichov
>> Web IR developer, market.yandex.ru
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>