Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: fromIntegral (Felipe Lessa)
2. Re: fromIntegral (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Fri, 1 Oct 2010 12:38:03 -0300
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] fromIntegral
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Fri, Oct 1, 2010 at 12:08 PM, Russ Abbott <[email protected]> wrote:
]
] On Thu, Sep 30, 2010 at 10:25 PM, Felipe Lessa <[email protected]>
] wrote:
]] Now, maybe 'fromIntegral' has something more than polymorphism?
]] Well, it has typeclasses. Â But we can represent those as
]] data types, so we could write
]]
]] Â fromIntegralD :: Integral a -> Num b -> a -> b
]] Â fromIntegralD intrDictA numDictB =
]] Â Â fromIntegral numDictB . toInteger intrDictA
]
] I'm afraid I don't understand this. Moreover, I couldn't get the preceding
] to load without error.
Let's simplify things a little bit to make a runnable example.
Suppose we have
> class MonoidClass a where
> mc_empty :: a
> mc_append :: a -> a -> a
We can construct the following function:
> mc_concat :: MonoidClass a => [a] -> a
> mc_concat [] = mc_empty
> mc_concat (x:xs) = mc_append x (mc_concat xs)
Pretty standard stuff.
Now, the 'MonoidClass' class could also be a plain data type:
> data MonoidDict a = MD {md_empty :: a
> ,md_append :: a -> a -> a}
I have just put the members of the class as fields of a data
type.
Now 'mc_concat' can be written as:
> md_concat :: MonoidDict a -> [a] -> a
> md_concat md [] = md_empty md
> md_concat md (x:xs) = md_append md x (md_concat md xs)
So, while 'mc_concat' has constraints, 'md_concat' is just as
pure polymorphic as 'length' is.
]] Functions that are polymorphic but do not have constraints are
]] not really overloaded because of parametricity, which means that
]] they can't change the way they work based on the specific choices
]] of types you make.
]
] I don't understand the preceding paragraph. Would you mind elaborating.
Take 'length', for example. It has type
length :: [a] -> Int
As it is polymorphic on the list's element type, it can't behave
any differently when I use it on an [Int] from when I use it on a
[Double].
]] > If so, can I say the same sort of thing about constants like 1 and []?
]] > In
]] > particular there is no single value []. Instead [] is a symbol which at
]] > compile time must be compiled to the empty list of some particular type,
]] > e.g., [Int]. There is no such Haskell value as [] :: [a] since [a] (as
]] > type) is not an actual type. I want to say the same thing about 1, i.e.,
]] > that there is no such Haskell value as 1 :: (Num t) => t. When the
]] > symbol 1
]] > appears in a program, the compiler must decide during compilation
]] > whether it
]] > is intended to be 1::Int or 1::Integer or 1::Double, etc.
]]
]] Well, [a] *is* an actual type, a polymorphic one.
]
] Here is the example that raised that issue for me. Let's say I define null'
] as follows.
]
] Â Â null' xs = xs == [ ]
]
] If I don't include a declaration in the file, Haskell (reasonably) concludes
] the following.
]
] Â > :t null'
] Â null' :: (Eq a) => [a] -> Bool
]
] If I write the following at the top level, everything is fine.
] Â > null' [ ]
] Â True
]
] But if I include the following in the file that defines null', I get an
] error message.
]
] Â test = null' [ ]
]
] Â Â Â Â Â Ambiguous type variable `a' in the constraint:
] Â Â Â Â Â Â Â Â Â Â `Eq a' arising from a use of `null'' at null.hs:6:17-24
] Â Â Â Â Â Â Â Â Probable fix: add a type signature that fixes these type
] variable(s)
]
] Why is that? And how can it be fixed? I know I can fix it as follows.
If your function was, for example,
> null'' :: [a] -> Bool
> null'' [] = True
> null'' _ = False
then there would be no error. I assume you already figured that
out. null'' works because it doesn't need to know what kind of
list is. By parametricity, its behaviour can't change based on
its type.
However, null' *can* change its behaviour based on the elements
type! It can use any of the functions in Eq class. For example,
> nullW :: Eq a => [a] -> Bool
> nullW [x,y] = x == y
> nullW _ = False
Note that this functions has the same type as your null', however
its behaviour depends on which kind of 'a' you give to it, as
different 'a's have different (==)s.
Another way of seeing this is by passing the type class as an
argument (I'll omit /=):
> data EqDict a = EQ {eq_equals :: a -> a -> Bool}
>
> -- Takes equality for 'a' and returns equality for '[a]'.
> -- Just like the type class which is
> --
> -- instance Eq a => Eq [a] where ...
> listEqDict :: EqDict a -> EqDict [a]
> listEqDict eq = EQ equals
> where
> equals [] [] = True
> equals (x:xs) (y:ys) = eq_equals eq x y && equals xs ys
> equals _ _ = False
>
> nullDict :: EqDict a -> [a] -> Bool
> nullDict eq xs = eq_equals (listEqDict eq) xs []
So while null'' only takes the list as argument, nullDict also
needs to know which EqDict you want to use. With type classes,
this EqDict is chosen based on 'a's type.
And that's precisely what the error message says. It says that
type 'a' is ambigous because of the 'Eq a' constraint.
] It seemed to me that similar reasoning applied to things like 1. How is the
] following explained?
]
] Â Â Prelude> 111111111111111111111111111111111111111111
] Â Â 111111111111111111111111111111111111111111
] Â Â it :: (Num t) => t
] Â Â Prelude> maxBound :: Int
] Â Â 2147483647
] Â Â it :: Int
] Â Â Prelude> 111111111111111111111111111111111111111111 - (1::Int)
] Â Â -954437178
] Â Â it :: Int
]
] Does it make sense to say that the long string of 1's is really of type (Num
] t) => t?
]
] If so, what does the compiler think it's doing when it processes(?) it as an
] Int so that it can subtract 1 :: Int from it? It didn't treat it as
] maxBound :: Int. And yet it didn't generate an error message.
This is the same thing. The type
(Num t) => t
really is the same as
NumDict t -> t
Hope that helps, =)
--
Felipe.
------------------------------
Message: 2
Date: Fri, 1 Oct 2010 18:08:10 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] fromIntegral
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Friday 01 October 2010 17:08:08, Russ Abbott wrote:
> Thanks, Filipe
>
> I clearly over-stated my case. I'd like to break it into a number of
> different question. Please see below.
>
> On Thu, Sep 30, 2010 at 10:25 PM, Felipe Lessa
<[email protected]>wrote:
> > I'll try to clarify some concepts. Please correct me if I am
> > wrong, and please forgive me if I misunderstood you.
> >
> > On Fri, Oct 1, 2010 at 12:54 AM, Russ Abbott <[email protected]>
> >
> > wrote:
> > > In explaining fromIntegral, I want to say that it is really a
> > > collection
> >
> > of
> >
> > > overloaded functions:
> > >
> > > Integer -> Double
> > > Int -> Float
> > > ...
> > >
> > > When GHC compiles a line of code with fromIntegral it in, it must
> > > decide
> >
> > at
> >
> > > compile time which of these overloaded functions to compile to.
> > > This is
> >
> > in
> >
> > > contrast to saying that fromIngetral is a function of the type
> > > (Integral
> >
> > a,
> >
> > > Num b) => a -> b. In reality there is no (single) function of the
> > > type (Integral a, Num b) => a -> b because (among other things)
> > > every function must map between actual types, but (Integral a, Num
> > > b) => a -> b does not say which actual types are mapped between.
> > >
> > > Is the preceding a reasonable thing to say?
> >
> > First of all, I do think that polymorphic functions are plain ol'
> > functions. For example
> >
> > id :: a -> a
> > id x = x
> >
> > is a function. Moreover, in GHC 'id' has only one
> > representation, taking a thunk and returning a thunk, so even at
> > the machine code level this is only one function.
>
> Agree. I over stated my case. The same can be said for
> length :: [a] -> Int
> It doesn't matter what the type of element in the list is. length runs
> the same way no matter what. So this is pure polymorphism.
>
> > Now, maybe 'fromIntegral' has something more than polymorphism?
> > Well, it has typeclasses. But we can represent those as
> > data types, so we could write
> >
> > fromIntegralD :: Integral a -> Num b -> a -> b
> > fromIntegralD intrDictA numDictB =
> > fromIntegral numDictB . toInteger intrDictA
>
> I'm afraid I don't understand this. Moreover, I couldn't get the
> preceding to load without error.
>
No wonder, Integral and Num are type classes and not datatypes (unless you
have defined such datatypes in scope).
The point is, you can represent type classes as dictionaries, e.g.
data Num a = NumDict
{ plus :: a -> a -> a
, minus :: a -> a -> a
, ...
, fromIntegerD :: Integer -> a
}
data Integral a = IntegralDict
{ quotD :: a -> a -> a
, ...
, toIntegerD a
}
Then a type-class polymorphic function like fromIntegral becomes a function
with some dictionaries as additional arguments.
foo :: (Class1 a, Class2 b) => a -> b
becomes
fooDict :: Class1Dict a -> Class2Dict b -> a -> b
To do that explicitly is of course somewhat cumbersome as one has to always
carry the dictionaries around and one can have more than one dictionary per
type (e.g.
intNum1 :: Num Int
intNum1 = NumDict
{ plus = (+)
, ...
, fromIntegerD = fromInteger
}
intNum2 :: Num Int
intNum2 = NumDict
{ plus = quot
, -- more nonsense
, fromInteger = const 1
}
).
Internally, GHC implements type classes via dictionaries and passes them as
extra arguments to overloaded functions, as you can see by inspecting the
Core output (-ddump-simpl).
> > Better yet, the compiler could write this code for us internally.
And GHC does.
> > Now, using thunks we can get a single machine code for
> > 'fromIntegralD' as well.
But that's not terribly efficient, so with -O, GHC tries to eliminate
dictionaries and use the specialised functions (like
plusInteger :: Integer -> Integer -> Integer).
> >
> > In sum, I think all functions are really just that, functions.
> >
> > --
> >
> > You may call functions that have typeclass constraints
> > "overloaded functions", but they still are functions.
> >
> > Functions that are polymorphic but do not have constraints are
> > not really overloaded because of parametricity, which means that
> > they can't change the way they work based on the specific choices
> > of types you make.
>
> I don't understand the preceding paragraph. Would you mind elaborating.
>
For a function like
length :: [a] -> Int
, because it doesn't know anything about the type a at which it will be
called, it cannot do anything with the contents of the list (well, it could
call seq on them, but it would do that for every type), it can only inspect
the spine of the list.
The code is completely independent of what type of data the pointers to the
contents point to, so `length [True,False]' and `length [()]' can and do
call the exact same machine code.
> > > If so, can I say the same sort of thing about constants like 1 and
> > > []? In particular there is no single value []. Instead [] is a
> > > symbol which at compile time must be compiled to the empty list of
> > > some particular type, e.g., [Int]. There is no such Haskell value
> > > as [] :: [a] since [a] (as type) is not an actual type. I want to
> > > say the same thing about 1, i.e., that there is no such Haskell
> > > value as 1 :: (Num t) => t. When the symbol
> >
> > 1
> >
> > > appears in a program, the compiler must decide during compilation
> > > whether
> >
> > it
> >
> > > is intended to be 1::Int or 1::Integer or 1::Double, etc.
> >
> > Well, [a] *is* an actual type, a polymorphic one.
>
> Here is the example that raised that issue for me. Let's say I define
> null' as follows.
>
> null' xs = xs == [ ]
>
> If I don't include a declaration in the file, Haskell (reasonably)
> concludes the following.
>
> > :t null'
>
> null' :: (Eq a) => [a] -> Bool
>
> If I write the following at the top level,
You seem to mean the ghci prompt here, not the top level of a module.
> everything is fine.
>
> > null' [ ]
>
> True
>
> But if I include the following in the file that defines null', I get an
> error message.
>
> test = null' [ ]
>
> Ambiguous type variable `a' in the constraint:
> `Eq a' arising from a use of `null'' at null.hs:6:17-24
> Probable fix: add a type signature that fixes these type
> variable(s)
>
> Why is that?
null' has an Eq constraint, so to evaluate test, an Eq dictionary is
needed, but there's no way to determine which one should be used.
At a lower level, the type of null' is
null' :: EqDict a -> [a] -> Bool
The (hidden) first argument is missing and GHC doesn't know which one to
pass.
At the ghci-prompt, ghci's extended default rules let it selet the Eq
dictionary of () and all's fine.
In a source file, GHC restricts itself to the default rules specified in
the language report, which state that for defaulting to take place, at
least one of the constraints must be a numeric class. There's none here, so
no defaulting and the type variable of the constraint remains ambiguous.
> And how can it be fixed? I know I can fix it as follows.
>
> test = null' ([ ] :: [Integer])
>
> > :reload
> >
> > test
>
> True
In that situation, I think giving a type signature is the only way¹.
test = null' ([] :: Num a => [a])
also works.
¹ -XExtendedDefaultRules might work too.
>
> That's what suggested to me that [ ] had to be compiled into a concrete
> value.
Try
null'' [] = True
null'' _ = False
test'' = null'' []
No type class constraints, no problems.
>
>
> It seemed to me that similar reasoning applied to things like 1. How is
> the following explained?
>
> Prelude> 111111111111111111111111111111111111111111
> 111111111111111111111111111111111111111111
> it :: (Num t) => t
> Prelude> maxBound :: Int
> 2147483647
> it :: Int
> Prelude> 111111111111111111111111111111111111111111 - (1::Int)
> -954437178
> it :: Int
>
> Does it make sense to say that the long string of 1's is really of type
> (Num t) => t?
Integer literals stand for (fromInteger Integer-value-of-literal), so the
literal itself can have any type belonging to Num. If you force it to have
a particular type, the corresponding fromInteger function is determined and
can be applied if the value is needed.
>
> If so, what does the compiler think it's doing when it processes(?) it
> as an Int so that it can subtract 1 :: Int from it? It didn't treat it
> as maxBound :: Int. And yet it didn't generate an error message.
For efficiency, fromInteger wraps, for a b-bit Integral type, the result of
fromInteger n is n `mod` 2^b.
>
> Thanks
>
> -- Russ
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 28, Issue 3
****************************************
