функция безлимитного списка

Question

список понимания haskell

 paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]]

a = делитель 3 b = квадрат

Элементы должны быть построены в справедливом порядке.

тест> elem (9,9801) должно быть True

моя ошибка

Main> elem (9, 9801) test

ERROR - Сборщик мусора не может восстановить достаточно места

Какя могу реализовать это с помощью диагонального аргумента Кантора?

thx

Answer 1

Не совсем уверен, что ваша цель здесь, но вот причина, почему ваш код взрывается.

Prelude> let paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]]
Prelude> take 10 paar
[(3,1),(3,4),(3,9),(3,16),(3,25),(3,36),(3,49),(3,64),(3,81),(3,100)]

Обратите внимание, что вы генерируете все пары (3, ?) раньше других. Функция elem работает путем линейного поиска в этом списке с самого начала. Поскольку существует бесконечное количество (3, ?) пар, вы никогда не достигнете (9, ?) пар.

Кроме того, ваш код, вероятно, где-то удерживается на paar, предотвращая его сборку мусора. Это приводит к тому, что elem (9, 9801) paar занимает не только бесконечное время, но и бесконечное пространство, что приводит к краху, который вы описали.

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

elemPaar :: (Integer, Integer) -> Bool
elemPaar (a, b) = mod a 3 == 0 && isSquare b
    where isSquare = ...

Или, в качестве альтернативы, определите другую стратегию поиска, чем прямой линейный поиск по бесконечному списку.

Answer 2

Вот альтернативный порядок того же списка (по предложению Хаммара):

-- the integer points along the diagonals of slope -1 on the cartesian plane,
-- organized by x-intercept
-- diagonals = [ (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...
diagonals = [ (n-i, i)  | n <- [0..], i <- [0..n] ]

-- the multiples of three paired with the squares
paar = [ (3*x, y^2) | (x,y) <- diagonals ]

и в действии:

ghci> take 10 diagonals
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]
ghci> take 10 paar
[(0,0),(3,0),(0,1),(6,0),(3,1),(0,4),(9,0),(6,1),(3,4),(0,9)]
ghci> elem (9, 9801) paar
True

Используя диагональный путь, чтобы пройти через все возможныезначения, мы гарантируем, что мы достигаем каждой конечной точки за конечное время (хотя некоторые точки все еще находятся за пределами памяти).

Как указывает Хаммар в своем комментарии, этого недостаточно, так каквсе еще потребуется бесконечное количество времени, чтобы получить False ответ.

Однако у нас есть порядок элементов paar, а именно (3*a,b^2) предшествует (3*c,d^2) при a + b < c + d.Таким образом, чтобы определить, находится ли данная пара (x,y) в paar, нам нужно только проверить пары (p,q), в то время как p/3 + sqrt q <= x/3 + sqrt y.

Чтобы избежать использования Floating чисел, мы можем использовать немного более свободныйусловие, что p <= x || q <= y.Конечно, p > x && q > y подразумевает p/3 + sqrt q > x/3 + sqrt y, так что это будет включать любые возможные решения, и оно гарантированно прекратит работу.

Так что мы можем встроить эту проверку в

-- check only a finite number of elements so we can get a False result as well
isElem (p, q) = elem (p,q) $ takeWhile (\(a,b) -> a <= p || b <= q) paar

И использовать ее:

ghci> isElem (9,9801)
True
ghci> isElem (9,9802)
False
ghci> isElem (10,9801)
False