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 (Thomas)
2. Re: fromIntegral (Brent Yorgey)
3. Re: fromIntegral (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Sat, 02 Oct 2010 23:28:59 +0200
From: Thomas <[email protected]>
Subject: Re: [Haskell-beginners] fromIntegral
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi Russ,
you'll likely get more elaborate answers from the real experts here
later on, but since I'm still pretty much a beginner in Haskell my
perspective might be closer to yours and my answers eventually helpful.
> So here are a couple of questions about this example.
>
> What does it mean to say a Num instance for Char. Can you give me an example
> of what that means in a program that will execute. (Preferably the program
> would be as simple as possible.)
Well, "Num" is a typeclass. You can visualize it in GHCi like this:
Prelude> :i Num
class (Eq a, Show a) => Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
Or alternatively have a look at the online docs:
http://hackage.haskell.org/packages/archive/base/3.0.3.1/doc/html/GHC-Num.html
So, instantiating Char for Num would require you to provide
implementations for (+), (*), (-), negate, abs, signum and fromInteger
for Char.
While syntactically possible, I don't see any semantically reasonable
way to do so.
> Is there a way to display a value along with its type during program
> execution? I know about Show; is there something similar like ShowWithType
> (or even ShowType) that (if implemented) will generate a string of a value
> along with its type?
AFAIK in GHCi you can do both, but not simultaneously:
Prelude> let a = 5::Int
Prelude> :t a
a :: Int
Prelude> a
5
> It makes sense to me to say that [ ] is a function that takes a type as an
> argument and generates an value. If that's the case, it also makes sense to
> say that [ ] == [ ] can't be evaluated because there is simply no == for
> functions.
Prelude> :t []
[] :: [a]
So [] is a list type, not a function type.
Prelude> [] == []
True
You can actually compare [] to itself.
So your reasoning does not seem to be valid to me.
At least not on the Haskell source code level (which is what you and
your students work with). Daniel referred to the Core level when saying
that [] was a function there.
My reasoning would go somewhere along the following line:
[] has a polymorphic type, specifically it's an empty list of elements
of any type ([] :: [a], type variable a is not restricted)
So, [] will compare to any empty list, no matter what its elements' type
actually is.
Given:
> let
> xs = []
> ys = 1:xs
> zs = 'a': xs
Then "tail ys == tail zs" will not type check. Neither "tail ys" nor
"tail zs" are polymorphic:
ys :: [Integer]
zs :: [Char]
So the expression "tail ys == tail zs" is invalid - the lhs and rhs must
have the same type but they do not. Nothing will get compared, no tail
will be determined - it will just plainly be rejected from the compiler
(or interpreter).
For comparison: "tail ys == []" is different.
(tail ys) :: [Integer]
[] :: [a]
So we set (well, GHC does this for us) type variable a to Integer and have:
tail ys :: [Integer] == [] :: [Integer]
which is perfectly valid.
> It also makes sense to me to say that == is a collection of more concrete
> functions from which one is selected depending on the type required by the
> expression within which == appears.
See above - [] is not a function.
> Since the required type is known at compile time, it would seem that the
> selection of which == to use could be made at compile time. One shouldn't
> have to carry along a dictionary. (Perhaps someone said that earlier. But
> if so, why the long discussion about Dictionaries?) This seems like a
> standard definition of an overloaded function. So why is there an objection
> to simply saying that == is overloaded and letting it go at that?
(==) :: (Eq a) => a -> a -> Bool
So, yes, (==) feels a little like an overloaded function. It is a
function that accepts any Eq-comparable type.
However, overloading IIRC does not behave identically.
For example function arity is not required to be the same when
overloading methods - and restrictions on types are very different, too.
HTH,
Thomas
------------------------------
Message: 2
Date: Sat, 2 Oct 2010 17:43:56 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] fromIntegral
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
A meta-comment: you seem to be quite hung up on what something like []
actually *is*. While this is a valid question, it is complicated by
the fact that the answer is different depending on the level at which
you consider it. For example, at the surface language level, [] is a
value with the polymorphic type [a]. At the core language level, it
is actually a function which takes a type T as an argument and
produces a value of type [T]. And at the runtime level, it is a
certain bit-pattern which is going to be the same bit-pattern no
matter what the type of the list.
-Brent
On Sat, Oct 02, 2010 at 12:53:11PM -0700, Russ Abbott wrote:
> Daniel, I appreciate your help. Let me tell you where I'm coming from. I
> teach an introductory Haskell course once a year. I'm not a Haskell expert,
> and I tend to forget much of what I knew from one year to the next. Perhaps
> more importantly, one reason for asking these questions is to explain what's
> going on to students who are just seeing Haskell for the first time. We are
> now 2 weeks into the course. If this can't be explained (at least at an
> intuitive level) without displaying lots of intermediate code, it doesn't
> help me.
>
> So here are a couple of questions about this example.
>
> What does it mean to say a Num instance for Char. Can you give me an example
> of what that means in a program that will execute. (Preferably the program
> would be as simple as possible.)
>
> Is there a way to display a value along with its type during program
> execution? I know about Show; is there something similar like ShowWithType
> (or even ShowType) that (if implemented) will generate a string of a value
> along with its type?
>
> It makes sense to me to say that [ ] is a function that takes a type as an
> argument and generates an value. If that's the case, it also makes sense to
> say that [ ] == [ ] can't be evaluated because there is simply no == for
> functions.
>
> It also makes sense to me to say that == is a collection of more concrete
> functions from which one is selected depending on the type required by the
> expression within which == appears.
>
> Since the required type is known at compile time, it would seem that the
> selection of which == to use could be made at compile time. One shouldn't
> have to carry along a dictionary. (Perhaps someone said that earlier. But
> if so, why the long discussion about Dictionaries?) This seems like a
> standard definition of an overloaded function. So why is there an objection
> to simply saying that == is overloaded and letting it go at that?
>
> The answer to why tail ['a'] == [ ] is ok would go something like this. (Is
> this ok?)
>
> a. [ ] is a function that takes a type argument and generates the empty list
> of that type. In particular [ ] is not a primitive value.
>
> b. The type of the lhs is [Char].
>
> c. That selects == :: [Char] -> [Char] -> Bool as the version of == to use
> in the expression.
>
> d. That inserts Char as the Type argument to be passed to the [ ] function
> on the rhs.
>
> e. All the preceding can be done at compile time.
>
> f. When executed, the lhs and rhs will both execute the [ ] function with
> argument Char. They both generate the value [ ] :: [Char]. Those two values
> will be identical and the value of the expression will be True.
>
>
> The reason == at the Equ level appears not to be transitive is that the
> "middle" element is not the same. We can write
>
> let xs = []
> ys = 1:xs
> zs = 'a': xs
> in tail ys == xs && xs == tail zs
>
> But that doesn't imply that tail ys == tail zs. The reason is that in the
> left expression xs is the [ ] function that is passed Char, and in the right
> expression xs is the [ ] function that is passed Int. Since xs does not
> refer to the same thing in both places, transitivity is not violated.
>
> In other words, xs is something like (f Char) on the left and (f Int) on the
> right--where f is the [ ] function. There is no reason to expect that (f
> Char) == (f Int). That expression is not even valid because the left and
> right types are different.
>
> All of the preceding is something I would feel comfortable saying to someone
> who is just 2 weeks into Haskell. There may be a lot of pieces to that
> explanation, but none of them require much prerequisite Haskell knowledge.
>
> -- Russ
>
>
>
> On Sat, Oct 2, 2010 at 7:09 AM, Daniel Fischer
> <[email protected]>wrote:
>
> > On Saturday 02 October 2010 07:24:38, Russ Abbott wrote:
> > > Thanks. I'm still wondering what [ ] refers to.
> >
> > That depends where it appears. Leaving aside []'s existence as a type
> > constructor, it can refer to
> > - an empty list of specific type
> > - an empty list of some constrained type (say, [] :: Num a => [a])
> > - an empty list of arbitrary type.
> >
> > At any point where it is finally used (from main or at the interactive
> > prompt), it will be instantiated at a specific type (at least in GHC).
> >
> > At the Haskell source code level, [] is an expression that can have any
> > type [a].
> >
> > At the Core level (first intermediate representation in GHC's compilation
> > process, still quite similar to Haskell), [] is a function which takes a
> > type ty as argument and produces a value of type [ty].
> >
> > At the assembly level, there are no types anymore, and I wouldn't be
> > surprised if all occurrences of [] compiled down to the same bit of data.
> >
> > > I can load the following file without error.
> > >
> > > null' xs = xs == [ ]
> >
> > Let's see what Core the compiler produces of that:
> >
> > Null.null' :: forall a_adg.
> > (GHC.Classes.Eq a_adg) =>
> > [a_adg] -> GHC.Bool.Bool
> >
> > --Straightforward, except perhaps the name mangling to produce unique
> > names.
> >
> > GblId
> > [Arity 1]
> >
> > --Lives at the top level and takes one argument.
> >
> > Null.null' =
> > \ (@ a_ahp) ($dEq3_aht :: GHC.Classes.Eq a_ahp) ->
> >
> > --Here it gets interesting, at this level, it takes more than one argument,
> > the first two are given here, a type a_ahp, indicated by the @ [read it as
> > "null' at the type a_ahp] and an Eq dictionary for that type.
> >
> > let {
> > ==_ahs :: [a_ahp] -> [a_ahp] -> GHC.Bool.Bool
> >
> > --Now we pull the comparison function to use out of the dictionary and bind
> > it to a local name.
> >
> > LclId
> > []
> > ==_ahs =
> > GHC.Classes.== @ [a_ahp] (GHC.Base.$fEq[] @ a_ahp $dEq3_aht) } in
> >
> > --First, from the Eq dictionary for a_ahp, we pull out the Eq dictionary
> > for the type [a_ahp] and from that we choose the "==" function.
> >
> > \ (xs_adh :: [a_ahp]) -> ==_ahs xs_adh (GHC.Types.[] @ a_ahp)
> >
> > --And now we come to the point what happens when the thing is called.
> > Given an argument xs_adh of type [a_ahp], it applies the comparison
> > function pulled out of the dictionary(ies) to a) that argument and b) []
> > (applied to the type a_ahp, so as the value [] :: [a_ahp]).
> >
> > >
> > > test =
> > > let x = [ ]
> > > in tail [1] == x && tail ['a'] == x
> >
> > And here (caution, it's long and complicated, the core you get with
> > optimisations is much better),
> >
> >
> > $dEq_riE :: GHC.Classes.Eq [GHC.Types.Char]
> > GblId
> > []
> > $dEq_riE = GHC.Base.$fEq[] @ GHC.Types.Char GHC.Base.$fEqChar
> >
> > -- The Eq dictionary for [Char], pulled from the Eq dictionary for Char
> >
> > $dEq1_riG :: GHC.Classes.Eq GHC.Integer.Type.Integer
> > GblId
> > []
> > $dEq1_riG =
> > GHC.Num.$p1Num @ GHC.Integer.Type.Integer GHC.Num.$fNumInteger
> >
> > -- The Eq dictionary for Integer, pulled from the Num dictionary for
> > Integer (Eq is a superclass of Num, so the Num dictionary contains [a
> > reference to] the Eq dictionary)
> >
> > $dEq2_riI :: GHC.Classes.Eq [GHC.Integer.Type.Integer]
> > GblId
> > []
> > $dEq2_riI = GHC.Base.$fEq[] @ GHC.Integer.Type.Integer $dEq1_riG
> >
> > -- The Eq dictionary for [Integer] pulled from the Eq dictionary for
> > Integer
> >
> > Null.test :: GHC.Bool.Bool
> > GblId
> > []
> > Null.test =
> > GHC.Classes.&&
> > (GHC.Classes.==
> > @ [GHC.Integer.Type.Integer]
> > $dEq2_riI
> >
> > -- pull the "==" member from the Eq dictionary for [Integer]
> >
> > (GHC.List.tail
> > @ GHC.Integer.Type.Integer
> >
> > -- apply tail to a list of Integers
> >
> > (GHC.Types.:
> > @ GHC.Integer.Type.Integer
> >
> > -- cons (:) an Integer to a list of Integers
> >
> > (GHC.Integer.smallInteger 1)
> >
> > -- 1
> >
> > (GHC.Types.[] @ GHC.Integer.Type.Integer)))
> >
> > -- empty list of integers, first arg of == complete.
> >
> > (GHC.Types.[] @ GHC.Integer.Type.Integer))
> >
> > -- empty list of Integers, second arg of ==, completes first arg of &&
> >
> > (GHC.Classes.==
> > @ [GHC.Types.Char]
> > $dEq_riE
> >
> > -- pull the == function from the Eq dictionary for [Char]
> >
> > (GHC.List.tail
> > @ GHC.Types.Char
> >
> > -- apply tail to a list of Chars
> >
> > (GHC.Types.:
> > @ GHC.Types.Char
> >
> > -- cons a Char to a list of Chars
> >
> > (GHC.Types.C# 'a')
> >
> > -- 'a'
> >
> > (GHC.Types.[] @ GHC.Types.Char)))
> >
> > -- empty list of Chars, first arg of == complete
> >
> > (GHC.Types.[] @ GHC.Types.Char))
> >
> > -- empty list of Chars, second arg of ==, completes second arg of &&
> >
> >
> > When compiled with optimisations, a lot of the stuff is done at compile
> > time and we get the more concise core
> >
> > Null.test :: GHC.Bool.Bool
> > GblId
> > [Str: DmdType]
> > Null.test =
> > case GHC.Base.$fEq[]_==
> > @ GHC.Integer.Type.Integer
> > GHC.Num.$fEqInteger
> > (GHC.Types.[] @ GHC.Integer.Type.Integer)
> > (GHC.Types.[] @ GHC.Integer.Type.Integer)
> > of _ {
> > GHC.Bool.False -> GHC.Bool.False;
> > GHC.Bool.True ->
> > GHC.Base.eqString
> > (GHC.Types.[] @ GHC.Types.Char) (GHC.Types.[] @ GHC.Types.Char)
> > }
> >
> >
> > The tails are computed at compile time and the relevant dictionaries are no
> > longer looked up in the global instances table but are directly referenced.
> >
> >
> > >
> > > (I know I can define null' differently. I'm defining it this way so that
> > > I can ask this question.)
> > >
> > > When I execute test I get True.
> > > > test
> > > True
> > >
> > > So my question is: what is x after compilation? Is it really a thing of
> > > type
> > >
> > > (Eq a) => [a] ?
> >
> > During compilation, the types at which x is used are determined (for the
> > first list, the overloaded type of 1 :: Num a => a is defaulted to Integer,
> > hence we use [] as an empty list of Integers, the second type is explicit)
> > and the (hidden, not present at source level) type argument is filled in,
> > yielding a value of fixed type. x is used at two different types, so we get
> > two different (at Core level) values.
> >
> > Since x is local to test, x doesn't exist after compilation.
> > It would still exist if it was defined at the module's top level and was
> > exported.
> >
> > > 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']?
> >
> > Perhaps it's best to think of a polymorphic expression as a function taking
> > types (one or more) as arguments and returning a value (of some type
> > determined by its type arguments; that value can still be a function taking
> > type arguments if fewer type arguments are provided than the expression
> > takes).
> >
> > > Furthermore, this seems to
> > > show that (==) is not transitive
> >
> > At any specific type, (==) is (at least it should be) transitive, but you
> > can't compare values of different types.
> >
> > > since one can't even compile
> > > tail [1] == tail ['a']
> >
> > Type error, of course, on the right, you have a value of type [Char], on
> > the left one of Type Num n => [n].
> > If you povide a Num instance for Char, it will complie and work.
> >
> > > much less find them to be equal. Yet they are each == to x.
> >
> > Yes, x can have many types, it's polymorphic.
> >
> > >
> > > -- Russ
> >
> >
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 3
Date: Sun, 3 Oct 2010 00:17:58 +0200
From: Daniel Fischer <[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 Saturday 02 October 2010 21:53:11, Russ Abbott wrote:
> Daniel, I appreciate your help. Â Let me tell you where I'm coming from.
> Â I teach an introductory Haskell course once a year. Â I'm not a Haskell
> expert, and I tend to forget much of what I knew from one year to the
> next. Â Perhaps more importantly, one reason for asking these questions
> is to explain what's going on to students who are just seeing Haskell
> for the first time.
Hrrrmmphhhh.
What's going on behind the scene is complex and implementation dependent
(and I know only a little about how GHC does it).
Perhaps it's best to say that for the time being, they should regard
polymorphic expressions like [] as either one symbol denoting different
values of different types or one value having many types, whichever they
feel more comfortable with.
Both are possible ways of implementing polymorphism and unless they want to
build their own implementation they need not choose how to nail it down.
Coming to grips with the gory details is difficult enough when you have a
good understanding of the higher level.
> We are now 2 weeks into the course. Â If this can't
> be explained (at least at an intuitive level) without displaying lots of
> intermediate code, it doesn't help me.
Well, at that point Core is not a good idea. At an intuitive level, I think
both of the above work.
If you want to know what happens in more detail, you have to look at the
compiler's intermediate representation(s), but to get proficient in using a
language, that's not necessary.
>
> So here are a couple of questions about this example.
>
> What does it mean to say a Num instance for Char.
You write an
instance Num Char where
and you say how the operations should work on Chars.
> Can you give me an
> example of what that means in a program that will execute. Â (Preferably
> the program would be as simple as possible.)
module Main (main) where
-- ord and chr convert between Char and Int
import Data.Char (ord, chr)
-- Number of elements Char has.
-- One could also choose 256 for example.
charMod :: Int
charMod = ord maxBound + 1
-- We lift addition, subtraction and multiplication
-- from Int, should be familiar from C (1-byte char, 256 values)
-- or Java (2-byte char, 65536 values).
-- negate and fromInteger are not quite the same because
-- the number of Chars is not a power of 2.
instance Num Char where
a + b = chr $ (ord a + ord b) `mod` charMod
a - b = chr $ (ord a - ord b) `mod` charMod
a * b = chr $ (ord a * ord b) `mod` charMod
negate a = chr $ negate (ord a) `mod` charMod
abs a = a
signum a = chr $ signum (ord a)
fromInteger n = chr $ fromInteger n `mod` charMod
test :: Bool
test = [97] == "a"
-- aka True
main :: IO ()
main = do
putStrLn
[67,104,97,114,97,99,116,101,114,115,32,97,115,32,110,117
,109,98,101,114,115,44,32,105,116,32,119,111,114,107,115,46]
putStrLn $ map (8600 -) "The quick brown fox jumps over the lazy dog."
-- That only uses fromInteger, so one could leave the other functions
-- undefined here, but you could substitute e.g. '0'+'1' for 97, 't'-'3'
for 67, '\n'*11 for 110, ...
>
> Is there a way to display a value along with its type during program
> execution?
At the ghci prompt (or hugs), you can
query the type of an expression with the :t command (or spell it out,
:type)
Prelude> :type True
True :: Bool
Prelude> :t \f -> [map f [1 .. 4], "now"]
\f -> [map f [1 .. 4], "now"]
:: (Num a, Enum a) => (a -> Char) -> [[Char]]
Prelude> :set +t
Prelude> length "Hey there!"
10
it :: Int
Prelude> []
[]
it :: [a]
Hugs> :set +t
Hugs> length "Hullo"
5 :: Int
Hugs> []
[] :: [a]
Those print only the type of the final value, so if you want to display the
types of intermediate values in a real programme, you need something
different.
> I know about Show; is there something similar like
> ShowWithType (or even ShowType) that (if implemented) will generate a
> string of a value along with its type?
Not really. There is Data.Typeable, though, which contains the typeOf
function:
Prelude Data.Typeable> :t typeOf
typeOf :: (Typeable a) => a -> TypeRep
it is, however, probably of limited use for that purpose, since
Prelude Data.Typeable> typeOf Nothing
<interactive>:1:0:
Ambiguous type variable `a' in the constraint:
`Typeable a' arising from a use of `typeOf' at <interactive>:1:0-13
Probable fix: add a type signature that fixes these type variable(s)
>
> It makes sense to me to say that [ ] is a function that takes a type as
> an argument and generates an value.
Note that that's an implementation detail. That's not at the Haskell level.
> If that's the case, it also makes
> sense to say that [ ] == [ ] can't be evaluated because there is simply
> no == for functions.
No. [] as a function taking a type as argument is an interpretation below
the Haskell level, while (==) operates on the Haskell level.
>
> It also makes sense to me to say that == is a collection of more
> concrete functions from which one is selected depending on the type
> required by the expression within which == appears.
That's one way to look at it. Probably the best for the beginning.
>
> Since the required type is known at compile time, it would seem that the
> selection of which == to use could be made at compile time. One
> shouldn't have to carry along a dictionary. Â (Perhaps someone said that
> earlier. But if so, why the long discussion about Dictionaries?)
Ah, but what if you compile a library? Then you don't know at which types
the function will be used in later programmes, so you have to have some
method of determining which particular (==) to use when you later compile
the programme.
> This seems like a standard definition of an overloaded function.
> So why is there an objection to simply saying that == is overloaded
> and letting it go at that?
I don't know, I wouldn't object to it. As long as you point out that it's
not quite the same overloading as e.g. in Java, you can't have an
overloading of a function with different numbers of arguments in Haskell.
>
> The answer to why tail ['a'] == [ ] is ok would go something like this.
> (Is this ok?)
>
> a. [ ] is a function that takes a type argument and generates the empty
> list of that type. In particular [ ] is not a primitive value.
>
> b. The type of the lhs is [Char].
>
> c. That selects == :: [Char] -> [Char] -> Bool as the version of == to
> use in the expression.
>
> d. That inserts Char as the Type argument to be passed to the [ ]
> function on the rhs.
>
> e. All the preceding can be done at compile time.
>
> f. When executed, the lhs and rhs will both execute the [ ] function
> with argument Char. They both generate the value [ ] :: [Char]. Those
> two values will be identical and the value of the expression will be
> True.
>
If you want to understand what happens at the lower Core level, that's
okay, but it utterly doesn't work at the Haskell level.
At the Haskell level, we have
(==) :: Eq a => a -> a -> Bool
so (==) takes two arguments of the same type, but it can take two Bools,
two Ints, ...
The LHS is [Char], hence the RHS must be too if the expression is to be
well-typed. The RHS, [] has the inferred type [a], i.e. it can be a list of
any type. That type can be unified with [Char] (since it is more general),
the unification is done, fixing the type of [] *in this expression* as
[Char].
>
> All of the preceding is something I would feel comfortable saying to
> someone who is just 2 weeks into Haskell.
I wouldn't.
> There may be a lot of pieces
> to that explanation, but none of them require much prerequisite Haskell
> knowledge.
>
> -- Russ
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 28, Issue 9
****************************************
