CODEWITHSUNDEEP
pythonrubyhaskelllist-comprehension
beoliver
beoliver

Reputation: 5759

List comprehension in Haskell, Python and Ruby

I have started looking at the project Euler site as a way to learn Haskell, and improve my Python and Ruby. I think the Haskell and Python versions are ok, but I'm sure there must be a cleaner way for Ruby.

This is not about how can I make one language look like another one.

This is Problem 1:

Q: Add all the natural numbers below one thousand that are multiples of 3 or 5.

Haskell:

sum [ x | x <- [1..999], mod x 3 == 0 || mod x 5 == 0 ]

Python:

sum ( [ x for x in range(1,1000) if x % 3 == 0 or x % 5 == 0 ] )

Ruby:

(1..999) . map {|x| x if x % 3 == 0 || x % 5 == 0 } . compact . inject(:+)

They all give the same answer.

OK, so Python can become:

sum ( x for x in range(1,1000) if x % 3 == 0 or x % 5 == 0 )

it is now a generator (a good thing as we are not storing the list)

but even more fun is:

sum( set(range(0,1000,3)) | set(range(0,1000,5)) )

For some reason I was looking at this again and tried a summation approach which should be constant time. In Python 3:

def step_sum(mn,mx,step):
    amax = mx - (mx - mn) % step
    return (mn + amax) * ((1 + ((amax - mn) / step)) / 2)

step_sum(3,999,3) + step_sum(5,999,5) - step_sum(15,999,15)

Ruby can become:

(1..999) . select {|x| x % 3 == 0 || x % 5 == 0} . inject(:+)

or

(1..999) . select {|x| x % 3 == 0 or x % 5 == 0} . reduce(:+)

I am presuming as unlike map, select doesn't produce 'nul' and therefore there is no need to call compact. nice.

Haskell can also be:

let ƒ n = sum [0,n..999] in ƒ 3 + ƒ 5 - ƒ 15

or to be clearer:

let ƒ n = sum [ 0 , n .. 999 ] in ƒ 3 + ƒ 5 - ƒ (lcm 3 5)

as a function that lets us provide the two numbers ourselves:

ƒ :: (Integral a) => a -> a -> a
ƒ x y = let ƒ n = sum [0,n..999] in ƒ x + ƒ y - ƒ (lcm x y)

Upvotes: 14

Views: 3710

Answers (5)

Landei
Landei

Reputation: 54574

For Haskell I like

let s n = sum [0,n..999] in s 3 + s 5 - s 15

or

sum $ filter ((>1).(gcd 15)) [0..999]

For fun the Rube-Goldberg version:

import Data.Bits

sum $ zipWith (*) [1..999] $ zipWith (.|.) (cycle [0,0,1]) (cycle [0,0,0,0,1])

Okay, explanation time.

The first version defines a little function s that sums up all multiples of n up to 999. If we sum all multiples of 3 and all multiples of 5, we included all multiples of 15 twice (once in every list), hence we need to subtract them one time.

The second version uses the fact that 3 and 5 are primes. If a number contains one or both of the factors 3 and 5, the gcd of this number and 15 will be 3, 5 or 15, so in every case the gcd will be bigger than one. For other numbers without a common factor with 15 the gcd becomes 1. This is a nice trick to test both conditions in one step. But be careful, it won't work for arbitrary numbers, e.g. when we had 4 and 9, the test gdc x 36 > 1 won't work, as gcd 6 36 == 6, but neither mod 6 4 == 0 nor mod 6 9 == 0.

The third version is quite funny. cycle repeats a list over and over. cycle [0,0,1] codes the "divisibility pattern" for 3, and cycle [0,0,0,0,1] does the same for 5. Then we "or" both lists together using zipWith, which gives us [0,0,1,0,1,1,0,0,1,1,0,1...]. Now we use zipWith again to multiply this with the actual numbers, resulting in [0,0,3,0,5,6,0,0,9,10,0,12...]. Then we just add it up.

Knowing different ways to do the same thing might be wasteful for other languages, but for Haskell it is essential. You need to spot patterns, pick up tricks and idioms, and play around a lot in order to gain the mental flexibility to use this language effectively. Challenges like the project Euler problems are a good opportunity to do so.

Upvotes: 8

pcalcao
pcalcao

Reputation: 15975

Not a list comprehension, I know, but to solve that I would use:

3*((999/3)**2+999/3)/2+5*((999/5)**2+999/5)/2-15*((999/15)**2+999/15)/2

Faster then any list comprehension one might come up with, and works in any language ;)

Only posting to show another way of looking at the same problem using http://en.wikipedia.org/wiki/Summation.

Upvotes: 2

jtbandes
jtbandes

Reputation: 118671

Try this for Ruby:

(1..999).select {|x| x % 3 == 0 or x % 5 == 0}.reduce(:+)

Or a little different approach:

(1..999).reduce(0) {|m, x| (x % 3 == 0 or x % 5 == 0) ? m+x : m }

Upvotes: 4

Jwosty
Jwosty

Reputation: 3634

Try something like this:

(1...1000).inject(0) do |sum, i|
  if (i % 3 == 0) or (i % 5 == 0)
    sum + i
  else
    sum
  end

Upvotes: 1

Mark Thomas
Mark Thomas

Reputation: 37507

I think the following is a better Ruby one:

(1..999).select{|x| x % 3 == 0 || x % 5 == 0}.reduce(:+)

Upvotes: 1

Related Questions