Задача понимания Хаскелла - PullRequest
Новая
       32

Задача понимания Хаскелла

0 голосов
/ 08 января 2019

Я пытаюсь изучить Haskell и списки понимания, но не могу найти решение по этому вопросу: 

mylist = [x*y | x <- [1..], y <- [1..]]

После моих испытаний результат примерно такой 

mylist = [1,2,3,4,5,...]

потому что в списках, x принимает значение 1, а затем y меняет значение несколько раз.

Но моя цель - выполнить другое задание, чтобы получить следующий результат: 

mylist = [1,2,2,4,3,3,6.....]

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

Я приведу более конкретный пример.

Я хочу список, в котором будут все номера этой формы: 

num = 2^x * 3^y

x и y должны принимать все значения >= 0.

Мой подход следующий: 

powers = [2^x * 3^y | x <- [0..], y <- [0..]]

Но таким образом я получаю только 3 силы, потому что x постоянно 0.

Я попробовал это 

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

, чтобы объединить разные, но опять же значения 6,12 и т. Д. отсутствуют - результат таков: 

mylist = [1,2,3,4,8,9,16,27,32,64,81...]

1 Ответ

0 голосов
/ 08 января 2019

код, который вы показываете, 

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

эквивалентно 

powers3 = [2^x * 3^y | x <- [0], y <- [0..]]
        = [2^0 * 3^y | y <- [0..]]
        = [3^y | y <- [0..]]
powers2 = [2^x * 3^y | y <- [0], x <- [0..]] 
        = [2^x * 3^0 | x <- [0..]]
        = [2^x | x <- [0..]]

, поэтому вы можете получить только силы 2 и 3 , без смешанных кратных. Таким образом, в потоке гарантированно не будет дубликатов, и nub не потребовалось. И, конечно, он неполон.

Но давайте посмотрим на это под другим углом. В комментариях было предложено создать двумерную сетку из этих чисел: 

mults23_2D = [[2^x * 3^y | y <- [0..]] | x <- [0..]]
{-
   1   3   9   27  81  ...
   2   6  18   54  ...
   4  12  36  108  ...
   8  24  72  ...
  16  ...
  .......     
-}

Теперь мы куда-то добираемся. По крайней мере, теперь ни один из них не пропущен. Нам просто нужно понять, как объединить их в один отсортированный, увеличивающийся поток чисел. Простой concat конечно не подойдет. Нам нужно объединить их по порядку. Хорошо известная функция merge делает это, если аргументы уже упорядочены, увеличивая списки.

Каждая произведенная строка уже в порядке возрастания, но их бесконечно много. Не бойся, foldr может это сделать. Мы определяем 

mults23 = foldr g [] [[2^x * 3^y | y <- [0..]] | x <- [0..]]
  -- foldr g [] [a,b,c,...] == a `g` (b `g` (c `g` (....)))
 where
 g (x:xs) ys =

Вот это немного сложно. Если мы определим g = merge, у нас будет убегающая рекурсия, потому что каждый merge захочет узнать элемент head своего «правого» (второго) потока аргументов.

Чтобы предотвратить это, мы сразу создаем самый левый элемент. 

                x : merge xs ys

И это все.

...