2010/03/05

流行ってるようなので「ループを使わずに配列の順序を逆にする」

どうしてこの問題が流行ってるんでしょうかね。

でも取り合えず書いてみます。
配列じゃなくてlistですけど。

reverse使えば良いじゃん。
; reverse
(define (my-reverse ls)
  (reverse ls))

(my-reverse '(1 2 3))
; -> (3 2 1)

というわけにもいかないでしょうからfold。
; fold
(define (my-reverse ls)
  (fold cons '() ls))

(my-reverse '(1 2 3 4 5))
;-> (5 4 3 2 1)

foldもなんとなく反則くさいので、letrecで末尾再帰呼び出し。
; recur
(define (my-reverse ls)
  (letrec
      ((rev (lambda (ret l)
              (if (null? l)
                  ret
                  (rev (cons (car l) ret)
                       (cdr l))))))
    (rev '() ls)))

(my-reverse '(a b c))
; -> (c b a)

これだと芸がないので、何かないかなー・・・。ということでY Combinator。
; y combinator
(define (my-reverse ls)
  (((lambda (f)
     (f f))
   (lambda (f)
     (lambda (ret l)
       (if (null? l)
           ret
           ((f f)(cons (car l) ret)(cdr l))))))
   '() ls))

(my-reverse '(a b c))
; -> (c b a)

letrecで良いじゃん・・・ですよね。
芸がない。


プログラミングGauche

追記

なんだ、元ネタはこれか。
再帰、再帰、再帰なSchemeでは、入門書の1章とか2章で出てきそうな問題。
他の問題は流行ってないのかな?
  • 数値Xのフィボナッチ数を計算する。
  • 指定された数値Xが素数であるかどうかを判定する。
  • ループを使わずに配列の順序を逆にする。
  • Fizz Buzz関連英文ブログ
素数のはSICPの1章でやった覚えがある。
計算機プログラムの構造と解釈

0 件のコメント:

コメントを投稿