Haskell - Prime Powers Excercise - Бесконечные слияния

Question

В университете моя задача следующая:

определить следующую функцию:

primepowers :: Integer -> [Integer]

, который вычисляет бесконечный список первых n степеней простых чисел для заданного параметра n, отсортированный asc. То есть, Primepowers n содержит в порядке возрастания элементы

{p ^ i | p простое, 1≤i≤n}.

После работы над этим заданием я зашел в тупик. У меня есть следующие четыре функции:

merge :: Ord t => [t] -> [t] -> [t]
merge [] b = b
merge a [] = a
merge (a:ax) (b:bx)
  | a <= b    = a : merge ax (b:bx)
  | otherwise = b : merge (a:ax) bx

primes :: [Integer] 
primes = sieve [2..]
    where sieve [] = []
          sieve (p:xs) = p : sieve (filter (not . multipleOf p) xs)
            where multipleOf p x = x `mod` p == 0   

powers :: Integer -> Integer -> [Integer] 
powers n num = map (\a -> num ^ a) [1..n]

primepowers :: Integer -> [Integer]
primepowers n = foldr merge [] (map (powers n) primes)

Я думаю, что они работают независимо, как я тестировал с некоторыми примерами входных данных. объединить объединяет два упорядоченных списка в один упорядоченный список простые числа возвращают бесконечный список простых чисел powers рассчитывает n степеней num (то есть num ^ 1, num ^ 2 ... num ^ n)

Я пытаюсь объединить все в простые числа, но функции не оцениваются, ничего не происходит, соответственно, существует некий бесконечный цикл.

Я не заинтересован в оптимизации простых чисел или степеней. Просто я не понимаю, почему это не работает. Или мой подход не хороший, не функциональный, не haskell?

Answer 1

Хотя вы, вероятно, не можете использовать это для своего задания, это может быть решено довольно элегантно с помощью простых чисел и data-ordlist пакетов из Hackage.

import Data.List.Ordered
import Data.Numbers.Primes

primePowers n = mergeAll [[p^k | k <- [1..n]] | p <- primes]

Обратите внимание, что mergeAll может объединять бесконечное количество списков, поскольку предполагает, что заголовки списков упорядочены в дополнение к упорядочиваемым самим спискам. Таким образом, мы можем легко сделать эту работу и для бесконечных сил:

allPrimePowers = mergeAll [[p^k | k <- [1..]] | p <- primes]

Answer 2

Я подозреваю, что проблема: primes - это бесконечный список.Следовательно, map (powers n) primes - это бесконечный список (конечных) списков.Когда вы пытаетесь foldr merge [] все вместе, merge должен оценить заголовок каждого списка ...

Поскольку существует бесконечное количество списков, это бесконечный цикл.*

Я бы предложил перенести структуру, что-то вроде:

primepowers n = foldr merge [] [map (^i) primes | i <- [1..n]]

Answer 3

Причина, по которой ваша программа работает в бесконечном цикле, заключается в том, что вы пытаетесь объединить бесконечное количество списков только с помощью инварианта, согласно которому каждый список сортируется в порядке возрастания.Прежде чем программа сможет вывести «2», она должна знать, что ни один из списков не содержит ничего меньше 2. Это невозможно, поскольку существует бесконечно много списков.

Answer 4

Вам нужна следующая функция:

mergePrio (h : l) r = h : merge l r