- 追加された行はこの色です。
- 削除された行はこの色です。
#contents
* 家電機器の連携動作の形式的記述について [#a956e427]
- あれってSICPの[[制約システム:http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_%_sec_Temp_396]]が参考になりませんか?Gaucheの実装は[[ここ:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3A%E5%88%B6%E7%B4%84%E3%81%AE%E6%8B%A1%E6%95%A3]]に転がっています。制約プログラミングの[[エッセイ:http://madeira.cc.hokudai.ac.jp/RD/yamamoto/Essay/5.html]]がありました。 - げんま 2006-10-24 (火) 17:47:58
* SEND + MORE = MONEY を解いてみよう! [#e74b7ff8]
S E N D
+ M O R E
----------
M O N E Y
(S,M != 0)
- 10/18の OCaml講義第3回 by ガリグ先生で、授業の課題として出ました。
- 授業では、search関数はガリグ先生のお手本があって、生徒はcheck関数を書くだけでしたが。
- 計算量が苦しいなら、M=1はOKにしましょう。 - げんま
** 授業の課題 [#w55b6646]
val check : (char * int) list -> bool = <fun>
let rec search dict letters numbers =
match letters with
[] -> if check dict then [dict] else []
| a :: leters ->
let rec choose tried numbers =
match numbers with
[] -> []
| n :: numbers ->
let sols = search ((a,n)::dict) letters (tried @ numbers) in
sols @ choose (n::tried) numbers
in
choose [] numbers ;;
val search :
(char * int) list -> char list -> int list -> (char * int) list list = <fun>
let rec interval m n =
if m > n then [] else m :: interval (m+1) n ;;
val interval : int -> int -> int list = <fun>
let solve () =
search [] ['S';'E';'N';'D';'M';'O';'R';'Y'] (interval 0 9) ;;
val solve : unit -> (char * int) list list = <fun>
solve () ;;
- : (char * int) list list = [[('Y',2); ...]]
** Gauche [#if874cf2]
ライブラリに、順列組み合わせのpermutationなどがあったので、かなり楽ができました。見つかったらreturnラベルで大域脱出。2.6Ghzで13秒。 - げんま
(use srfi-1)
(use util.combinations)
(use util.match)
(define return #f)
(define (eval-poly li x)
(fold (lambda (a b) (+ a (* b x))) 0 li))
(define (check li)
(match li
((S E N D M O R Y)
(if
(and
(not (= S 0))
(not (= M 0))
(= (+ (eval-poly (list S E N D) 10)
(eval-poly (list M O R E) 10))
(eval-poly (list M O N E Y) 10)))
(return (list S E N D '+ M O R E '= M O N E Y))))))
(define (solve)
(combinations-for-each
(lambda (a) (permutations-for-each check a))
(iota 10) 8))
(print
(call/cc
(lambda (cc)
(set! return cc)
(solve))))
**Haskellで解いてみる [#n5f2521d]
(''追記''：[[nobsunさんのコード:http://haskell.g.hatena.ne.jp/nobsun/20061019/alphametic]]のほうがスマート。)
([[らくがきえんじん:http://d.hatena.ne.jp/syd_syd/20061018]]にも書いた。)
がしがし書いてください
何も考えてない。15分くらいででけた。こういう問題にはリストモナドがめっぽう強い。（けいご）
Showのインスタンスが必要なのはご愛嬌。
import Control.Monad.State
ten = [0..9]
-- StateT [Int] [] Intが何であるかを考えるより、単に [Int]->[(Int,[Int])] だと思えばよい
-- (「リストlを貰って、その中のどれかの要素eと、lからeを取った残りl'の対(e,l')を返す」という非決定的な関数)
getNum :: StateT [Int] [] Int
getNum = StateT $ ?ns -> do{n <- ns; return (n, filter (n/=) ns)}
sendmory = do
s <- getNum
if s==0 then lift [] else return ()
m <- getNum
if m==0 then lift [] else return ()
e <- getNum
n <- getNum
d <- getNum
o <- getNum
r <- getNum
y <- getNum
if s*1000+e*100+n*10+d+m*1000+o*100+r*10+e==m*10000+o*1000+n*100+e*10+y then return (s,e,n,d,m,o,r,y) else lift []
instance (Show s, Show e, Show n, Show d, Show m, Show o, Show r, Show y)=>
Show (s,e,n,d,m,o,r,y) where
show (s,e,n,d,m,o,r,y) = "("++show s++","++show e++","++show n++","++show d++","++show m++","++show o++","++show r++","++show y++")"
main = print (evalStateT sendmory ten)
#ls(ネタ記録庫)
sydney$ ghc -package mtl Desktop/hoge.hs -o a.out
sydney$ time ./a.out
[(?,?,?,?,?,?,?,?)]
real 0m4.544s
user 0m4.341s
sys 0m0.076s
体感5秒位 (PPC, 2.3GHz dual) ただし今インタプリタ(ghci)で試したら25秒くらいかかった。
**そっちがMonadなら、こっちはamb<<改訂版>> [#rad040bb]
- 48秒@2.6GHz- げんま
(use srfi-1)
;; stack of cc.
(define fail '())
;; nondeterminsm operator
(define (amb li)
(if (null? li)
((pop! fail))
(call/cc
(lambda (cc)
(push! fail (lambda ()
(cc (amb (cdr li)))))
(car li)))))
(define (toint li)
(fold (lambda (a b) (+ a (* b 10))) 0 li))
(define (solve)
(let ((digs (iota 10 0))
(digs1 (iota 9 1)))
(let* ((S (amb digs1))
(E (amb (remove (lambda (a) (memq a (list S))) digs)))
(N (amb (remove (lambda (a) (memq a (list S E))) digs)))
(D (amb (remove (lambda (a) (memq a (list S E N))) digs)))
(M (amb (remove (lambda (a) (memq a (list S E N D))) digs1)))
(O (amb (remove (lambda (a) (memq a (list S E N D M))) digs)))
(R (amb (remove (lambda (a) (memq a (list S E N D M O))) digs)))
(Y (amb (remove (lambda (a) (memq a (list S E N D M O R))) digs))))
(if
(= (+ (toint (list S E N D))
(toint (list M O R E)))
(toint (list M O N E Y)))
(list S E N D '+ M O R E '= M O N E Y)
(amb '())))))
(print
(call/cc
(lambda (cc)
;; initial value for fail
(push! fail
(lambda ()
(cc 'no-choise)))
(solve))))
*javascriptでゲームなら、<canvas>タグが面白い![#k543fb5f]
-[[3DWalker:http://www.abrahamjoffe.com.au/ben/canvascape/index.htm]]
http://www.geocities.jp/teruakigemma/scheme2js/doom.png
*継続とは?[#y87e71e0]
**参考文献 [#c9a07956]
-[[なんでも継続:http://www.shiro.dreamhost.com/scheme/docs/cont-j.html]]
-[[Scheme:なぜSchemeにはreturnが無いのか:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3a%e3%81%aa%e3%81%9cScheme%e3%81%ab%e3%81%afreturn%e3%81%8c%e7%84%a1%e3%81%84%e3%81%ae%e3%81%8b]]
-[[Schemeを作ろう 第3回:http://www.jah.ne.jp/~naoyuki/Writings/VScheme3.html]]
-[[Scheme入門 継続:http://www.shido.info/lisp/scheme_cc.html]]
- 継続には副作用がある。
[[Scheme:call/ccと副作用:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3acall%2fcc%e3%81%a8%e5%89%af%e4%bd%9c%e7%94%a8]]
**何ができるの? [#c933f2be]
- 大域脱出
- 例外処理
- [[非決定性:http://www.shido.info/lisp/scheme_amb.html]] [[gemmaの実装:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?amb]]
例えば、
(let ((i (amb 4 6 7))
(j (amb 5 8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))
;Value 23: (6 5)
のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。
これを理解するのに、自分は3ヶ月かかりました。
ambは、バックトラック演算子です。動きを大雑把に言うと、
(let (i (amb 4 6 7))で、
i に 4 が入ると同時に、
この時点のツヅキ、
"6 7))
(j (amb 5 8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
を取り出して、スタックにpush。
次の行、
(j (amb 5 8 11))で、
j に 5が入ると同時に、
この時点のツヅキ、
"8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
を取り出して、スタックにpush。
(prime? (+ 4 5))は偽。(amb)が動く。amb関数は、引数なしで呼ばれると、スタックをpopして、中身の、ツヅキを実行。
"8 11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
が実行されて、jに8が入ると同時に、
この時点のツヅキ、
"11)))
(if (prime? (+ i j))
(list i j)
(amb)))"
を取り出して、スタックにpush...という感じです。
**もっと教えて! [#vf61a3fe]
-[[名大の謎の天才h003149b氏:http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/index.html]]
-[[SICP.Nondeterministic Computing:http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_%_sec_4.3]]
**継続サーバはどうなった? [#qc90b476]
-[[境界を越える: 継続とWeb開発、そしてJavaプログラミング:https://www-06.ibm.com/jp/developerworks/java/060412/j_j-cb03216.shtml]]
-[[継続サーバの実装の最先端、Seaside:http://www.seaside.st/]]
-[[Seasideの開発者が継続のゆくえについて語る:http://smallthought.com/avi/?p=14]]
-[[もとネタになった??Queinnec氏の論文PDF:http://www-spi.lip6.fr/~queinnec/PDF/webcont.pdf]]
-[[WebBasedアプリケーションと継続について、わかりやすい説明:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3aCPS]]
* 型クラスがあるC言語!? [#h5b86e1f]
- [[Jekyll:http://jekyllc.sourceforge.net/index.html]]
>Jekyll is a high-level language that can be losslessly translated to and from readable editable C. This allows it to be used in C projects, with C programmers, C libraries, and C tools.
#comment
* Compiling Scheme to JavaScript [#p1b71405]
- http://hop.inria.fr/usr/local/share/hop/weblets/home/articles/scheme2js/article.html
- 夏休み中に、Hopを試してみるつもりです。 -- [[げんま]] &new{2006-08-10 (木) 09:39:32};
- [[Compiling to JavaScript:http://calculist.blogspot.com/2006/08/compiling-to-javascript.html]]いろんな言語で、Javascriptへのコンパイルが模索されているらしい。 -- [[げんま]] &new{2006-08-26 (土) 10:22:24};
- Scheme2jsを使って、テトリスを書いてみました。http://www.geocities.jp/teruakigemma/scheme2js/demo.html -- [[げんま]] &new{2006-09-02 (土) 21:10:45};
- sugeeeeee! -- [[Keigo]] &new{2006-09-04 (月) 16:55:31};
- あれ、IEだとキー入力ができないです。Firefoxでならできてたんです。 -- [[げんま]] &new{2006-09-04 (月) 21:23:40};
- Safari(MacOSX)ではOK。ところで勉強会には来れません？ -- [[けいご]] &new{2006-09-04 (月) 21:56:00};
- １１日の勉強会に行きます。浜松に帰省してましたが、ようやく。PPLサマースクールでバイト申し込んだので、そこでもみんなに会えます♪ -- [[げんま]] &new{2006-09-05 (火) 10:13:39};
- prototype.jsのおかげで、ＩＥでキー入力できるようになりました。 -- [[げんま]] &new{2006-09-05 (火) 22:55:07};
- script.aculo.usのデモを書いてみました。Firefoxでは動いてるんですが、他だとどうでしょう。http://www.geocities.jp/teruakigemma/scheme2js/aculo.html -- [[げんま]] &new{2006-09-07 (木) 02:09:49};
#comment
* Proof are Programs [#fca44cec]
- http://www.radiumsoftware.com/0605.html#060523
- Philip Wadler. [[Proofs are Programs: 19th Century Logic and 21st Century Computing:http://homepages.inf.ed.ac.uk/wadler/papers/frege/frege.pdf]]
- 数理論理学とコンピュータ・プログラムの間には深い関連性がある。この論文では，近代論理学の開祖であるフレーゲの概念記法を出発点として，ゲンツェンの自然演繹 と，チャーチの型付きラムダ計算の二つの流れを追い，最終的にそれらのモデルがカリー・ハワード対応によって同型として対応付けられるところまでを辿る。
* History of Haskell [#z4d010cb]
- http://haskell.org/haskellwiki/History_of_Haskell
- HOPL'07に提出する予定の論文の、ドラフトだそうです。
#comment
* Functional Reactive Programming [#i4d505da]
- http://www.haskell.org/frp/
- LL3での、"Functional Reactive Programming in Scheme"の発表者、 Gregory Cooper氏のホームページ http://www.cs.brown.edu/~greg/
#comment
* roguelike in ocaml [#o7afaf8c]
(今井) http://cristal.inria.fr/%7Eddr/mlrogue/
- おぉーー! -- [[源馬]] &new{2006-07-13 (木) 03:12:06};
#comment
* 尋ね人 [#sdf98c23]
- 場違いな質問で恐縮ですが、ご存じありませんか? 名大の方みたいなんですが。
- http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/index.html -- [[源馬]] &new{2006-07-11 (火) 04:30:06};
- その人、気になりますよね。私と同い年です。元坂部研という噂。ただ、私は情報工学の人間ではなかったので、知りません。末ちゃんなら知ってると思う。 -- 今井
- たくさん興味深いことを書かれているので、続きを読みたい! -- [[源馬]] &new{2006-07-13 (木) 03:18:14};
- 確かに同級生のようです．ただ名前が無いので誰だか分からない。。。 -- [[末次]] &new{2006-08-10 (木) 21:59:55};
- 名字は"水野"だそうです。そこまでなんとか掴みました。 -- [[末次]] &new{2006-08-10 (木) 22:10:37};
- "水野"で坂部研なら水野 清貴君かな? かなり当てずっぽうです．信憑性はありません． -- [[末次]] &new{2006-08-10 (木) 22:13:33};
- 違うよ。そうじゃなくて…僕らがB4の時の坂部研だったはず -- [[けいご]] &new{2006-08-11 (金) 12:07:11};
- M1になってはじめに聞いたのが彼の行方だったのだけど(明らかに先を越されていたから)、確か末ちゃんその時は教えてくれたような… -- [[けいご]] &new{2006-08-11 (金) 12:09:11};
- [[はてなブックマークでもそれなりに人気が:http://b.hatena.ne.jp/entrylist?url=http%3A%2F%2Fwww.ice.nuie.nagoya-u.ac.jp%2F]] -- [[けいご]] &new{2006-08-11 (金) 12:28:46};
#comment
*[[AA折れ線グラフ:http://oss.timedia.co.jp/index.fcgi/kahua-web/show/column/%ba%a3%c6%fc%a4%ce%b0%ec%b9%d4/%a3%b2%a3%b0%a3%b0%a3%b6%c7%af%a3%b3%b7%ee#H-1bpntk8]] [#j83662b2]
>AAで折れ線グラフを書くというお題．
>入力は'R','F','C'の3種類も文字からなる長さ1以上の文字列
>'R'は上昇を表し，折れ線グラフの要素としては '/' (スラッシュ)1文字に対応
>'F'は下降を表し，折れ線グラフの要素としては '?' (バックスラッシュ)1文字に対応
>'C'は変化なしを表し，折れ線グラフの要素としては'_'(アンダスコア)1文字に対応
>たとえば，
$ ./plot RCRFCRFFCCRFFRRCRRCCFRFRFF
>とすると
__
/ ?/?/?
_/?_/? _/ ?
/ ?__/? /
?/
>が出力されるようなスクリプトを書け．
> --nobsun
源馬のSchemeでの回答はこちら。~
http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?gemma -- [[源馬]] &new{2006-07-01 (土) 12:00:06};
**解答 in Haskell [#nd70223e]
下村です。
無駄に長い上に汚いですけど…。
output str =
let result = graph str
output' :: [String] -> IO ()
output' mat =
if any null mat then return ()
else do if any (' '/=) h then putStrLn h
else return ()
output' t
where
h = map head mat
t = map tail mat
in
output' result
graph :: String -> [String]
graph str =
let
height = (length str) * 2
graph' [] _ = []
graph' (x:xs) pos =
case x of
'R' -> oneline (pos) '/' height : graph' xs (pos-1)
'F' -> oneline (pos+1) '??' height : graph' xs (pos+1)
'C' -> oneline pos '_' height : graph' xs pos
in
graph' str (length str)
-- n番目の文字がcであるような、長さlの文字列を生成する
oneline :: Int -> Char -> Int -> String
oneline _ _ 0 = ""
oneline n c l = (if n==0 then c else ' ') : oneline (n-1) c (l-1)
で、結果は…
Main> output "RCRFCRFFCCRFFRRCRRCCFRFRFF"
__
/ ?/?/?
_/?_/? _/ ?
/ ?__/? /
?/
Main>
**解答 in OCaml [#yc2d1595]
また下村です。OCamlで書き換えたので書いときます。Haskell版より関数とかをちょっと整理しました。あと、文字列はコマンドライン引数で指定するようにしてあります。explodeとimplodeは拡張ライブラリ関数なので、コンパイルするためにはExtLibをインストールする必要があります。
(* <<COMPILE>> "ocamlopt -I +extlib extlib.cmxa lineGraph.ml" *)
open ExtString.String;;
open List;;
exception NotRFC;;
let any = List.fold_left (or) false;;
let graph charlist =
let height = (length charlist) * 2 in
let rec transpose mat = if any (map (fun x -> x=[]) mat)
then []
else map hd mat :: transpose (map tl mat) in
let rec oneline n c l = if l=0
then []
else (if n=0 then c else ' ') :: oneline (n-1) c (l-1) in
let rec graph' charlist pos =
match charlist with
[] -> []
| c::cs -> match c with
'R' -> oneline (pos) '/' height :: graph' cs (pos-1)
| 'F' -> oneline (pos+1) '??' height :: graph' cs (pos+1)
| 'C' -> oneline pos '_' height :: graph' cs pos
| otherwise -> raise NotRFC
in
transpose (graph' charlist (length charlist));;
let output =
try
let result =
map (fun l -> if any (map (fun x -> x<>' ') l)
then implode l ^ "?n" else "")
(graph (explode Sys.argv.(1))) in
let rec output' list = match list with
[] -> ()
| (""::ls) -> output' ls
| (l::ls) -> print_string l;
output' ls in
output' result
with
NotRFC ->
print_string ("Usage : " ^ Sys.argv.(0) ^ " [RFC]*?n")
| Invalid_argument _ ->
print_string ("Usage : " ^ Sys.argv.(0) ^ " [RFC]*?n");;
実行結果は…
mac{sho}% ./a.out RCRFCRFFCCRFFRRCRRCCFRFRFF [~/src/ocaml]
__
/ ?/?/?
_/?_/? _/ ?
/ ?__/? /
?/
mac{sho}% [~/src/ocaml]
- Ocamlがわかってないので、おぼろげにしかわからないです。なんかすごい。今度、教えてください。 -- [[源馬]] &new{2006-07-04 (火) 03:35:28};
#comment
* HaskellでOS。 [#s0a682d7]
http://www.cse.ogi.edu/~hallgren/House/ -- [[源馬]] &new{2006-07-04 (火) 16:16:05};
*The Evolution of a Haskell Programmer [#ga1c48ba]
[[The Evolution of a Haskell Programmer:http://www.willamette.edu/~fruehr/haskell/evolution.html]] かなりハイレベルにバカやってる感じ
- バカだ〜！fold関数使うまではわかるけど、その後が！まだまだまだまだ続くし。 -- [[げんま]] &new{2006-08-12 (土) 10:35:43};
- インタプリタを作って階乗計算させたり，型クラスを使ったテクニックなんかもあるので分かると結構良いかも。 -- [[けいご]] &new{2006-08-12 (土) 15:27:52};
#comment
![[PukiWiki]](image/caml3.jpg "[PukiWiki]")
