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

Question

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

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

primepowers :: Integer -> [Integer]

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

{р ^ я | 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)

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

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

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

Answer 1

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

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

---

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

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

Answer 2

Хотя вы, вероятно, не можете использовать это для своего назначения, это может быть решено довольно элегантно с использованием пакетов простых чисел и 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 3

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

Answer 4

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

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