Feb 07 2012

もうやらないと思ってたけど Project Euler - Problem 48

main = print $ foldl plus 0 $ map self_pow [1 .. 1000]
    where
        plus a b = (a+b) `mod` rr
        self_pow n = pow n n
        pow n 0 = 1
        pow n 1 = n `mod` rr
        pow n m =
            if m`mod`2 == 0 then
                (mod ((pow n (div m 2)) ^ 2) rr)
            else
                (mod (n * ((pow n (div m 2)) ^ 2)) rr)
        rr = 10000000000
(letrec ((rr    10000000000)
         (plus (^ (a b) (modulo (+ a b) rr)))
         (pow  (^ (n m)
                 (cond [(= m 0) 1]
                       [(= m 1) (modulo n rr)]
                       [(zero? (modulo m 2))
                           (mod (expt (pow n (div m 2)) 2) rr)]
                       [else
                           (mod (* (expt (pow n (div m 2)) 2) n) rr)])))
         (self_pow (^n (pow n n))) )
(display (fold plus 0 (map self_pow (iota 1000 1)))) )

最後の行のは、gauche0.9.3から標準になった$マクロによって、

($ display $ fold plus 0 $ map self_pow $ iota 1000 1) )

と書ける.

SRFI-49 というものを知った.S式の代わりにI式で書く. I式のIはインデントのIですか?さすがにこれは極端だよね.

こんなのあっても使わなそうだけど、ノートに手書きで擬似コードを 書くときに、lispで書いちゃうことがあって、そういう時は S式とI式の折衷になっちゃう.

; let多相
(let1 id (^x x) (id id) )

; 謎の多相 (MLなんかでは型推論に失敗する)
((^f (f f)) (^x x))