Понимание списка в Haskell, Python и Ruby

Question

Я начал смотреть на проект Euler проекта как способ изучения Haskell и улучшения моих Python и Ruby.Я думаю, что версии на Haskell и Python в порядке, но я уверен, что для Ruby должен быть более чистый путь.

Это не о том, как я могу сделать один язык похожим на другой.

Это Задача 1 :

Q: Добавитьвсе натуральные числа меньше тысячи, кратные 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(:+)

Все они дают один и тот же ответ.

---

ОК, поэтому Python может стать:

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

теперь это генератор (хорошо, что мыне хранят список)

, но еще интереснее:

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

По какой-то причине я снова посмотрел на это и попробовал подход суммирования, который должен быть постоянным временем.В 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 может стать:

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

или

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

Я предполагаю, что в отличие от map, select не делаетt 'nul' и, следовательно, нет необходимости звонить compact.nice.

Haskell также может быть:

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

или, чтобы быть более понятным:

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

как функция, которая позволяет нам самим предоставить два числа:

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

Answer 1

Для Haskell мне нравится

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

или

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

Для забавы версия Рубе-Голдберга:

import Data.Bits

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

---

Хорошо, время объяснения,

Первая версия определяет небольшую функцию s, которая суммирует все кратные n до 999. Если мы сложим все кратные 3 и все кратные 5, мы включили все кратные 15 дважды (один раз в каждом списке), следовательно, нам нужно вычесть их один раз.

Во второй версии используется тот факт, что 3 и 5 - простые числа.Если число содержит один или оба из факторов 3 и 5, то значение gcd этого числа и 15 будет равно 3, 5 или 15, поэтому в каждом случае значение gcd будет больше единицы.Для других чисел без общего множителя с 15 gcd становится равным 1. Это хороший прием для проверки обоих условий за один шаг.Но будьте осторожны, он не будет работать для произвольных чисел, например, когда у нас было 4 и 9, тест gdc x 36 > 1 не будет работать, как gcd 6 36 == 6, но ни mod 6 4 == 0, ни mod 6 9 == 0.

Третья версия довольно забавная.cycle повторяет список снова и снова.cycle [0,0,1] кодирует «шаблон делимости» для 3, а cycle [0,0,0,0,1] делает то же самое для 5. Затем мы «или» оба списка вместе, используя zipWith, что дает нам [0,0,1,0,1,1,0,0,1,1,0,1...].Теперь мы снова используем zipWith, чтобы умножить это на фактические числа, в результате чего [0,0,3,0,5,6,0,0,9,10,0,12...].Тогда мы просто добавим это.

Знание различных способов сделать то же самое может быть расточительным для других языков, но для Хаскелла это важно.Вам нужно выявлять закономерности, подбирать трюки и идиомы и много играть, чтобы обрести умственную гибкость для эффективного использования этого языка.Задачи, такие как проект Эйлера, являются хорошей возможностью для этого.

Answer 2

Попробуйте это для Ruby:

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

Или немного другой подход:

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

Answer 3

Не знаю, что такое списочное понимание, но для решения этого я бы использовал:

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

Быстрее, чем любое понимание списка, которое можно придумать, и работает на любом языке;)

Только публикация, чтобы показать другой взгляд на ту же проблему, используя http://en.wikipedia.org/wiki/Summation.

Answer 4

Попробуйте что-то вроде этого:

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

Answer 5

Я думаю, что лучше Ruby:

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