Newbie seeks advice 
Author Message
 Newbie seeks advice

Hello,
I have a tried to translate the Scheme program
(From Structure and Interpretations of Computer Programs,
http://www.*-*-*.com/ )

define (fast-expt b n)
          (cond ((= n 0) 1)
                ((even? n) (square (fast-expt b (/ n 2))))
                (else (* b (fast-expt b (- n 1))))))
into Haskell:

fastexp b n
    | n==0 =  1
    | (even n) = ((fastexp b (n/2))^2)
    | otherwise = (b * fastexp b (n-1))

But when i try it, it gives me the error message:
ERROR: Unresolved overloading
*** Type       : (Integral a, Fractional a) => Integer
*** Expression : fastexp 2 10

I guess it is some silly type error, but i found myself not able
to correct it easily. What is wrong here?
Thanks in advance for any reply!



Mon, 19 Jan 2004 05:50:59 GMT  
 Newbie seeks advice

Quote:

> Hello,
> I have a tried to translate the Scheme program
> (From Structure and Interpretations of Computer Programs,
> http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html)

> define (fast-expt b n)
>           (cond ((= n 0) 1)
>                 ((even? n) (square (fast-expt b (/ n 2))))
>                 (else (* b (fast-expt b (- n 1))))))
> into Haskell:

> fastexp b n
>     | n==0 =  1
>     | (even n) = ((fastexp b (n/2))^2)
>     | otherwise = (b * fastexp b (n-1))

> But when i try it, it gives me the error message:
> ERROR: Unresolved overloading
> *** Type       : (Integral a, Fractional a) => Integer
> *** Expression : fastexp 2 10

> I guess it is some silly type error, but i found myself not able
> to correct it easily. What is wrong here?

Your use of "n / 2".  It is compounded by
Haskell's use of type classes and overloading of integral literals.

(/):: a -> a -> a belongs to the type class Fractional a.  When you
use "n / 2", you are saying n is a member of a type that is an instance
of Fractional.

You are also saying that 2 is, but integer literals are read as
(fromInteger <literal>), so can be members of any type that belongs to
the class Integral.

You probably want to write "n `div` 2" instead.

HTH.

(BTW, Haskell already uses a variant of this algorithm internally for the
"^" function; see the definition in the prelude. It uses `quot` instead of
`div` although they should be the same for positive integers)

--
Aaron Denney
-><-



Mon, 19 Jan 2004 07:11:33 GMT  
 Newbie seeks advice

In the second case, use (div n 2) rather than (n/2).
Also, you have a typo in the 1st case.

John
--


Quote:
>Hello,
>I have a tried to translate the Scheme program
>(From Structure and Interpretations of Computer Programs,
>http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html)

>define (fast-expt b n)
>          (cond ((= n 0) 1)
>                ((even? n) (square (fast-expt b (/ n 2))))
>                (else (* b (fast-expt b (- n 1))))))
>into Haskell:

>fastexp b n
>    | n==0 =  1
>    | (even n) = ((fastexp b (n/2))^2)
>    | otherwise = (b * fastexp b (n-1))

>But when i try it, it gives me the error message:
>ERROR: Unresolved overloading
>*** Type       : (Integral a, Fractional a) => Integer
>*** Expression : fastexp 2 10

>I guess it is some silly type error, but i found myself not able
>to correct it easily. What is wrong here?
>Thanks in advance for any reply!



Mon, 19 Jan 2004 07:46:43 GMT  
 Newbie seeks advice

Quote:
> > fastexp b n
> >     | n==0 =  1
> >     | (even n) = ((fastexp b (n/2))^2)
> >     | otherwise = (b * fastexp b (n-1))

Haskell doesn't need as much parentheses as Scheme:

fastexp b n
  | n == 0 = 1
  | even n = fastexp b (div n 2) ^ 2
  | otherwise = b * fastexp b (n - 1)

The div function is used for dividing integers and losing precision on the
way (div 10 3 gives 3).
The operator / is used for dividing without losing (too much) precision.
Therefore, you can only use it on real numbers and fractionals.

Arjan



Mon, 19 Jan 2004 16:32:58 GMT  
 Newbie seeks advice

Quote:


> > Hello,
> > I have a tried to translate the Scheme program
> > (From Structure and Interpretations of Computer Programs,
> > http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html)

> > define (fast-expt b n)
> >           (cond ((= n 0) 1)
> >                 ((even? n) (square (fast-expt b (/ n 2))))
> >                 (else (* b (fast-expt b (- n 1))))))
> > into Haskell:

> > fastexp b n
> >     | n==0 =  1
> >     | (even n) = ((fastexp b (n/2))^2)
> >     | otherwise = (b * fastexp b (n-1))

> > But when i try it, it gives me the error message:
> > ERROR: Unresolved overloading
> > *** Type       : (Integral a, Fractional a) => Integer
> > *** Expression : fastexp 2 10

> > I guess it is some silly type error, but i found myself not able
> > to correct it easily. What is wrong here?

> Your use of "n / 2".  It is compounded by
> Haskell's use of type classes and overloading of integral literals.

> (/):: a -> a -> a belongs to the type class Fractional a.  When you
> use "n / 2", you are saying n is a member of a type that is an instance
> of Fractional.

> You are also saying that 2 is, but integer literals are read as
> (fromInteger <literal>), so can be members of any type that belongs to
> the class Integral.

> You probably want to write "n `div` 2" instead.

> HTH.

> (BTW, Haskell already uses a variant of this algorithm internally for the
> "^" function; see the definition in the prelude. It uses `quot` instead of
> `div` although they should be the same for positive integers)

> --
> Aaron Denney
> -><-

Yes,
Thank You! That helped me much, since i just tried to change the types and
all i did won't work.
so '/' in Scheme and in Haskell means a different thing? did not know that.
Thank you!!


Tue, 20 Jan 2004 00:01:20 GMT  
 Newbie seeks advice

Quote:

> so '/' in Scheme and in Haskell means a different thing? did not know that.

Actually, it only means different things in Scheme. :-)

Dividing integers and dividing floats (or "real numbers", if you want
to be more mathematical, but rather imprecise) are different things.

In Scheme, being dynamically typed and all, / checks the type of the
arguments when called, and subsequently invokes the proper
implementation.  Obviously, this occasionally leads to run time
errors when trying to divide indivisible types.

In Haskell, the types need to be determined at compile time, so we
have no such luxury - we need different functions.  Now, the type
class system makes sure we only need two, one for the Fractional
class - fractions, floats, etc. - where you can do exact division
((/)), and one for the Integral class - e.g. integers of various kinds
- where you usually can't do it exactly (div).

(I suppose you could have just one division, but division of
fractionals is related to functions like recip (i.e. 1/x), so it's
probably a sensible division)

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Tue, 20 Jan 2004 14:38:55 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. seek advice on mac vs 486 for apl

2. Interpreter advice sought.

3. Advice to Companies Seeking Consultants

4. Advice sought...

5. Advice sought on selling Source & Copyright

6. A complaint from Colin James III - advice sought

7. Seeking advice!

8. Seeking advice...

9. New Micros 68HC11 Advice Sought

10. Student seeks advice from FORTH community

11. Clipper for Windows: Advice is sought!

12. Seeking basic networking advice

 

 
Powered by phpBB® Forum Software