[Haskell-cafe] an evil type hangs GHC

[roconnor at theorem.ca]

See <http://www.haskell.org/pipermail/haskell/2006-September/018497.html>

On Fri, 12 Nov 2010, Petr Pudlak wrote:

> On Fri, Nov 12, 2010 at 07:52:53PM +0100, Petr Pudlak wrote:
>> Hi, I was playing with the following example I found in D.A.Turner's paper 
>> Total Functional Programming:
>> 
>>> data Bad a = C (Bad a -> a)
>>> 
>>> bad1 :: Bad a -> a
>>> bad1 b@(C f) = f b
>>> 
>>> bad2 :: a
>>> bad2 = bad1 (C bad1)
>> 
>> To my surprise, instead of creating a bottom valued function (an infinite 
>> loop), I managed to send the GHC compiler (ver. 6.12.1) to an infinite 
>> loop. Could anybody suggest an explanation? Is this a GHC bug? Or is this 
>> "Bad" data type so evil that type checking fails?
>>
>>    Thanks,
>>    Petr
>
> PS: The following code compiles, the difference is just in modifying "bad2" 
> to include an argument:
>
>> data Bad a = C (Bad a -> a)
>> 
>> bad1 :: Bad a -> a
>> bad1 b@(C f) = f b
>> 
>> bad2 :: (a -> a) -> a
>> bad2 f = bad1 (C $ f . bad1)
>
> [BTW, "bad2" has the type of the Y combinator and indeed works as expected:
>
>> factorial :: (Int -> Int) -> Int -> Int
>> factorial _ 0 = 1
>> factorial r n = n * (r (n-1))
>> 
>> main :: IO ()
>> main = print $ map (bad2 factorial) [1..10]
>
> ... so one can get general recursion just by crafting such a strange data 
> type.]
>

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''