Iterating with respect to two variables in haskell

Question

OK, continuing with my solving of the problems on project Euler, I am still beginning to learn Haskell and programming in general.

I need to find the lowest number divisible by the numbers 1:20

So I started with:

divides :: Int -> Int -> Bool
divides d n = rem n d == 0

divise n a  | divides n a == 0 = n : divise n (a+1) 
     | otherwise        = n : divise (n+1) a

What I want to happen is for it to keep moving up for values of n until one magically is evenly divisible by [1..20].
But this doesn't work and now I am stuck as from where to go from here. I assume I need to use: [1..20] for the value of a but I don't know how to implement this.

Answer 1

Well, having recently solved the Euler problem myself, I'm tempted to just post my answer for that, but for now I'll abstain. :)

---

Right now, the flow of your program is a bit chaotic, to sound like a feng-shui person. Basically, you're trying to do one thing: increment n until 1..20 divides n. But really, you should view it as two steps.

Currently, your code is saying: "if a doesn't divide n, increment n. If a does divide n, increment a". But that's not what you want it to say.

You want (I think) to say "increment n, and see if it divides [Edit: with ALL numbers 1..20]. If not, increment n again, and test again, etc." What you want to do, then, is have a sub-test: one that takes a number, and tests it against 1..20, and then returns a result.

Hope this helps! Have fun with the Euler problems!

Edit: I really, really should remember all the words.

Answer 2

Well, as an algorithm, this kinda sucks.

Sorry.

But you're getting misled by the list. I think what you're trying to do is iterate through all the available numbers, until you find one that everything in [1..20] divides. In your implementation above, if a doesn't divide n, you never go back and check b < a for n+1.

Any easy implementation of your algorithm would be:

lcmAll :: [Int] -> Maybe Int
lcmAll nums = find (\n -> all (divides n) nums) [1..]

(using Data.List.find and Data.List.all).

A better algorithm would be to find the lcm's pairwise, using foldl:

lcmAll :: [Int] -> Int
lcmAll = foldl lcmPair 1

lcmPair :: Int -> Int -> Int
lcmPair a b = lcmPair' a b
   where lcmPair' a' b' | a' < b' = lcmPair' (a+a') b'
                        | a' > b' = lcmPair' a' (b + b')
                        | otherwise = a'

Of course, you could use the lcm function from the Prelude instead of lcmPair.

This works because the least common multiple of any set of numbers is the same as the least common multiple of [the least common multiple of two of those numbers] and [the rest of the numbers]

Answer 3

The function 'divise' never stops, it doesn't have a base case. Both branches calls divise, thus they are both recursive. Your also using the function divides as if it would return an int (like rem does), but it returns a Bool.

I see you have already started to divide the problem into parts, this is usually good for understanding and making it easier to read.

Another thing that can help is to write the types of the functions. If your function works but your not sure of its type, try :i myFunction in ghci. Here I've fixed the type error in divides (although other errors remains):

*Main> :i divise
divise :: Int -> Int -> [Int]   -- Defined at divise.hs:4:0-5

Did you want it to return a list?

Leaving you to solve the problem, try to further divide the problem into parts. Here's a naive way to do it:

1. A function that checks if one number is evenly divisible by another. This is your divides function.

2. A function that checks if a number is dividable by all numbers [1..20].

3. A function that tries iterates all numbers and tries them on the function in #2.

Answer 4

Here's my quick, more Haskell-y approach, using your algorithm:

Prelude> let divisibleByUpTo i n = all (\x -> (i `rem` x) == 0) [1..n]
Prelude> take 1 $ filter (\x -> snd x == True) $ map  (\x -> (x, divisibleByUpTo x 4)) [1..]
[(12,True)]

divisibleByUpTo returns a boolean if the number i is divisible by every integer up to and including n, similar to your divides function.

The next line probably looks pretty difficult to a Haskell newcomer, so I'll explain it bit-by-bit:

Starting from the right, we have map (\x -> (x, divisibleByUpTo x 4)) [1..] which says for every number x from 1 upwards, do divisibleByUpTo x 4 and return it in a tuple of (x, divisibleByUpTo x 4). I'm using a tuple so we know which number exactly divides.

Left of that, we have filter (\x -> snd x == True); meaning only return elements where the second item of the tuple is True.

And at the leftmost of the statement, we take 1 because otherwise we'd have an infinite list of results.

This will take quite a long time for a value of 20. Like others said, you need a better algorithm -- consider how for a value of 4, even though our "input" numbers were 1-2-3-4, ultimately the answer was only the product of 3*4. Think about why 1 and 2 were "dropped" from the equation.