From leavens@cs.iastate.edu Wed Sep 3 23:44:57 2003 Date: Wed, 3 Sep 2003 23:43:12 -0500 (CDT) From: Gary T. Leavens To: cs541s@cs.iastate.edu Subject: Re: Com S 541 feedback: Other Suggestion Hi, On Wed, 3 Sep 2003, WorldWideWeb wrote: > This really belongs in Q&A, but my e-mail account is inaccessible right now: > > Is HUnit installed on popeye? If so, how do we use it in our code? > (Hugs started from the command line as hugs complains about not > being able to open the file HUnit.) If not, I hope you'll consider > installing HUnit where it will be usable from the default hugs > command. > I have put a copy of the HUnit 1.0 files in /home/course/cs541/public/lib/HUnit/ (on the Com S machines). I edited the script "hugs" in the course bin directory, /home/course/cs541/public/bin/, to include the load path for the modules so that if you start hugs using this script you can use the HUnit modules. Enjoy. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From gejun@iastate.edu Thu Sep 4 16:36:19 2003 Date: Thu, 04 Sep 2003 14:31:43 -0500 From: Ge Jun To: leavens@cs.iastate.edu Subject: integrate hugs into emacs? Dear Sir, Can you give me some suggestions about how to do it? If no other things comes up, I will go to your office hours tomorrow :) Thanks, Jun From leavens@cs.iastate.edu Sat Sep 6 17:29:03 2003 Date: Sat, 6 Sep 2003 17:28:41 -0500 (CDT) From: Gary T. Leavens To: David Faden Cc: cs541s@cs.iastate.edu Subject: Re: inferred type not general enough? Hi David, On Sat, 6 Sep 2003, David Faden wrote: > I'm having trouble getting my test code to type check. Hugs is > complaining about the inferred type not being general enough: > > popeye:~/541/hw1> hugs Tests.hs > ... > Reading file "Hw1_1a.hs": > Reading file "Tests.hs": > Type checking > ERROR "Tests.hs":7 - Inferred type is not general enough > *** Expression : problem1Tests > *** Expected type : Eq a => String -> (a -> [a] -> [a]) -> [Test] > *** Inferred type : Eq Char => String -> (Char -> [Char] -> [Char]) -> > [Test] > > The code producing the above error message is pasted below. (Line 7 is > "problem1Tests name delete_all =".) Do you have any suggestions on what > to do to fix the problem? This is a general limitation of the Hindley-Milner type system that Hugs uses. It is that you can't use a formal parameter, such as the delete_all method that is the second argument to problem1Tests in a polymorphic way -- it can only be used with one type within the function if delete_all is a formal. There are two ways to fix this. First, just import the module where delete_all is defined, and don't pass delete_all as a formal, but use that name as a global. This will work because the function delete_all is polymorphic, since it's not a formal paramter. The second is to break problem1Tests into to functions, but that sort of defeats the purpose of writing it. So I recommend the first approach. > ----- > > Tests.hs: > module Tests where > > import HUnit > import Hw1_1a > > problem1Tests :: (Eq a) => String -> (a -> [a] -> [a]) -> [Test] > problem1Tests name delete_all = > (name ~: "delete_all 1 []" ~: [] ~=? (delete_all 1 [])) > : > (name ~: "delete_all 1 [2,3,4]" ~: [2,3,4] ~=? > (delete_all 1 [2,3,4])) : > (name ~: "delete_all 1 [1,2,1,3,1,4,1]" ~: [2,3,4] ~=? > (delete_all 1 [1,2,1,3,1,4,1])) : > (name ~: "delete_all 'a' \"aaaaaaaa\"" ~: [] ~=? > delete_all 'a' "aaaaaaaa") : > [] > > tests = TestList (problem1Tests "1a" Hw1_1a.delete_all) > > main = do runTestTT tests > -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ----------------------------------------------------------------- From leavens@cs.iastate.edu Sun Sep 7 10:55:35 2003 Date: Sun, 7 Sep 2003 10:55:06 -0500 (CDT) From: Gary T. Leavens To: wfengm@cs.iastate.edu Cc: Staff for Com S 541 , S.J.Thompson@kent.ac.uk Subject: Re: Strange Hugs type error (new explanation) Hi Fengming, (Simon, I'm cc'ing you because I think this might be a new error to add to your web page at http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/errors.html. BTW, the http://www.cs.kent.ac.uk/people/staff/sjt/cgi-bin/findError web page gets an internal server error. ) On Sun, 7 Sep 2003 wfengm@cs.iastate.edu wrote: > This is my question as follows. > my original program: > easydiff :: (Real a, Fractional a) => (a -> a) -> a -> a -> a > easydiff f x delta = (f(x+delta) - f(x))/delta > > diffApproxims :: (Real a, Fractional a) => a -> (a -> a) -> a -> [a] > diffApproxims x f delta = [easydiff f x delta] ++ (diffApproxims x f delta/2) > > the ouput: > Prelude> :l "E:\\problem6.txt" > Reading file "E:\problem6.txt": > Type checking > ERROR "E:\problem6.txt":5 - Cannot justify constraints in explicitly typed binding > *** Expression : diffApproxims > *** Type : (Real a, Fractional a) => a -> (a -> a) -> a -> [a] > *** Given context : (Real a, Fractional a) > *** Constraints : Fractional [a] > > I don't know what's wrong with it? Could you please tell me? Well, it's clear that you have a type error in your code. The problem is that you did not parenthesize delta/2. Function application has higher precedence than infix operators, like division, so Haskell parses (diffApproxims x f delta/2) as ((((diffApproxims x) f) delta)/2). That means that the / operator has to be applicable to the result type, [a], of (((diffApproxims x) f) delta). If you fix the parenthesization error, the problem will go away. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ----------------------------------------------- From leavens@cs.iastate.edu Mon Sep 8 23:58:52 2003 Date: Mon, 8 Sep 2003 23:56:00 -0500 (CDT) From: Gary T. Leavens To: David Faden Cc: cs541s@cs.iastate.edu Subject: Re: How do we turn in our homework? Hi David, On Mon, 8 Sep 2003, David Faden wrote: > How do we turn in our homework? Make a printout and bring it to class. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------------------------------- From leavens@cs.iastate.edu Tue Sep 9 00:02:43 2003 Date: Tue, 9 Sep 2003 00:02:12 -0500 (CDT) From: Gary T. Leavens To: David Faden Cc: cs541s@cs.iastate.edu Subject: Re: 1.14121 /= 1.14121? Hi David, On Mon, 8 Sep 2003, David Faden wrote: > The value printed for a Double seems sometimes to differ from its > actual value: > > Hw1_5> squareRoot 1.0 0.0000001 2.0 > 1.41421 :: Double > Hw1_5> 1.41421 > 1.41421 :: Double > Hw1_5> 1.41421 == squareRoot 1.0 0.0000001 2.0 > Bool_False :: Bool > Hw1_5> squareRoot 1.0 0.0000001 2.0 == squareRoot 1.0 0.0000001 2.0 > Bool_True :: Bool > > But, given the following, it seems that Hugs's Doubles provide very > little precision: > > Hw1_5> 1.41421001 == 1.41421 > Bool_True :: Bool > > Given the apparent small amount of precision, it seems odd that 1.41421 > can be not equal to 1.41421. What explains the above? Probably, that the output doesn't print all the bits, but rounds somehow. Also that the decimals giving the expected results are also approximated. > What I'd really like to know is how, given the above, we should write > HUnit test cases for functions returning floating point numbers. One > thing that comes to mind is to just test that the actual value is "very > close" to the expected value. But it seems like this is a common enough > problem that a better solution is already probably built in. Yes, I think HUnit should have a assertEqual method that, for doubles, takes two doubles and an epsilon. > In the mean time, would the following be acceptable as evidence of an > assignment being "error free"? > > Tests> main > ### Failure in: 3:1:5:approximations of 2's square root > expected: [1.0,1.5,1.41667,1.41422,1.41421] > but got: [1.0,1.5,1.41667,1.41422,1.41421] > ### Failure in: 3:2:5:approximations of 64's square root > expected: [1.0,32.5,17.2346,10.474,8.29219] > but got: [1.0,32.5,17.2346,10.474,8.29219] > ### Failure in: 3:5:5:1.41421 ~=? (squareRoot 1.0 0.0000001 2.0) > expected: 1.41421 > but got: 1.41421 > ### Failure in: 3:8:5:3.0e-20 ~=? (relativeSquareRoot 1.0 0.1e-5 > 9.0e-40) > expected: 3.0e-20 > but got: 3.0e-20 > ### Failure in: 4:0:6:diffApproxims of x*x at 20 > expected: [540.0,290.0,165.0,102.5,71.25,55.625,47.8125,43.9062,41.9531] > but got: [540.0,290.0,165.0,102.5,71.25,55.625,47.8125,43.9062,41.9531] > ### Failure in: 4:1:6:diffApproxims of x*x*x at 10 > expected: [13300.0,4300.0,1675.0,831.25,526.562,403.516,349.316,324.048] > but got: [13300.0,4300.0,1675.0,831.25,526.562,403.516,349.316,324.048] > Cases: 42 Tried: 42 Errors: 0 Failures: 6 > :: IO Counts > This is probably fine. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@larch.cs.iastate.edu Thu Sep 11 21:36:24 2003 Date: Thu, 11 Sep 2003 21:35:52 -0500 (CDT) From: Gary T. Leavens To: Kun Liang Subject: Re: COMS 541: foldTree for the trees shown in class Hi Kun Liang, On Thu, 11 Sep 2003, Kun Liang wrote: > I am wondering where can I find some more materials about the Functor, still a little bit confused:) All I can find (apart from my notes) are the following from section 6.3.5 of the haskell report: "6.3.5 The Functor Class class Functor f where fmap :: (a -> b) -> f a -> f b The Functor class is used for types that can be mapped over. Lists, IO, and Maybe are in this class. Instances of Functor should satisfy the following laws: fmap id = id fmap (f . g) = fmap f . fmap g All instances of Functor defined in the Prelude satisfy these laws." This class is not as important as the idea of (higher-order) type classes itself. I was trying to use it to illustrate the idea. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Sep 14 10:22:27 2003 Date: Sun, 14 Sep 2003 10:22:00 -0500 (CDT) From: Gary T. Leavens To: Daniel Patanroi Cc: Staff for Com S 541 Subject: Re: Com S 541 Hi Daniel, Sorry this has taken so long to answer. It got buried in some other e-mails... On Thu, 11 Sep 2003, Daniel Patanroi wrote: > Can you give an 'english' explanation of > > delete_all :: (Eq a) => a -> ([a] -> [a]) > within :: (Ord a, Num a) => a -> [a] -> a > relativeSquareRoot :: (Real a, Fractional a) => a -> a -> a -> a > isFuction :: (Eq, Eb) => (BinaryRel a b) -> Bool I presume you want an explanation of what the types mean. Let's step back and explain what a nonqualified polymorphic type means. For example, > compose :: [(a -> a)] -> (a -> a) means that For all types a, compose takes a list of functions that take arguments of type a and return the same type, and produces a function that takes an argument of type a and produces a result of the same type. In this case, the type a is unbonded or unqualified, that is, every type in Haskell works as an instance. Now if we consider a declaration like: > delete_all :: (Eq a) => a -> ([a] -> [a]) we are faced with a qualified type. The qualification appears to the left of the => in the declaration. In this case we can instantiate the type of delete_all only with types a that satisfy the declarations in the type class Eq. (These say that such type must have an == operator, for example.) So we can read this type as follows: For all types a such that a satisfies the type class Eq, delete_all takes an argument of type a and an argument that is a list of elements of type a, and returns a list of elements of the same type. Note that (Eq a) => a -> ([a] -> [a]) and (Eq a) => a -> [a] -> [a] are the same type. Technically, in Haskell all functions are curried, so every function takes exactly one argument and returns a function that takes the remaining arguments. For example, we can described the following > within :: (Ord a, Num a) => a -> [a] -> a as For all types a such that a satisfies the type classes Ord and Num, within takes an argument of type a and returns a function that takes a list of elements of type a, and returns an element of type a. Similarly, > relativeSquareRoot :: (Real a, Fractional a) => a -> a -> a -> a is read as: For all types a such that a satisfies the type classes Real and Fractional, relativeSquareRoot takes three arguments of type a and returns a result of that type. A corrected last question is that: > isFuction :: (Eq a, Eq b) => (BinaryRel a b) -> Bool For all types a and b such that a satisfies the type class Eq and b satisfies Eq, isFunction takes an arguments of type (BinaryRel a b) and returns a result of type Bool. See also Thompson's book, chapter 12 and the Haskell report. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------------------- From leavens@cs.iastate.edu Sat Sep 20 07:59:48 2003 Date: Sat, 20 Sep 2003 07:57:23 -0500 (CDT) From: Gary T. Leavens To: David Faden Cc: cs541s@cs.iastate.edu Subject: Re: derive? Hi David, On Fri, 19 Sep 2003, David Faden wrote: > In homework 2, when it asks us to derive the type, is it OK simply to > guess the type and prove its correctness? Yes; I recommend that. > Or must we show how we've > derived the type? The derivation and the proof look the same when done, so there's no way to tell. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ---------------------------------------------------- Date: Sun, 21 Sep 2003 21:44:26 -0500 (CDT) From: Gary T. Leavens To: Shane Oldenburger Subject: Re: COMS 541 - type checking Hi Shane, On Sun, 21 Sep 2003, Shane Oldenburger wrote: > Dr. Leavens: > > For problem #7, the infer function, I was wondering how parentheses in types > were supposed to work. For instance, is > ((\x:(o->(o->(o->o))).x) (\y:(o->o).y)) > type o->o, or does not check? That doesn't type check. In general, the type (o->(o->(o->o))) is not equal to the type ((o->o)->(o->o)) Thus ((\x:(o->(o->(o->o))).x) (\y:(o->o).y)) doesn't type check but ((\x:((o->o)->(o->o)).x) (\y:(o->o).y)) should. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------------------------------------- From leavens@larch.cs.iastate.edu Fri Sep 26 18:32:01 2003 Date: Fri, 26 Sep 2003 18:31:44 -0500 (CDT) From: Gary T. Leavens To: Computer Science 541 -- Brett Graves , com_s_541@cs.iastate.edu, Yogy Namara Subject: The eta rule Hi all, I've seen several people on the homework misapply the eta rule. The common mistake is to write: (\y.x) M ==> % wrong! x This is not an eta reduction, but a beta reduction. In fact, there is no eta-redex in the term ((\y.x) M) at all. The eta rule (in the untyped langauge) says (eta) (\x.(e x)) = e, if x not in Fv(e) Note that this is equivalent to saying (without the parentheses: (eta) \x.e x = e, if x not in Fv(e) but that is not at all the same as the beta rule application: (\x.e) x ==> % right! e, This latter is valid as an instance of the beta rule, (beta) ((\x.e) e') = [e'/x]e since if x is not free in e, then [e'/x]e = e. But that has nothing to do with the eta rule. In an eta rule application, you have to have a lambda abstraction with an application in its body, like (\x.plus x), an application by itself can't be an eta-redex. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580