Hello, I've been studying this fascinating language for a few days so I am pretty new to all this (especially the error messages from the interpreter!)
I wrote this simple function, which purpose is to generate a list of proper divisors of a number:
proper_divisors :: Int -> [Int] proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0]
Saved in a file, when I :load it from GHCI 6.8.2 this is what I get:
[1 of 1] Compiling Main ( pd.hs, interpreted )
pd.hs:2:37: No instance for (RealFrac Int) arising from a use of `floor' at pd.hs:2:37-41 Possible fix: add an instance declaration for (RealFrac Int) In the first argument of `(.)', namely `floor' In the expression: (floor . sqrt) n In a list comprehension: d <- [1 .. (floor . sqrt) n]
pd.hs:2:45: No instance for (Floating Int) arising from a use of `sqrt' at pd.hs:2:45-48 Possible fix: add an instance declaration for (Floating Int) In the second argument of `(.)', namely `sqrt' In the expression: (floor . sqrt) n In a list comprehension: d <- [1 .. (floor . sqrt) n] Failed, modules loaded: none.
I can imagine that perhaps it has something to do with type conflict but I can't go any further. Would someone help?
> proper_divisors :: Int -> [Int] > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0] (snip) > No instance for (RealFrac Int) > arising from a use of `floor' at pd.hs:2:37-41 (snip) > No instance for (Floating Int) > arising from a use of `sqrt' at pd.hs:2:45-48
the (floor . sqrt) can't accept an n :: Int, because they need n's type to be instances of Floating and RealFrac, and Int isn't.
Prelude> :type sqrt sqrt :: (Floating a) => a -> a
... note that the return type is the same as the argument type. From a commonsense point of view, one can see part of the reason for the complaint about Int as being that for things like sqrt (2::Int) you couldn't return an Int answer (at least a correct one!).
Of course,
Prelude> :type mod mod :: (Integral a) => a -> a -> a
mod expects an integral n, and you already declared n to be Int.
How about,
proper_divisors n = [d | d <- [1 .. (floor . sqrt . fromIntegral) n], mod n d == 0]
By the way, though I actually much prefer your convention, upper and lower camel case seem to have established themselves as the Haskell way, so normally one would name your function properDivisors.
> > proper_divisors :: Int -> [Int] > > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0] > (snip) > > No instance for (RealFrac Int) > > arising from a use of `floor' at pd.hs:2:37-41 > (snip) > > No instance for (Floating Int) > > arising from a use of `sqrt' at pd.hs:2:45-48
> the (floor . sqrt) can't accept an n :: Int, because they need n's type > to be instances of Floating and RealFrac, and Int isn't.
> Prelude> :type sqrt > sqrt :: (Floating a) => a -> a
> ... note that the return type is the same as the argument type. From a > commonsense point of view, one can see part of the reason for the > complaint about Int as being that for things like sqrt (2::Int) you > couldn't return an Int answer (at least a correct one!).
> Of course,
> Prelude> :type mod > mod :: (Integral a) => a -> a -> a
> mod expects an integral n, and you already declared n to be Int.
> How about,
> proper_divisors n = [d | d <- [1 .. (floor . sqrt . fromIntegral) n], mod n d == 0]
> By the way, though I actually much prefer your convention, upper and > lower camel case seem to have established themselves as the Haskell way, > so normally one would name your function properDivisors.
> Mark
Hey Mark, Couldn't have asked for a better explanation. Sorry for the "newbie-ness". Grazie! max(ino)
maxino <max.korob...@gmail.com> writes: > proper_divisors :: Int -> [Int] > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0]
Aside from the type error that Mark explained, I think the algorithm isn't right. Suppose n=10 for example. The divisors are 2 and 5, but you'll miss the 5.
On Jun 13, 7:01 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> maxino <max.korob...@gmail.com> writes: > > proper_divisors :: Int -> [Int] > > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0]
> Aside from the type error that Mark explained, I think the algorithm > isn't right. Suppose n=10 for example. The divisors are 2 and 5, > but you'll miss the 5.
Yes, I just realized it :-) Should be simply floor (n / 2) instead of (floor.sqrt) n.
maxino <max.korob...@gmail.com> writes: > Yes, I just realized it :-) > Should be simply floor (n / 2) instead of (floor.sqrt) n.
That's not so good either, you don't really want to divide all the way up to n/2. I'll leave the right answer as an exercise but think of using one of the "fold" functions or recursing on n/d when you find a divisor.
maxino <max.korob...@gmail.com> wrote: > On Jun 13, 7:01 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote: >> maxino <max.korob...@gmail.com> writes: >> > proper_divisors :: Int -> [Int] >> > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0] >> Aside from the type error that Mark explained, I think the algorithm >> isn't right. Suppose n=10 for example. The divisors are 2 and 5, >> but you'll miss the 5. > Yes, I just realized it :-) > Should be simply floor (n / 2) instead of (floor.sqrt) n.
Then you could just use div n 2 or n `div` 2 with infix notation. No need to convert to floating point and back.
> maxino <max.korob...@gmail.com> wrote: > > On Jun 13, 7:01 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote: > >> maxino <max.korob...@gmail.com> writes: > >> > proper_divisors :: Int -> [Int] > >> > proper_divisors n = [d | d <- [1 .. (floor . sqrt) n], mod n d == 0] > >> Aside from the type error that Mark explained, I think the algorithm > >> isn't right. Suppose n=10 for example. The divisors are 2 and 5, > >> but you'll miss the 5. > > Yes, I just realized it :-) > > Should be simply floor (n / 2) instead of (floor.sqrt) n.
> Then you could just use div n 2 or n `div` 2 with infix notation. > No need to convert to floating point and back.
> Project Euler? :-)
> - Dirk
Guilty as charged :-) I did a good number of problems in Python and now I am trying to do them again in Haskell... I am fascinated by this language but for me the learning curve is almost... "vertical" :-)))
> I did a good number of problems in Python and now I am trying to do > them again in Haskell... I am fascinated by this language but for me > the learning curve is almost... "vertical" :-)))
Yeah, that's normal. Was for me, too. Project Euler is especially hard, because not only you have to solve the problem, you have to do it efficiently. So for learning, I guess it makes the curve even steeper.
Once you're comfortable with writing in purely functional style, have a look at imperative array updates and the ST-monad. You're going to need it.
|
