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))))))

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:
*** 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?

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))))))

> 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:
> *** 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))))))

>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:
>*** 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?

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:
> > *** 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

 Page 1 of 1 [ 6 post ]

Relevant Pages