Haskell, tìm hiểu giải pháp cho euler # 3

Question

Tôi vừa mới học để tìm hiểu về một haskell và đã có thời gian khá tốt. Tôi đã làm việc thông qua một số vấn đề Project Euler để nắm bắt cú pháp và đã xem xét các giải pháp được đăng ở đây http://www.haskell.org/haskellwiki/Euler_problems/1_to_10 như một công cụ học tập. Mặc dù tôi đã tìm thấy bản thân mình không thể quấn quanh đầu tôi các giải pháp gửi cho problem #3:

-- Find the largest prime factor of 317584931803. 

primes = 2 : filter ((==1) . length . primeFactors) [3,5..] 

primeFactors n = factor n primes 
    where 
    factor n (p:ps) 
     | p*p > n  = [n] 
     | n `mod` p == 0 = p : factor (n `div` p) (p:ps) 
     | otherwise  = factor n ps 

problem_3 = last (primeFactors 317584931803) 

tôi không thể tìm ra cho cuộc sống của tôi như thế nào nó hoạt động. primes và primeFactors dường như đang gọi nhau để xây dựng danh sách của riêng họ và cố gắng theo dõi nó làm chua não tôi. Bất kỳ ai biết một bài đăng trên blog tốt về giải pháp này hoặc muốn viết một lời giải thích về nó ở đây?

Answer 1

Điều này thực sự khó hiểu ngay từ cái nhìn đầu tiên. Nhưng nó không có phép thuật nếu bạn không nghĩ "vô cùng". Định nghĩa Haskell chỉ là: cho bạn biết một cái gì đó là, không phải những gì cấp thấp hơn hoạt động máy tính có nghĩa vụ phải thực hiện.

Do đó, danh sách số nguyên tố là danh sách chứa 2 và tất cả các số tự nhiên lẻ lớn hơn 2 chỉ có một yếu tố chính (cụ thể là chính nó).

Danh sách các thừa số nguyên tố cho một số nguyên n, mặt khác, là danh sách các số nguyên tố chia n.

Đảm bảo bạn hiểu các định nghĩa đó trước khi đọc.

Như trừu tượng Haskell có thể, nó vẫn là ngôn ngữ lập trình, vì vậy chúng tôi cần đưa ra một số lời khuyên theo thời gian cách để tính toán điều gì đó. Cụ thể, trong ví dụ trên, chúng tôi làm không kiểm tra tất cả các số nguyên tố để tìm các hệ số nguyên tố của n, bởi vì nó đủ để kiểm tra 2..k trong đó k*k <= n. Điều này cũng đảm bảo rằng chúng tôi chỉ sử dụng phần đó của số nguyên tố đã được tính toán.

Lúc đầu, primes trông như thế này:

2 : filter ((==1) . length . primeFactors) [3,5..] 

Nếu chúng ta đòi hỏi các yếu tố tiếp theo sau khi 2, chúng tôi buộc đánh giá của biểu thức bên phải của ruột kết. Điều này, đến lượt nó, gây lọc để đánh giá vị cho 3. Sau đó nó đi:

primeFactors 3 
    factor 3 (2 : ...) 
    2*2 > 3 
    [3] 
[3] 

Do đó, primeFactors 3 là [3] và chúng tôi không cần phải nhìn xa hơn 2 trong số nguyên tố. (Đây là điểm mấu chốt tại sao điều này làm việc!) Rõ ràng, độ dài của [3] là 1 và

2 : filter ((==1) . length . primeFactors) [3,5..] 

đánh giá để

2 : 3 : filter ((==1) . length . primeFactors) [5, 7..] 

Bây giờ bạn có thể muốn giảm bớt primeFactors 5 cho chính mình.

Answer 2

Đó là sự lười biếng trong hành động :) Danh sách các số nguyên tố bắt đầu rỗng,

primes = 2 : don't_know_yet_let's_see 

và primeFactors tính toán các yếu tố chính của một số bằng cách sử dụng danh sách các số nguyên tố. Nhưng để tìm các yếu tố chính của bất kỳ số nào 'n', chúng ta chỉ cần biết số nguyên tố lên đến sqrt(n). Vì vậy, đuôi của primes,

filter ((== 1) . length . primeFactors) [3, 5 .. ] 

có thể sử dụng những gì đã biết về primes. Để kiểm tra 3, chúng tôi

factor 3 (2:don't_kow_yet_let's_see) 
    | 2*2 > 3 = [3] 
    | don't_care_above_was_true 

Và nếu chúng ta bắt đầu với bất kỳ n, nói n = 35 để giữ cho nó ngắn,

factor 35 (2:??) 
    | 2*2 > 35 -- False, next clause 
    | 35 `mod` 2 == 0 -- False, next clause 
    | otherwise = factor 35 ?? 

Bây giờ chúng ta cần phải tìm hiểu ?? là gì. Chúng tôi đã thấy ở trên rằng filter ing cho phép 3 vượt qua, vì vậy nó 3:???, do đó

factor 35 (3:???) 
    | -- first two guards are False 
    | otherwise = factor 35 ??? 

Bây giờ là những gì ???? Vâng, filter ((== 1) . length . primeFactors) [5, 7 .. ], vì vậy chúng ta hãy xem liệu 5 vượt qua bộ lọc

factor 5 (2:3:???) -- note, we already know the first two elements of primes 
    | 2*2 > 5 -- False 
    | 5 `mod` 2 == 0 -- False 
    | otherwise = factor 5 (3:???) 
        | 3*3 > 5 = [5] 

Vì vậy 5 đèo và chúng tôi biết ba yếu tố đầu tiên của primes. Trong phân tích nhân tử là 35, chúng tôi tiếp tục

factor 35 (5:????) 
    | 5*5 > 35 -- False 
    | 35 `mod` 5 == 0 = 5 : factor (35 `div` 5) (5:????) 
          factor 7 (5:????) 
           | 5*5 > 7 = [7] 

Vì vậy, khi factorising một con số, danh sách các số nguyên tố được xây dựng lên như xa như cần thiết, mỗi nguyên tố mới sẽ được xác định khi nó được yêu cầu, và tại thời điểm đó, tất cả các số nguyên tố cần thiết để xác định nguyên tố tiếp theo đã được tìm thấy.