在Haskell、Python和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.

我已经开始将项目Euler站点视为学习Haskell的一种方式，并改进我的Python和Ruby。我认为Haskell和Python版本是可以的，但是我确信Ruby肯定有一种更干净的方式。

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

这不是我如何让一种语言看起来像另一种语言。

This is Problem 1:

这是问题1:

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

问:把所有的自然数加到1000以下，这些自然数是3或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:

好，那么Python可以变成:

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:

出于某种原因，我又看了一遍然后尝试了一种求和方法应该是常数时间。在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:

Ruby可以成为:

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

或

(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.

我假设与map不同，select不会产生“nul”，因此不需要调用compact。好了。

Haskell can also be:

Haskell也可以:

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)

5 个解决方案

#1

For Haskell I like

Haskell的我喜欢

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

或

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.

第一个版本定义了一个小函数s，它将n的所有倍数加到999。如果我们把3的所有倍数和5的倍数都加起来，我们把15倍的倍数都包含在内，因此我们需要一次减去它们。

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.

第二个版本使用了3和5是质数这一事实。如果一个数字包含一个或两个因子3和5，那么这个数字和15的gcd就是3 5或15，所以在每种情况下gcd都大于1。对于没有公因数15的其他数，gcd变成1。这是一个很好的技巧，可以一步测试这两个条件。但是要小心，它不会对任意数起作用，例如，当我们有4和9时，测试gdc x36 > 1不会起作用，因为gcd 6 36 == 6，但既没有mod 6 4 == 0，也没有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.

第三个版本很有趣。循环反复重复一个列表。循环[0,0,1]编码3的“可分性模式”，循环[0,0,0,0,0,0,0,1]对5也是如此。然后我们用zipWith将这两个列表组合在一起，得到[0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1…]现在我们再用zipWith把这个和实际数字相乘，得到[0,0,0,3,0,5,6,0,0,0,0,0,9,0,0,12…]然后我们把它加起来。

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.

知道不同的方法去做同样的事情对其他语言来说可能是浪费，但是对Haskell来说这是必不可少的。您需要发现模式，学习技巧和习语，并进行大量的练习，以便获得有效使用这种语言的心理灵活性。像欧拉项目这样的挑战是一个很好的机会。

#2

Try this for Ruby:

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 }

#3

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.

只是通过http://en.wikipedia.org/wiki/Summation来展示另一种查看相同问题的方式。

#4

I think the following is a better Ruby one:

我认为下面是一个更好的Ruby:

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

#5

Try something like this:

试试这样:

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

#1