Эффективные альтернативы квалифицированным интерпретациям списков Haskell

Question

В качестве иллюстрации квалифицированных списков в Haskell учебник Learn You a Haskell служит примером понимания списка, который предлагает общий подход к поиску правильных треугольников с заданным периметром p, выраженный в виде кортежа:

λ> let rightTriangles p = [ (a,b,c) | c <- [1..(quot p 2)], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a + b + c == p] 

Но этот подход становится очень медленно, как p становится большим.

Есть ли вообще более быстрый, но идиоматический способ Haskell для достижения той же цели для больших p?

Answer 1

В комментариях подчеркивается, что то, что вам действительно нужно, является лучшим алгоритмом.

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

let rightTrianglesCubic p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a + b + c == p] 

Во-первых, обратите внимание, как мы пробегаем по всем значениям [1..b], пока не найдете тот, где a + b + c == p. Но единственное значение, где это имеет место в a = p - b - c, так что мы можем пропустить цикл в целом, и сделать это в квадратичный алгоритм:

let rightTrianglesQuadraticA p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], let a = p - b - c, a^2 + b^2 == c^2] 

Там есть небольшая проблема с этим подходом:

λ rightTrianglesCubic 120 
[(30,40,50),(24,45,51),(20,48,52)] 
λ rightTrianglesQuadraticA 120 
[(40,30,50),(30,40,50),(45,24,51),(24,45,51),(48,20,52),(20,48,52),(0,60,60)] 

Мы получаем некоторые дополнительные результаты! Это связано с тем, что мы проигнорировали неявные условия, сделанные a <- [1..b], а именно 1 <= a и a <= b. Поэтому давайте добавим их обратно в

let rightTrianglesQuadraticB p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], let a = p - b - c, a^2 + b^2 == c^2, 1 <= a, a <= b] 

И теперь мы получаем правильный ответ:.

λ rightTrianglesQuadraticB 120 
[(30,40,50),(24,45,51),(20,48,52)] 

Поскольку каждое значение b имеет уникальный a, условие 1 <= a и a <= b могут быть сформулированы как условия на b. 1 <= a - это то же самое, что и 1 <= p - b - c или b <= p - c - 1. a <= b - это то же самое, что и p - b - c <= b или p - c <= 2*b или div (p - c + 1) 2 <= b.

Это позволяет нам сжать границы на петле b <- [1..c]:

let rightTrianglesQuadraticC p = [ (a,b,c) | c <- [1..quot p 2], b <- [max 1 (div (p - c + 1) 2) .. min c (p - c - 1) ], let a = p - b - c, a^2 + b^2 == c^2] 

Мы можем даже термоусадочной границы на c <- [1..quot p 2], отметив, что для того, чтобы a < b < c с a+b+c == p, мы должны иметь c > p/3:

let rightTrianglesQuadraticD p = [ (a,b,c) | c <- [1 + quot p 3..quot p 2], b <- [max 1 (div (p - c + 1) 2) .. min c (p - c - 1) ], let a = p - b - c, a^2 + b^2 == c^2] 

Это касается того, насколько оптимизирован этот конкретный код. Для дальнейшего улучшения производительности нам нужно будет полностью переключить алгоритмы.