ネタ記録庫のバックアップ(No.40)

Monadとamb、非決定性計算と副作用 &dagger;

下をやって思ったんですが。Monadは副作用に使う。ambはcall/ccを使う、そしてcall/ccは副作用をうむ。似ているのでちょっと感動しました。 - げんま

SEND + MORE = MONEY を解いてみよう! &dagger;

  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にしましょう。 - げんま

↑

Gauche &dagger;

ライブラリに、順列組み合わせの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で解いてみる &dagger;

(追記：nobsunさんのコードのほうがスマート。) (らくがきえんじんにも書いた。)

何も考えてない。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)

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<<改訂版>> &dagger;

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>タグが面白い! &dagger;

3DWalker

↑

継続とは? &dagger;

↑

参考文献 &dagger;

継続には副作用がある。 Scheme:call/ccと副作用

↑

何ができるの? &dagger;

大域脱出
例外処理

非決定性 gemmaの実装

例えば、
(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...という感じです。

↑

もっと教えて! &dagger;

↑

継続サーバはどうなった? &dagger;

↑

型クラスがあるC言語!? &dagger;

Jekyll
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.

↑

Compiling Scheme to JavaScript? &dagger;

http://hop.inria.fr/usr/local/share/hop/weblets/home/articles/scheme2js/article.html
夏休み中に、Hopを試してみるつもりです。 -- げんま? 2006-08-10 (木) 09:39:32
Compiling to JavaScriptいろんな言語で、Javascriptへのコンパイルが模索されているらしい。 -- げんま? 2006-08-26 (土) 10:22:24
Scheme2jsを使って、テトリスを書いてみました。http://www.geocities.jp/teruakigemma/scheme2js/demo.html -- げんま? 2006-09-02 (土) 21:10:45
sugeeeeee! -- Keigo? 2006-09-04 (月) 16:55:31
あれ、IEだとキー入力ができないです。Firefoxでならできてたんです。 -- げんま? 2006-09-04 (月) 21:23:40
Safari(MacOSX)ではOK。ところで勉強会には来れません？ -- けいご? 2006-09-04 (月) 21:56:00
１１日の勉強会に行きます。浜松に帰省してましたが、ようやく。PPLサマースクールでバイト申し込んだので、そこでもみんなに会えます♪ -- げんま? 2006-09-05 (火) 10:13:39
prototype.jsのおかげで、ＩＥでキー入力できるようになりました。 -- げんま? 2006-09-05 (火) 22:55:07
script.aculo.usのデモを書いてみました。Firefoxでは動いてるんですが、他だとどうでしょう。http://www.geocities.jp/teruakigemma/scheme2js/aculo.html -- げんま? 2006-09-07 (木) 02:09:49

お名前:

↑

Proof are Programs &dagger;

http://www.radiumsoftware.com/0605.html#060523
Philip Wadler. Proofs are Programs: 19th Century Logic and 21st Century Computing
数理論理学とコンピュータ・プログラムの間には深い関連性がある。この論文では，近代論理学の開祖であるフレーゲの概念記法を出発点として，ゲンツェンの自然演繹と，チャーチの型付きラムダ計算の二つの流れを追い，最終的にそれらのモデルがカリー・ハワード対応によって同型として対応付けられるところまでを辿る。

↑

History of Haskell &dagger;

http://haskell.org/haskellwiki/History_of_Haskell
HOPL'07に提出する予定の論文の、ドラフトだそうです。

↑

Functional Reactive Programming &dagger;

http://www.haskell.org/frp/
LL3での、"Functional Reactive Programming in Scheme"の発表者、 Gregory Cooper氏のホームページ http://www.cs.brown.edu/~greg/

↑

roguelike in ocaml &dagger;

(今井) http://cristal.inria.fr/%7Eddr/mlrogue/

おぉーー! -- 源馬? 2006-07-13 (木) 03:12:06

↑

尋ね人 &dagger;

場違いな質問で恐縮ですが、ご存じありませんか? 名大の方みたいなんですが。
http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/index.html -- 源馬? 2006-07-11 (火) 04:30:06
その人、気になりますよね。私と同い年です。元坂部研という噂。ただ、私は情報工学の人間ではなかったので、知りません。末ちゃんなら知ってると思う。 -- 今井
たくさん興味深いことを書かれているので、続きを読みたい! -- 源馬? 2006-07-13 (木) 03:18:14
確かに同級生のようです．ただ名前が無いので誰だか分からない。。。 -- 末次? 2006-08-10 (木) 21:59:55
名字は"水野"だそうです。そこまでなんとか掴みました。 -- 末次? 2006-08-10 (木) 22:10:37
"水野"で坂部研なら水野清貴君かな? かなり当てずっぽうです．信憑性はありません． -- 末次? 2006-08-10 (木) 22:13:33
違うよ。そうじゃなくて…僕らがB4の時の坂部研だったはず -- けいご? 2006-08-11 (金) 12:07:11
M1になってはじめに聞いたのが彼の行方だったのだけど(明らかに先を越されていたから)、確か末ちゃんその時は教えてくれたような… -- けいご? 2006-08-11 (金) 12:09:11
はてなブックマークでもそれなりに人気が -- けいご? 2006-08-11 (金) 12:28:46

↑

AA折れ線グラフ &dagger;

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 -- 源馬? 2006-07-01 (土) 12:00:06

↑

解答 in Haskell &dagger;

下村です。無駄に長い上に汚いですけど…。

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 &dagger;

また下村です。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がわかってないので、おぼろげにしかわからないです。なんかすごい。今度、教えてください。 -- 源馬? 2006-07-04 (火) 03:35:28

↑

HaskellでOS。 &dagger;

http://www.cse.ogi.edu/~hallgren/House/ -- 源馬? 2006-07-04 (火) 16:16:05

↑

The Evolution of a Haskell Programmer &dagger;

The Evolution of a Haskell Programmer かなりハイレベルにバカやってる感じ

バカだ～！fold関数使うまではわかるけど、その後が！まだまだまだまだ続くし。 -- げんま? 2006-08-12 (土) 10:35:43
インタプリタを作って階乗計算させたり，型クラスを使ったテクニックなんかもあるので分かると結構良いかも。 -- けいご? 2006-08-12 (土) 15:27:52

ネタ記録庫 のバックアップ(No.40)