とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
人気ジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
<   2015年 08月 ( 13 )   > この月の画像一覧
カメとウサギのアルゴリズム、もしくは・・・
Exercise 3.19について他の人の解答を見てみると、メモリ消費量を抑えつつ線形時間で完了するやり方があるということで、うならされました。

私の考えたdepthを使ったやり方は、リストをカントールの証明のように操作する方法ですが、それだとリスト長(もしくは無限ループの大きさ)に対して2乗オーダで計算時間が増えます。

Barry Allisonさんのコードでは「カメとウサギのアルゴリズム」として紹介されていた方法ですが、最初このコードを読んでも何をやっているのかわかりませんでした。

その方法は、リストの先頭から、1歩ずつ進むポインタ(カメ)と2歩ずつ進むポインタ(ウサギ)を同時に動かしてやるやり方なのですが、直感的にはカメとウサギがどんどん離れていくのでうまくいかないように思えます。

しかし、循環リストの構造としては、L = (a1 ... an b1 ... bm b1 ... bm b1 ...)というような構造をしていて、2つのポインタがanより後ろにあれば、ポインタの距離がmの整数倍の条件で一致するという特徴があります。

なので、カメポインタで必ず1歩は進むようにすればとっととanよりも先に進むことができ、カメポインタとウサギポインタの距離を常に離していくことで距離mを同時に探索することもできるということです。アタマいい〜

以下は私がアレンジした「カメとウサギのアルゴリズム」のコードです。
(optional lineの行はあってもなくてもいいです)

(define (cycle? lst)
  (define (go-downstairs walker runner)
    (cond ((null? runner) #f)
          ((null? (cdr runner)) #f)
          ((eq? runner walker) #t)
          ;((eq? (cdr runner) walker) #t) <- optional line ->
          (#t (go-downstairs (cdr walker) (cddr runner)))))
  (and (not (null? lst))
       (not (null? (cdr lst)))
       (go-downstairs lst (cddr lst))))


[PR]
by tempurature | 2015-08-26 00:59 | scheme
SICP Exercise 3.18, 3.19の解答
Exercise 3.18は循環リストを判別せよという問題、Exercise 3.19はメモリを一定以上消費しないようにそれを実装せよという問題でした。

; Exercise 3.18

(define (check-circulation lst)
  (define (get-next tadpole)
    (cond ((null? (cdr tadpole)) #f)
          ((memq (cadr tadpole) (car tadpole)) #t)
          (#t (cons (cons (cadr tadpole) (car tadpole))
                    (cddr tadpole)))))
  (define (iter tadpole)
    (if (pair? tadpole) (iter (get-next tadpole)) tadpole))
  (iter (cons '() lst)))

; Exercise 3.19

(define (find elem lst depth)
  (cond ((<= depth 0) #f)
        ((null? lst) #f)
        ((eq? elem lst) #t)
        (#t (find elem (cdr lst) (- depth 1)))))
(define (infinite-loop? lst)
  (define (go-downstairs lst node depth)
    (cond ((null? node) #f)
          ((find node lst depth) #t)
          (#t (go-downstairs lst (cdr node) (+ depth 1)))))
  (go-downstairs lst lst 0))


[PR]
by tempurature | 2015-08-25 23:15 | scheme
SICP Exercise 3.17 の解答
この問題のヒントが気に入らなくて、別回答を考えました。

(define (flatten lst)
  (cond ((null? lst) '())
        ((not (list? lst)) '())
        (#t (append (list lst)
                    (flatten (car lst))
                    (flatten (cdr lst))))))
(define (filter proc lst)
  (cond ((null? lst) '())
        ((proc (car lst)) (cons (car lst) (filter proc (cdr lst))))
        (#t (filter proc (cdr lst)))))
(define (uniq lst)
  (define (iter res rest)
    (if (null? rest)
        res
        (let ((current (filter (lambda (x) (eq? x (car rest)))
                               (cdr rest))))
          (if (null? current) (iter (cons (car rest) res) (cdr rest))
                              (iter res (cdr rest))))))
  (iter '() lst))
(define (count-pairs x)
  (length (uniq (flatten x))))

[PR]
by tempurature | 2015-08-23 15:13 | scheme
とあるSICP 3章の環境の説明図の簡単なバージョン
SICPで⦿⦿(ニップルマーク?)が出てきた時、最初これの意味がわかりませんでした。なのでSICPの説明図より簡単な場合について作図してみました。合ってなかったらごめんなさい。

c0364169_21311784.png

<ソースコード>

(define (add a b) (+ a b))
(define (make-add-proc a)
(define (dispatch b) (add a b))
dispatch)
(define add-10 (make-add-proc 10))


[PR]
by tempurature | 2015-08-22 21:31 | scheme
800x600の画面でDr. Racketの言語を切り替える方法
chromebookでChromeリモートデスクトップなどを使用する際、chromebookの画面解像度の都合上、リモートPCの解像度は800x600に設定しています。

そうするとVS, Eclipseなどを使う場合には多分に使い勝手が悪いのですが、Dr. Racketを使う分にはこれで間に合っています。

ただ、Dr. Racketでracketのコードを書きたくて、SICPも勉強したい人は次のウィンドウに悩まされるはずです。

c0364169_15524334.png
Dr. Racketのメニューバーから[Language] - [Choose Language]を選択して
表示されるウィンドウ

なんとこのウィンドウはOther Languagesを選択すると下に伸びます。

c0364169_15561202.png
ここで私なんかはまごついてしまうのですが、次のようにすればうまくいきます。

  • racket選択時:[The Racket Language]を選択して、Enterキーを押す。
  • R5RS選択時:[Other Languages]を選択して、[R5RS]をダブルクリックする。


[PR]
by tempurature | 2015-08-17 16:00 | プログラミング
SICP ex.3.9の代わりに変なコード書いてみた
問題3.9が例のごとく面倒な作図問題で、環境の話はDr. RacketをREPLしているうちになんとなく理解していたので、応用問題を自分で考えました。

Q. 自分自身を書き換える手続きを定義せよ。

A.
(define (f x) #f)
(let* ((f1 (lambda () #f))
(f2 (lambda () (set! f f1) 2)))
(set! f1 (lambda () (set! f f2) 1))
(set! f f1))

または
(define (f)
  (define (f1) (set! f f2) 1)
  (define (f2) (set! f f1) 2)
  (f1))


[PR]
by tempurature | 2015-08-15 23:26 | scheme
【racket】電卓サンプル
racketで電卓サンプル作りました。ソースコードは240行あります。

c0364169_01053595.png
<github>



[PR]
by tempurature | 2015-08-14 01:07 | scheme
「関数型プログラミングに目覚めた! IQ145の女子高校生の先輩から受けた特訓5日間」を読みました
表紙を見た時は、いつものアレかと思ってスルーしていたのですが、ネット界隈でものすごいバッシングを受けているらしいということであえて読んでみることにしました。400ページありましたが7時間くらいで読めたと思います。

内容としてはラノベ5割、哲学3割、コードの解説2割といったところでしょうか。言っていることは8割がた合っているとはおもいますが、Javascriptで関数型プログラミングをしたい人向けの本であることと、内容がスカスカなので、読む価値がないという意見は正しいと思います。

(それにしてもハードウェアモードってなんだったんだ?SICPにもそんな用語なかったみたいだし、彼の造語であれば知らない人をだましていることになる)

ラノベの内容については、私は小学校の時にスレイヤーズをやみつきになって読んだきりなので正しくは判断できないですが、それほど悪いものではなかったとは思います。疲れている人の気分転換にはなると思います。

ただ、Javascript, Lisp, Smalltalkなどのうんちくは面白かったかなと。私はRacketerなのでLisperと胸はって言えなくて、Lisp自体関数型言語というよりはメタプログラミング言語というのが正しいと思うので、偉そうに関数型プログラミングについて講釈たれることなんておこがましいと思っています。筆者の岡部健氏がSICPの信者だということでそういうところでは共感もあります。

人の意見を鵜呑みにしないで自分で考えろというのを繰り返しますが、プログラマというのは情報の大海に飲まれて嘘情報に騙され傷だらけになりながら成長するものだと思うので、ある程度教条主義に陥るのも仕方がないのかと思います。ただ、自分の考えを必要もないのに人に言って回っていたら嫌われ者になるのだと思います(分かっていてもついやってしまうのですねー)。
(だいたいポール・グレアムやその他のLisperのいうようにLispが最強なのかは私の中で未だに判断ついていないです)

[PR]
by tempurature | 2015-08-13 19:47 | プログラミング
googleリモートデスクトップではアンダーバー(_)を入力することができない
知らなかった。2週間くらい使っているのに気付かなかった。

なるほどlispにはアンダーバーを使う文化がないからか。

[PR]
by tempurature | 2015-08-11 22:27
bashはすごいのか?
bashはシェルスクリプティングで一番メジャーなシェルですが、プログラミング言語としてはいかほどのものなのでしょうか?

BashはBシェル(bsh)に近いのですが、Bシェルよりもインタラプティブです。BシェルはPOSIXで規定されているシェルのことを指しますが対話処理には向かないようであり、CシェルはBシェルと比較してインタラプティブなのでもてはやされた時期があったようです。
(参考:ブルース・ブリン「入門UNIX シェルプログラミング 改訂第2版」)

bashが効果を発揮するのは、主にテキストファイルの操作においてですが、それでもbashは6割くらいしかニーズを満たしてくれません。しかし、自分がやりたかったことがsed, grep, pipeなんかとジャストミートすると恐ろしいくらいコード効率が上がるわけです。つまりperlで100行必要なものが10行で済んでしまう。

6割しかニーズを満たさないので、足りない機能は短いperlコードで補ってやったりするわけですが、それでもperl, rubyだけで書いたプログラムに比べてコード効率がいいし、可読性もテスタビリティも向上します。

ただ、bashコードは3行書くだけでも非常に苦しみますね。そういう意味ではwrite-only-languageたるperlと双極をなすread-only-languageのAdaに近いところがあるかもしれません。(アホすぎる文なので見せ消し) なぜかというと、シェルスクリプトで正規表現を書こうとする場合、getoptやエスケープシーケンスの仕組みなど、スクリプトを書くのを放棄してしまうような罠が結構あったりするからです。

もしそのような問題で苦しんでいる場合、echoコマンドやprintfコマンドが役に立ちます。bashスクリプトではsedやgrepなどのコマンドがbash経由で呼び出されます。

 user -> bash -> sed, grepなど

なので、bashに打ち込んだ文字が自分の意図通りに解釈されているかを知るために、echoコマンドやprintfコマンドを入力して確認します。

user@user-PC ~
$ echo 'windows\directory' | sed -r "s/\/\//g"
sed: -e expression #1, char 8: `s' コマンドが終了していません

user@user-PC ~
$ echo 'windows\directory' | sed -r "s/\\/\//g"
sed: -e expression #1, char 8: `s' コマンドが終了していません

user@user-PC ~
$ echo 'windows\directory' | sed -r 's/\\/\//g'
windows/directory

(例は適当です)

bashの強みはperl, lispと同じくインタプリタが搭載されていて、かつ、Java, C#のIDEのように強力な入力支援機能が搭載されていることです。

<インタプリタの強み>
・マニュアルを見なくともコマンドが存在するか確認できる
・コマンドの使い方に自信がない時、素早く色々試せる

<入力支援機能の強み>
・手が痛くならない
・ゲームみたいで楽しい
・タイプミスが減らせる

とはいえ、bashでプログラミングをするのはlispでプログラムするよりも難易度が高いと思います。自分のしたいことがbashでできるのか見極めることと、自分がしようとしていることよりも効率のよい方法がないか考えることが求められるからです。最初に汚いコードを書いてきれいにしていくというようなやり方はあまりできないと思います。

自分なんかはbashコードを1日に30行も書くことができないです。bashコードを3行書くために100回PEPLしているように思います。なのでbashのプログラミングをすると手よりも頭が疲れてしまいます。まさにプロ仕様の言語なわけです。

だからbashというのは誰でも使っているから大したことがないように思うけれど、実は知る人ぞ知る名言語なのではないかと思うわけなのです。

<追記>
とある名言、
私が知る中で、書く人がタイピングよりも考える事に費やす時間が長い言語は、SQL, Lisp, Haskellだけだ。 - Philip Greenspun
というのに是非bashを加えて頂きたく、どうでしょうか?

[PR]
by tempurature | 2015-08-09 23:38 | プログラミング