CODEWITHSUNDEEP
haskell
Chris
Chris

Reputation: 1128

What is the Haskell way of solving this?

New to Haskell. I have the following code

fac :: Integer -> [Integer]
fac x = take 1 $ map (x `mod` ) $ reverse [2 .. xs]
    where xs = floor $ sqrt $ fromIntegral x

I want to display the first value from [2 .. xs] such that x mod y == 0. But I can't use filter as that only would work off the output from mod. How do I do this?

Upvotes: 0

Views: 200

Answers (4)

Emil
Emil

Reputation: 2167

You can use filter. Just compose (==0) and (x `mod`) for the first argument of filter.

If you are trying to do Project Euler Problem 3, this will be an incredibly painful way of solving it.

I would suggest the following:

  • Define a function for what you have in the where clause, i.e. isqrt = round . sqrt . fromIntegral

  • Define two functions isPrime and primeList that are mutually recursive for calculating primes and you should use isqrt in the definition of isPrime, although the use of the isqrt isn't actually necessary; I just find it easier to think about for writing this function. (there is a hint below for how to do this step)

  • Using primeList, define a recursive factorize function that outputs a list of primes (or something similar)

  • Factorize the number from the question and return the largest prime in the list

What I have suggested above is usually not that great for calculating very large primes quickly, but it should be adequate for this problem. This paper goes into more detail why: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

For future number theory related PE problems, look into using this library: https://hackage.haskell.org/package/arithmoi-0.2.0.4

Other comments:

Instead of take 1, you should actually use head; it's slightly better.

Also, since the biggest number you will deal with here is 600851475143, you don't actually need the function to have type Integer -> [Integer]. 32-bit Int doesn't do the trick, because maxBound :: Int is 2147483647. maxBound :: Int64, however, is 9223372036854775807, which is much more than you need. So you could just define your function to have type Int64 -> [Int64] (or just Int -> [Int] if the machine is 64-bit already).

Hint:

primeList should be defined as something like primeList = 2 : 3 : filter isPrime [5,7..], but you can decide to be as fancy as you want with this); again, these definitions should be mutually recursive.

Upvotes: 2

Bolo
Bolo

Reputation: 11690

You can use filter. Here's a one-liner (well, two-liner if you count the import):

import Data.Ix (range)
fac x = head . filter ((==) 0 . mod x) . curry range 2 . floor . sqrt . fromIntegral $ x

Upvotes: 1

Lee Duhem
Lee Duhem

Reputation: 15121

I want to display the first value from [2 .. xs] such that x mod y == 0

In this case, you should not use reverse:

fac x = take 1 $ filter (\y -> x `mod` y == 0) $ reverse [2 .. xs]
    where xs = floor $ sqrt $ fromIntegral x

If you want to find out the first value starting from xs such that mod x y == 0, there is also no need to use reverse:

fac x = take 1 $ filter (\y -> x `mod` y == 0) $ [xs, xs-1 .. 2]
    where xs = floor $ sqrt $ fromIntegral x

Upvotes: 2

Karol S
Karol S

Reputation: 9457

fac x = take 1 $ filter (\y -> x `mod` y == 0 ) $ reverse [2 .. xs]
    where xs = floor $ sqrt $ fromIntegral x

or, to be point-free:

fac x = take 1 $ filter ((== 0).(x `mod`)) $ reverse [2 .. xs]
    where xs = floor $ sqrt $ fromIntegral x

Not sure if you want reverse here, or what exactly is your goal.

Upvotes: 1

Related Questions