You can help ghci out a bit with type synonyms:
type T a = (a, a)
type T2 a = T (T a)
type T4 a = T2 (T2 a)
type T8 a = T4 (T4 a)
type T16 a = T8 (T8 a)
f0 :: a - T a
f1 :: a - T2 a
f2 :: a - T4 a
f3 :: a - T8 a
f4 :: a - T16 a
f0 x = (x,x)
f1 = f0 . f0
f2 = f1 . f1
f3 = f2 . f2
f4
On Wednesday 14 October 2009 5:25:10 am Roel van Dijk wrote:
With newtypes I can probably abstract even more. (newtype X a b = X (a (a
b))
In fact, with GHC extensions, you don't need newtypes:
{-# LANGUAGE LiberalTypeSynonyms #-}
type T a = (a,a)
type X f a = f (f a)
f0 :: a - T
On Wed, Oct 14, 2009 at 11:53 AM, Dan Doel dan.d...@gmail.com wrote:
In fact, with GHC extensions, you don't need newtypes:
{-# LANGUAGE LiberalTypeSynonyms #-}
Ah, I completely forgot about that language extension. Thanks!
Yeah. Asking for the type of 'f4 . f4' doesn't seem to expand the
On Wednesday 14 October 2009 6:15:11 am Roel van Dijk wrote:
If you declare a type for f5 then ghci must check if that type is
correct, which triggers the explosion. If you don't declare a type
then it won't infer the type until necessary. Basically, ghci is lazy
Well, that may be the
On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones
simo...@microsoft.com wrote:
| Is there any way to define type-level multiplication without requiring
| undecidable instances?
|
| No, not at the moment. The reasons are explained in the paper Type
| Checking with Open Type Functions
Yes, there are simple H-M examples that are exponential.
x0 = undefined
x1 = (x1,x1)
x2 = (x2,x2)
x3 = (x3,x3)
...
xn will have a type with 2^n type variables so it has size 2^n.
-- Lennart
On Tue, Oct 13, 2009 at 6:04 PM, Brad Larsen brad.lar...@gmail.com wrote:
On Tue, Oct 13, 2009 at 3:37
2009/10/13 Lennart Augustsson lenn...@augustsson.net:
Yes, there are simple H-M examples that are exponential.
x0 = undefined
x1 = (x1,x1)
x2 = (x2,x2)
x3 = (x3,x3)
...
xn will have a type with 2^n type variables so it has size 2^n.
Reformulated:
let dup x = (x,x)
:t dup . dup . dup . dup
On Tue, Oct 13, 2009 at 12:32 PM, Serguey Zefirov sergu...@gmail.com wrote:
2009/10/13 Lennart Augustsson lenn...@augustsson.net:
Yes, there are simple H-M examples that are exponential.
x0 = undefined
x1 = (x1,x1)
x2 = (x2,x2)
x3 = (x3,x3)
...
xn will have a type with 2^n type variables
On Tuesday 13 October 2009 1:06:41 pm Brad Larsen wrote:
Good example! I have a feeling that the `dup' example is a bit
contrived, not something that one would be likely to find in the wild.
This is, after all, why HM is useful. In general, there are programs that take
exponential time/space
