Skip to content
2011/05/08 / highmt

clojureで継続モナドを使う

環境:
Clojure 1.2.0

非決定性を扱うにはいろいろな選択肢がありますが、そのひとつとして継続での実装があると思います。
clojureで継続を使うには On Lisp 風の継続渡しマクロを使った実装などが考えられますが、
今回は継続モナドの使い方のサンプルもかねて継続モナドで choose / fail を書いてみました。
連続して失敗する選択肢が多いとスタックが溢れるので実用にはなりません。
工夫したらなんとかなるんだろうか…。
陽に restart を返してたりとかあんまり継続を使うメリットいかせてないし…。
新しくモナド書いてうまく隠せばいけそうな気もするけど今の力ではとても大掛かりな感じがするし…。
そもそもモナドを使うのであれば素直にシーケンスとかを使ったほうが
m-zeroとか使ってもっとシンプルに書けるし対角化シーケンスとかの応用もできるしよさげです多分。

(use '[clojure.contrib.monads])

(defn choose
  "Chooses one from specified choices.
  Returns a function to try the next choice for each choices."
  ([choices]
     (with-monad cont-m
       (call-cc
        (fn [cc]
          (m-result (choose cc choices))))))
  ([cc choices]
     (if (empty? choices)
       [nil nil]
       [(first choices) #(cc (choose cc (next choices)))])))

(defn pass
  "Falls through to pass the choice."
  ([] (pass nil))
  ([v] (with-monad cont-m (m-result v))))

(defn merge-restarts
  "Calls restart to go back to the next choice."
  [restarts]
  #(if-let [restart (some identity (reverse restarts))]
     (restart)
     (pass true)))

(defn test-choose
  "Gets choices from the function 'choose' and returns a passed result.
  The returned result contains a function to try the next choice."
  []
  (run-cont (domonad cont-m
              [[v1 restart1 :as vr1] (choose [1 2 3])
               [v2 restart2 :as vr2] (choose [5 6 7])
               :let [v (if (not-any? nil? [v1 v2]) (* v1 v2))
                     fail (merge-restarts [restart1 restart2])]
               ;; sample test
               eos (if (or (nil? v) (odd? v))
                     (fail)
                     (pass))]
              ;; passed result
              [[v1 v2 v] (if-not eos fail)])))

(defn do-test-choose []
  "Collects results from the function 'test-choose' and returns lazy-seq of them."
  (letfn [(step [[v restart]]
            (lazy-seq
             (if restart (cons v (step (run-cont (restart)))) nil)))]
    (step (test-choose))))

;;; get lazy-seq
(do-test-choose)
;; user=> (do-test-choose)
;; ([1 6 6] [2 5 10] [2 6 12] [2 7 14] [3 6 18])

;;; or step manually in repl
(test-choose)
;; user=> (test-choose)
;; [[1 6 6] #<user$choose$fn__917 user$choose$fn__917@6155035a>]
(run-cont ((fnext *1)))
;; user=> (run-cont ((fnext *1)))
;; [[2 5 10] #<user$choose$fn__917 user$choose$fn__917@72a60191>]
;; user=> (run-cont ((fnext *1)))
;; [[2 6 12] #<user$choose$fn__917 user$choose$fn__917@41697023>]
;; ...

広告

One Comment

Trackbacks

  1. 続 clojureで継続モナドを使う « 日々の反省1

現在コメントは受け付けていません。

%d人のブロガーが「いいね」をつけました。