Schemeでクイックソート
先日の納会でソートの話が少し出たのでクイックソートを書いてみました.
書きやすいのでGaucheで.
まず普通に書いてみます.
(define (quick lst) (if (null? lst) '() (let ((first (car lst))) (append (quick (filter (lambda (x) (< x first)) lst)) (filter (lambda (x) (= x first)) lst) (quick (filter (lambda (x) (< first x)) lst))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1)) (1 2 3 3 4 7 7 7 8 9 92)
普通ですね.
ただfilterで何度もリストの中身を舐めているのが嫌です.
ここでstreamを使ってみます.
(use util.stream) (define (quick lst) (stream->list (let recur ((s (list->stream lst))) (if (stream-null? s) stream-null (let ((first (stream-car s))) (stream-append (recur (stream-filter (lambda (x) (< x first)) s)) (stream-filter (lambda (x) (= x first)) s) (recur (stream-filter (lambda (x) (< first x)) s))))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1)) (1 2 3 3 4 7 7 7 8 9 92)
リストからストリームへの変換とストリームからリストへの変換が入っているので
効率的になったのかどうか怪しいですが一応期待通りに動いていますね.
どうするのが正解なんでしょう?
once-onlyマクロの解読
実践Common Lisp p100にあるonce-onlyマクロの解読に挑戦.
- 作者: Peter Seibel,佐野匡俊,水丸淳,園城雅之,金子祐介
- 出版社/メーカー: オーム社
- 発売日: 2008/07/26
- メディア: 単行本(ソフトカバー)
- 購入: 8人 クリック: 192回
- この商品を含むブログ (69件) を見る
マクロのコードは以下のとおり.
(defmacro onece-only ((&rest names) &body body) (let ((gensyms (loop for n in names collect (gensym)))) `(let (,@ (loop for g in gensyms collect `(,g (gensym)))) `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n))) ,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g))) ,@body)))))
一行ずつ解読していく
まずは
(let ((gensyms (loop for n in names collect (gensym))))
の部分から.
バッククォートがないので何がgensymsに束縛されるかをREPLで確かめる.
CL-USER> (let ((gensyms (loop for n in '(a b c) collect (gensym)))) gensyms) (#:G884 #:G885 #:G886)
namesの数と同じだけのユニークなシンボルを作成している.
次の行は
`(let (,@ (loop for g in gensyms collect `(,g (gensym))))
gensymsは一行目の処理でユニークなシンボルのリストになっている.
gensymsのそれぞれの要素と(gensym)をペアにしていく.
ここまでを実行してみる.
CL-USER> (let ((gensyms (loop for n in '(a b c) collect (gensym)))) `(let (,@ (loop for g in gensyms collect `(,g (gensym)))))) (LET ((#:G887 (GENSYM)) (#:G888 (GENSYM)) (#:G889 (GENSYM))) )
三行目.
`(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n)))
とうとう`,が二重に.
1つずつ見ていく.
二行目の`(let の式の中で `(letとなっているのでここは出力後の形が`(letとなってほしいはず.
,,@となっているのは二行目のバッククォート,三行目頭のバッククォートと二回バッククォートされているので
二度展開しなといloopが展開されない.
これでloop内は展開されるようになった.
次は``(,,g ,,n).二重にバッククォートするのは先ほどと同じように`(foo bar) という形のリストにしたいから.
(,,g ,,n)になっているのはloopでgensymsの要素をgに,namesの要素をnに対応付けているから.
`(,gensymsの要素 ,nameの要素)という形に変換しようとしている.
ここまでを展開するとこうなる
CL-USER> (let ((names '(a b c))) (let ((gensyms (loop for n in names collect (gensym)))) `(let (,@(loop for g in gensyms collect `(,g (gensym)))) `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n))) )))) (LET ((#:G937 (GENSYM)) (#:G938 (GENSYM)) (#:G939 (GENSYM))) `(LET (,`(,#:G937 ,A) ,`(,#:G938 ,B) ,`(,#:G939 ,C)) ))
コンパイル時には新たに(gensym)で作られたユニークなシンボルにnamesの値が束縛されるようになる.
最後に4行目.
,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g)))
二行目と三行目でバッククォートされてるので,先頭のカンマは展開されず(let ...という形になる.
,@の部分は既に先頭で一度カンマがあった後なのでそのまま展開出来る.
`(,n ,g)の部分で実際にAにAの値を束縛するという部分を作る.
なのでここではバッククォートが一つ.
ここのgには3行目で値に束縛したユニークなシンボルが入る.
実際に展開する.
最後なのですべて展開するとこうなる.
CL-USER> (let ((names '(a b c)) (body '(body))) (let ((gensyms (loop for n in names collect (gensym)))) `(let (,@(loop for g in gensyms collect `(,g (gensym)))) `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n))) ,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g))) ,@body))))) (LET ((#:G934 (GENSYM)) (#:G935 (GENSYM)) (#:G936 (GENSYM))) `(LET (,`(,#:G934 ,A) ,`(,#:G935 ,B) ,`(,#:G936 ,C)) ,(LET ((A #:G934) (B #:G935) (C #:G936)) BODY)))
まとめ
まずnamesと同じ数だけ(gensym)でユニークなシンボルを作り,それをgensymsというリストにする.
gensymsの各要素を新たに(gensym)に束縛するlet式を作る.
この(gensym)はonce-onlyを使うマクロの展開時に新しくユニークなシンボルを作る.
gensymsの各要素を評価すると新しく作られるユニークなシンボルを返すようになる.
このユニークなシンボルにnamesの各値を束縛するようにする.
それが本体の三行目に当たる.
四行目ではnamesのシンボルにgensymsの各要素を対応付ける.
gensymsの各要素は新たに作られたユニークなシンボルに束縛され,そのユニークなシンボルはnameの値に束縛される.
以上で終わり.
高階マクロで名前の衝突を回避して,評価順序を保つのはこんなに大変なんですね.
shibuya.lispで発表しました
ゆるわな感じです.
Lisp Meet Up presented by Shibuya.lisp #38 - connpass
反省点は聞いてる人のほうを向いて喋れなかったことですね. 自分のPCのモニタばかり見てました. 次どこかで発表するときはそこを改善したいですね. 後もっとましなスライドを作れるようになりたい.
- 作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一
- 出版社/メーカー: 翔泳社
- 発売日: 2014/05/17
- メディア: 大型本
- この商品を含むブログ (2件) を見る
Emacsのhtmlizeを使ってコードのシンタックスハイライトを保ったままKeynoteにコピペ
Rubyで言語処理100本ノック 00-04
Rubyの練習のために始めました.
4章からは難しそうなので3章まで頑張りたい.でも飽きたらやめるかも.
コードを書く基礎が足りない気がするのでもっと書かないと.
始めるにあって,とりあえずRuby 2.2.3のStringクラスは一通り目を通してきました.
全体的に末尾再帰でなんとかしようとしてます.
Rubyは末尾再帰の最適化がないって聞いたんですがどうなんですかね?
Rubyっぽい書き方がわからないので,Rubocop先生に出来るだけ怒られないように書いてます.
00
# 00 文字列を受け取り,末尾から順に表示する class String def my_reverse size = length result = '' while size > 0 size -= 1 result << self[size] end result end # Like tail call def iter_reverse iter('', length) end private def iter(str, str_len) if str_len > 0 iter(str + self[str_len - 1], str_len - 1) else str end end end 'reverse'.my_reverse # => "esrever" 'a'.my_reverse # => "a" ''.my_reverse # => "" 'reverse'.iter_reverse # => "esrever" 'a'.iter_reverse # => "a" ''.iter_reverse # => ""
01
# 01 文字列の奇数番目だけ取り出した新しい文字列を返す class String def str_odd iter(0, '') end private def iter(index, str) if index < length if index.even? iter(index + 1, str + self[index]) else iter(index + 1, str) end else str end end end 'hello'.str_odd # => "hlo" 'abcde'.str_odd # => "ace" 'パタトクカシーー'.str_odd # => "パトカー"
02
# 02 2つの文字列を受け取り,先頭から交互に混ぜた文字列をつくる def comb_str(str1, str2) iter(str1, str2, '') end def iter(str1, str2, result) if str1.empty? result + str2 elsif str2.empty? result + str1 else iter(str1[1..-1], str2[1..-1], result + str1[0] + str2[0]) end end comb_str('パトカー', 'タクシー') # => "パタトクカシーー"
03
# 03 文字列から数字のリストをつくる class String def pi split.map(&:length) end end "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.".pi # => [3, 1, 4, 1, 6, 9, 2, 7, 5, 3, 5, 8, 9, 7, 10]
04
# 04 文字列を受け取り,単語に分解し,1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字 # それ以外の単語は先頭に2文字を取り出し,取り出した文字列から単語の位置(先頭から何番目の単語か)への連想配列を返す class String def element recur(split, 1, []) end private def helper(str, i) case i when 1, 5, 6, 7, 8, 9, 15, 16, 19 [str[0], i] else [str[0, 2], i] end end def recur(arr, index, result) if arr.empty? result else recur(arr.drop(1), index + 1, result.push(helper(arr[0], index))) end end end "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.".element # => [["H", 1], ["He", 2], ["Li", 3], ["Be", 4], ["B", 5], ["C", 6], ["N", 7], ["O", 8], ["F", 9], ["Ne", 10], ["Na", 11], ["Mi", 12], ["Al", 13], ["Si", 14], ["P", 15], ["S", 16], ["Cl", 17], ["Ar", 18], ["K", 19], ["Ca", 20]]
Stringクラスを一読するのに時間がかかったので今日はこれだけ.
OSX クリーンインストール前の準備
yosemiteからEl Capitanへアップデートする前の準備.
dotfilesの準備
.bashrcや.emacs.dなどインストール後に必要になりそうなものをここに入れてしまいます.
他にも次の環境に必要なものはここに入れてしまいます.
そしてシンボリックリンクを貼るスクリプトをつけておきます.
最強の dotfiles 駆動開発と GitHub で管理する運用方法 - Qiita
ここのスクリプトを少し変更して
#!/bin/bash for f in .??* do filepath="${PWD}/${f}" homefile="${HOME}/${f}" [[ "$f" == ".git" ]] && continue [[ "$f" == ".DS_Store" ]] && continue ln -snf $filepath $homefile done
これを実行すればホームディレクトリにシンボリックリンクが張られます.
Homebrewでインストールしたもののリスト,tap先を保存する
Homebrewで何を入れたかなんて覚えていられませんね.
tapで何を追加したのかも覚えていられません.
なのでファイルに書き出しておきます.
ここから抜き出して一気にインストールなんてことが出来るかは知りません.
クリーンインストール後に調べます.
$ brew tap > ~/dotfiles/brewtaplist $ brew list > ~/dotfiles/brewlist
これで全て書きだされます.
さっきのスクリプトはドットファイル以外のシンボリックリンクは作らないのでこれらのリンクは作られません.
iTerm2の設定のエクスポート
iTerm2の設定も覚えていられませんね.
未来を見てきたらこういうのです.(timemachineで戻ってきました)
なので設定ファイルをエクスポートしておきます.
iTerm2の設定をインポート・エクスポートする方法 - Qiita
ここを見てきてください.
Preferences > General > Prefeences のLoad preferences ... のチェックボックスをクリックしてホームディレクトリのdotfilesにします.
ディレクトリを確認して com.googlecode.iterm2.plist
があればOK.
なければもう一度保存先のディレクトリ名があってるか確認してください.
Karabinerの設定のエクスポート
Karabinerの設定も覚えていられませんね.
快適な環境を維持するためにこれもエクスポートして次の環境に持って行きましょう.
$ /Applications/Karabiner.app/Contents/Library/bin/karabiner export > ~/dotfiles/karabiner.sh
これで大丈夫です.
最後に
以上の作業で作ったdotfilesをgithubに上げるなり,dropboxに上げるなり,外付けHDDに入れるなりして次の環境に送りましょう.
準備完了です.
初めてのgem
キャメルケース,スネークケース,パスカルケースを相互に変換するgemを書きました.
書き方わからずに色々やってたら最初にリリースした分は盛大にバグってました.
とりあえずバグが取れたのでまたgemに.
一応 gem install case_converter
で入れられます.
使い方はこんな感じ
"camel_case".snake_to_camel # => "camelCase" "string ca_mel_case string".snake_to_camel # => "string caMelCase string" "pascal_case".snake_to_camel # => "pascalCase" "string pas_cal_case string".snake_to_camel # => "string pasCalCase string" "snakeCase".camel_to_snake # => "snake_case" "foo snakeCase bar".camel_to_snake # => "foo snake_case bar" "pascalCase".camel_to_pascal # => "PascalCase" "foo pasCalCase bar".camel_to_snake # => "foo pas_cal_case bar" "SnakeCase".pascal_to_snake # => "snake_case" "foo SnaKeCase bar".pascal_to_snake # => "foo sna_ke_case bar" "CamelCase".pascal_to_camel # => "camelCase" "foo CaMelCase bar".pascal_to_camel # => "foo caMelCase bar"
初心者でもこれなら簡単に書ける!