`(Hello ,world)

ツッコミ、添削大歓迎です。いろいろ教えてください。

2008-02-20

Burrows-Wheeler Transform

| 23:54

http://golf.shinh.org/p.rb?BWT

Schemeで:

(use srfi-1)

; カリー化
(define (curry f . arg)
        (lambda rest
          (apply f (append arg rest))))

; 文字列の回転
(define (roll-str s n)
        (string-append (string-copy s n)
                       (substring s 0 n)))

; リスト中に要素が現れた場所を返す
(define (index x ls)
        (let ((rest (member x ls)))
          (if rest (- (length ls) (length rest))
            #f)))

; 文字列リストのけつをつないだ文字列を取得
(define (take-tail-string ls)
        (apply string-append
               (map (lambda (s) (string-copy s (- (string-length s) 1)))
                    ls)))

; Burrows-Wheeler Transform
(define (bwt s)
        (let ((mtx (sort (map (curry roll-str s) (iota (string-length s))))))
          (cons (index s mtx)
                (take-tail-string mtx))))

(port-for-each
 (lambda (s)
   (let ((res (bwt s)))
     (format #t "~d ~A~%" (car res) (cdr res))))
 (lambda () (read-line (current-input-port) #t)))

Scheme を Haskell化する計画

| 23:13

カリー

関数引数の一部を与えて、残りの引数を受け取ると結果を返すクロージャを返す関数を作る。Common Lisp だと funcall があれなので Schemeで。

; カリー化した関数を返す
(define (curry f . arg)
        (lambda rest
          (apply f (append arg rest))))

テスト:

; 2の3乗
(expt 2 3)
  ; => 8

; べき乗関数のカリー化
(curry expt 2)
  ; => #<closure (curry curry)>

; リストの要素を2のn乗する: Haskellだと map ((**) 2) [1 .. 5]
(map (curry expt 2) '(1 2 3 4 5)) 
  ; => (2 4 8 16 32)
flip

関数への引数の順番を反転する

(define (flip f x y)
        (f y x))

テスト:

; リストの要素を2乗する: Haskellだと map (flip (**) 2) [1 .. 5]
(map (curry flip expt 2) '(1 2 3 4 5)) 
  ; => (1 4 9 16 25)
関数合成

関数合成は組み込みライブラリcompose が用意されている。

テスト:行数を数える

; 文字列の行数を数える関数: Haskellだと count_line = length . lines 
(define count-line 
        (compose length (curry flip string-split "\n"))) 
(count-line "this\nis\na\npen.") 
  ; => 4 
  • カリー化があると、いちいち (lambda (...) ...) と書かなくていいので、ちょっと楽になりますね。その分 (curry ...) と書かないといけませんが、引数の受け渡しを書かなくていい分だけ見た目すっきりします。
  • まあ Scheme の流儀ではないし、無理してる感はいなめませんが…。
  • no title
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20080220