<div dir="ltr"><font color="#003333"><font size="2"><font face="verdana,sans-serif">Thanks. I'm still wondering what [ ] refers to. I can load the following file without error.<br><br></font></font></font><div style="margin-left: 40px;">
<font color="#003333"><font size="2"><font face="verdana,sans-serif">null' xs = xs == [ ]</font></font></font><br><br><font color="#003333"><font size="2"><font face="verdana,sans-serif">test = </font></font></font><br>
<font color="#003333"><font size="2"><font face="verdana,sans-serif"> let x = [ ] </font></font></font><br><font color="#003333"><font size="2"><font face="verdana,sans-serif"> in tail [1] == x && </font></font></font><font color="#003333"><font size="2"><font face="verdana,sans-serif">tail ['a'] == x </font></font></font><br>
</div><font color="#003333"><font size="2"><font face="verdana,sans-serif"><br></font></font></font><font color="#003333"><font size="2"><font face="verdana,sans-serif">(I know I can define null' differently. I'm defining it this way so that I can ask this question.)<br>
<br></font></font></font><font color="#003333"><font size="2"><font face="verdana,sans-serif">When I execute test I get True.<br></font></font></font><div style="margin-left: 40px;"><font color="#003333"><font size="2"><font face="verdana,sans-serif"> > test</font></font></font><br>
<font color="#003333"><font size="2"><font face="verdana,sans-serif"> True</font></font></font><br></div><font color="#003333"><font size="2"><font face="verdana,sans-serif"><br></font></font></font><font style="font-family: verdana,sans-serif; color: rgb(0, 51, 51);" color="#003333" size="2">So my question is: what is x after compilation? Is it really a thing of type <br>
(Eq a) => [a] ? <br>If so, how should I think of such a thing being stored so that it can be found equal to both tail [1] and tail ['a']? Furthermore, this seems to show that (==) is not transitive since one can't even compile</font><font style="font-family: verdana,sans-serif; color: rgb(0, 51, 51);" color="#003333" size="2"><br>
tail [1] == tail ['a']</font><font style="color: rgb(0, 51, 51);" size="2"><br style="font-family: verdana,sans-serif;"><span style="font-family: verdana,sans-serif;">much less find them to be equal. </span></font><font style="font-family: verdana,sans-serif; color: rgb(0, 51, 51);" color="#003333" size="2">Yet they are each == to x.<br>
</font><font style="color: rgb(0, 51, 51);" size="2"><br style="font-family: verdana,sans-serif;"></font><div dir="ltr"><font style="color: rgb(0, 51, 51); font-family: verdana,sans-serif;" size="2"><span style="font-family: verdana,sans-serif; color: rgb(0, 51, 51);">-- Russ </span><br>
</font></div><br>
<br><br><div class="gmail_quote">On Fri, Oct 1, 2010 at 9:08 AM, Daniel Fischer <span dir="ltr"><<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div><div></div><div class="h5">On Friday 01 October 2010 17:08:08, Russ Abbott wrote:<br>
> Thanks, Filipe<br>
><br>
> I clearly over-stated my case. I'd like to break it into a number of<br>
> different question. Please see below.<br>
><br>
> On Thu, Sep 30, 2010 at 10:25 PM, Felipe Lessa<br>
<<a href="mailto:felipe.lessa@gmail.com">felipe.lessa@gmail.com</a>>wrote:<br>
> > I'll try to clarify some concepts. Please correct me if I am<br>
> > wrong, and please forgive me if I misunderstood you.<br>
> ><br>
> > On Fri, Oct 1, 2010 at 12:54 AM, Russ Abbott <<a href="mailto:russ.abbott@gmail.com">russ.abbott@gmail.com</a>><br>
> ><br>
> > wrote:<br>
> > > In explaining fromIntegral, I want to say that it is really a<br>
> > > collection<br>
> ><br>
> > of<br>
> ><br>
> > > overloaded functions:<br>
> > ><br>
> > > Integer -> Double<br>
> > > Int -> Float<br>
> > > ...<br>
> > ><br>
> > > When GHC compiles a line of code with fromIntegral it in, it must<br>
> > > decide<br>
> ><br>
> > at<br>
> ><br>
> > > compile time which of these overloaded functions to compile to.<br>
> > > This is<br>
> ><br>
> > in<br>
> ><br>
> > > contrast to saying that fromIngetral is a function of the type<br>
> > > (Integral<br>
> ><br>
> > a,<br>
> ><br>
> > > Num b) => a -> b. In reality there is no (single) function of the<br>
> > > type (Integral a, Num b) => a -> b because (among other things)<br>
> > > every function must map between actual types, but (Integral a, Num<br>
> > > b) => a -> b does not say which actual types are mapped between.<br>
> > ><br>
> > > Is the preceding a reasonable thing to say?<br>
> ><br>
> > First of all, I do think that polymorphic functions are plain ol'<br>
> > functions. For example<br>
> ><br>
> > id :: a -> a<br>
> > id x = x<br>
> ><br>
> > is a function. Moreover, in GHC 'id' has only one<br>
> > representation, taking a thunk and returning a thunk, so even at<br>
> > the machine code level this is only one function.<br>
><br>
> Agree. I over stated my case. The same can be said for<br>
> length :: [a] -> Int<br>
> It doesn't matter what the type of element in the list is. length runs<br>
> the same way no matter what. So this is pure polymorphism.<br>
><br>
> > Now, maybe 'fromIntegral' has something more than polymorphism?<br>
> > Well, it has typeclasses. But we can represent those as<br>
> > data types, so we could write<br>
> ><br>
> > fromIntegralD :: Integral a -> Num b -> a -> b<br>
> > fromIntegralD intrDictA numDictB =<br>
> > fromIntegral numDictB . toInteger intrDictA<br>
><br>
> I'm afraid I don't understand this. Moreover, I couldn't get the<br>
> preceding to load without error.<br>
><br>
<br>
</div></div>No wonder, Integral and Num are type classes and not datatypes (unless you<br>
have defined such datatypes in scope).<br>
<br>
The point is, you can represent type classes as dictionaries, e.g.<br>
<br>
data Num a = NumDict<br>
{ plus :: a -> a -> a<br>
, minus :: a -> a -> a<br>
, ...<br>
, fromIntegerD :: Integer -> a<br>
}<br>
<br>
data Integral a = IntegralDict<br>
{ quotD :: a -> a -> a<br>
, ...<br>
, toIntegerD a<br>
}<br>
<br>
Then a type-class polymorphic function like fromIntegral becomes a function<br>
with some dictionaries as additional arguments.<br>
<br>
foo :: (Class1 a, Class2 b) => a -> b<br>
<br>
becomes<br>
<br>
fooDict :: Class1Dict a -> Class2Dict b -> a -> b<br>
<br>
To do that explicitly is of course somewhat cumbersome as one has to always<br>
carry the dictionaries around and one can have more than one dictionary per<br>
type (e.g.<br>
<br>
intNum1 :: Num Int<br>
intNum1 = NumDict<br>
{ plus = (+)<br>
, ...<br>
, fromIntegerD = fromInteger<br>
}<br>
<br>
intNum2 :: Num Int<br>
intNum2 = NumDict<br>
{ plus = quot<br>
, -- more nonsense<br>
, fromInteger = const 1<br>
}<br>
).<br>
<br>
Internally, GHC implements type classes via dictionaries and passes them as<br>
extra arguments to overloaded functions, as you can see by inspecting the<br>
Core output (-ddump-simpl).<br>
<div class="im"><br>
> > Better yet, the compiler could write this code for us internally.<br>
<br>
</div>And GHC does.<br>
<div class="im"><br>
> > Now, using thunks we can get a single machine code for<br>
> > 'fromIntegralD' as well.<br>
<br>
</div>But that's not terribly efficient, so with -O, GHC tries to eliminate<br>
dictionaries and use the specialised functions (like<br>
plusInteger :: Integer -> Integer -> Integer).<br>
<div class="im"><br>
> ><br>
> > In sum, I think all functions are really just that, functions.<br>
> ><br>
> > --<br>
> ><br>
> > You may call functions that have typeclass constraints<br>
> > "overloaded functions", but they still are functions.<br>
> ><br>
> > Functions that are polymorphic but do not have constraints are<br>
> > not really overloaded because of parametricity, which means that<br>
> > they can't change the way they work based on the specific choices<br>
> > of types you make.<br>
><br>
> I don't understand the preceding paragraph. Would you mind elaborating.<br>
><br>
<br>
</div>For a function like<br>
<br>
length :: [a] -> Int<br>
<br>
, because it doesn't know anything about the type a at which it will be<br>
called, it cannot do anything with the contents of the list (well, it could<br>
call seq on them, but it would do that for every type), it can only inspect<br>
the spine of the list.<br>
<br>
The code is completely independent of what type of data the pointers to the<br>
contents point to, so `length [True,False]' and `length [()]' can and do<br>
call the exact same machine code.<br>
<div class="im"><br>
> > > If so, can I say the same sort of thing about constants like 1 and<br>
> > > []? In particular there is no single value []. Instead [] is a<br>
> > > symbol which at compile time must be compiled to the empty list of<br>
> > > some particular type, e.g., [Int]. There is no such Haskell value<br>
> > > as [] :: [a] since [a] (as type) is not an actual type. I want to<br>
> > > say the same thing about 1, i.e., that there is no such Haskell<br>
> > > value as 1 :: (Num t) => t. When the symbol<br>
> ><br>
> > 1<br>
> ><br>
> > > appears in a program, the compiler must decide during compilation<br>
> > > whether<br>
> ><br>
> > it<br>
> ><br>
> > > is intended to be 1::Int or 1::Integer or 1::Double, etc.<br>
> ><br>
> > Well, [a] *is* an actual type, a polymorphic one.<br>
><br>
> Here is the example that raised that issue for me. Let's say I define<br>
> null' as follows.<br>
><br>
> null' xs = xs == [ ]<br>
><br>
> If I don't include a declaration in the file, Haskell (reasonably)<br>
> concludes the following.<br>
><br>
> > :t null'<br>
><br>
> null' :: (Eq a) => [a] -> Bool<br>
><br>
> If I write the following at the top level,<br>
<br>
</div>You seem to mean the ghci prompt here, not the top level of a module.<br>
<div class="im"><br>
> everything is fine.<br>
><br>
> > null' [ ]<br>
><br>
> True<br>
><br>
> But if I include the following in the file that defines null', I get an<br>
> error message.<br>
><br>
> test = null' [ ]<br>
><br>
> Ambiguous type variable `a' in the constraint:<br>
> `Eq a' arising from a use of `null'' at null.hs:6:17-24<br>
> Probable fix: add a type signature that fixes these type<br>
> variable(s)<br>
><br>
> Why is that?<br>
<br>
</div>null' has an Eq constraint, so to evaluate test, an Eq dictionary is<br>
needed, but there's no way to determine which one should be used.<br>
<br>
At a lower level, the type of null' is<br>
<br>
null' :: EqDict a -> [a] -> Bool<br>
<br>
The (hidden) first argument is missing and GHC doesn't know which one to<br>
pass.<br>
<br>
At the ghci-prompt, ghci's extended default rules let it selet the Eq<br>
dictionary of () and all's fine.<br>
<br>
In a source file, GHC restricts itself to the default rules specified in<br>
the language report, which state that for defaulting to take place, at<br>
least one of the constraints must be a numeric class. There's none here, so<br>
no defaulting and the type variable of the constraint remains ambiguous.<br>
<div class="im"><br>
> And how can it be fixed? I know I can fix it as follows.<br>
><br>
> test = null' ([ ] :: [Integer])<br>
><br>
> > :reload<br>
> ><br>
> > test<br>
><br>
> True<br>
<br>
</div>In that situation, I think giving a type signature is the only way¹.<br>
<br>
test = null' ([] :: Num a => [a])<br>
<br>
also works.<br>
<br>
¹ -XExtendedDefaultRules might work too.<br>
<div class="im">><br>
> That's what suggested to me that [ ] had to be compiled into a concrete<br>
> value.<br>
<br>
</div>Try<br>
<br>
null'' [] = True<br>
null'' _ = False<br>
<br>
test'' = null'' []<br>
<br>
No type class constraints, no problems.<br>
<div class="im"><br>
><br>
><br>
> It seemed to me that similar reasoning applied to things like 1. How is<br>
> the following explained?<br>
><br>
> Prelude> 111111111111111111111111111111111111111111<br>
> 111111111111111111111111111111111111111111<br>
> it :: (Num t) => t<br>
> Prelude> maxBound :: Int<br>
> 2147483647<br>
> it :: Int<br>
> Prelude> 111111111111111111111111111111111111111111 - (1::Int)<br>
> -954437178<br>
> it :: Int<br>
><br>
> Does it make sense to say that the long string of 1's is really of type<br>
> (Num t) => t?<br>
<br>
</div>Integer literals stand for (fromInteger Integer-value-of-literal), so the<br>
literal itself can have any type belonging to Num. If you force it to have<br>
a particular type, the corresponding fromInteger function is determined and<br>
can be applied if the value is needed.<br>
<div class="im"><br>
><br>
> If so, what does the compiler think it's doing when it processes(?) it<br>
> as an Int so that it can subtract 1 :: Int from it? It didn't treat it<br>
> as maxBound :: Int. And yet it didn't generate an error message.<br>
<br>
</div>For efficiency, fromInteger wraps, for a b-bit Integral type, the result of<br>
fromInteger n is n `mod` 2^b.<br>
<br>
><br>
> Thanks<br>
><br>
> -- Russ<br>
<br>
</blockquote></div><br></div>