Как сохранить неуменьшенную форму соотношения в Хаскеле

Question

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

mergeArrays :: [Int] -> [Int] -> [Ratio Int]
mergeArrays [] [] = []
mergeArrays (x:xs) (y:ys) = [x%y] ++ mergeArrays xs ys

rationalSum :: Int -> [Ratio Int]
rationalSum 0 = []
rationalSum 1 = []
rationalSum n = mergeArrays [1..(n-1)] [(n-1), (n-2)..1]

sumLowestBool :: Ratio Int -> Bool
sumLowestBool x
  |(gcd (extractNumerator (x)) (extractDenominator (x)) == 1) = True
  |otherwise = False

rationalSumLowest :: Int -> [Ratio Int]
rationalSumLowest 0 = []
rationalSumLowest 1 = []
rationalSumLowest n = [i | i <- rationalSum (n), sumLowestBool i == True]

Он должен работать так:

*Main> rationalSumLowest 5
[1 % 4,2 % 3,3 % 2,4 % 1]
*Main> rationalSumLowest 8
[1 % 7,3 % 5,5 % 3,7 % 1]
*Main> rationalSumLowest 12
[1 % 11,5 % 7,7 % 5,11 % 1]

С rationalSum, работающим так:

*Main> rationalSum 5
[1 % 4,2 % 3,3 % 2,4 % 1]
*Main> rationalSum 8
[1 % 7,1 % 3,3 % 5,1 % 1,5 % 3,3 % 1,7 % 1]
*Main> rationalSum 1
[]

Моя rationalSum функция работает нормально, а моя rationalSumLowest - нет.Возвращает тот же список, что и функция rationalSum.Я знаю, что это потому, что в Haskell все соотношения автоматически уменьшаются, и поэтому мой sumLowestBool вернул бы True для всех записей в списке.

Мой вопрос: есть ли способ сохранить неуменьшенная форма отношения в исходном списке, чтобы моя sumLowestBool функция могла работать правильно?

Answer 1

Поскольку коэффициенты уменьшены, проверка того, что gcd равен 1, аналогична проверке того, что числитель не изменился.

import Data.Ratio

rationalSumLowest :: Integer -> [Rational]
rationalSumLowest n =
    [ v
    | i <- [1 .. n-1]
    , let v = i % (n-i)
    , numerator v == i
    ]