Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-10-22

ClojureでL-99 (P26 指定した個数を抜き出す組み合わせ)

| 17:01 | ClojureでL-99 (P26 指定した個数を抜き出す組み合わせ) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P26 指定した個数を抜き出す組み合わせ) - わだばLisperになる

Arcの[]や、Clojureの#()は、便利なんですが、更に進んで、mapの等で、`#(~(first coll) ~@%)みたいに書きたくなることが結構あります。どっちも今のところできません。というか、筋道立てて考えるとそもそも無理な相談という感じなのですが。

(defn 
  #^{:doc "P26 (**) Generate the combinations of K distinct objects 
chosen from the N elements of a list"
     :test (do (test= (combination 0 [1 2 3]) [])
               (test= (combination 88 []) [])
               (test= (count (combination 3 (range 12))) 220))}
  combination
  ([num coll]
     (cond (or (empty? coll) (>= 0 num)) 
           []
           (= 1 num) 
           (map list coll)
           :else
           `(~@(map #(cons (first coll) %)
                    (combination (- num 1) (rest coll)))
             ~@(combination num (rest coll))))))

2008-10-21

ClojureでL-99 (P25 ランダムに並び換え)

| 12:21 | ClojureでL-99 (P25 ランダムに並び換え) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P25 ランダムに並び換え) - わだばLisperになる

ちょっと鬱気味だなあと思ったら、L-99をやってませんでした。いけないいけない。L-99は心が安らぎます。

(defn 
  #^{:doc "P25 (*) Generate a random permutation of the elements of a list."
     :test (do (test= (rnd-permu []) [] ))}
; ---------
  rnd-permu
; ---------
  ([coll]
     (rnd-select coll (count coll))))

2008-10-16

ClojureでL-99 (P24 ロトくじ)

| 12:21 | ClojureでL-99 (P24 ロトくじ) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P24 ロトくじ) - わだばLisperになる

こういうランダムな場合に上手く条件をテストできる方法が知りたいと思ったり。

(defn
  #^{:doc "P24 (*) Lotto: Draw N different random numbers from the set 1..M."}
; ------------
  lotto-select
; ------------
  ([nums rng]
     (if (or (>= 0 rng) (>= 0 nums)) 
       nil
       (rnd-select (range 1 (+ 1 rng)) nums))))

2008-10-14

ClojureでL-99 (P23 ランダムに指定した個数の要素を選択)

| 06:37 | ClojureでL-99 (P23 ランダムに指定した個数の要素を選択) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P23 ランダムに指定した個数の要素を選択) - わだばLisperになる

P20で作ったremove-atを使用します。どうも、ぱっとしない出来。

(defn
  #^{:doc "P20 (*) Remove the K'th element from a list."
     :test (do (test= (rnd-select [] 3) [])) }
; ----------
  rnd-select
; ----------
  ([coll num]
     (loop [coll coll, cnt 1, len (length coll), ans [] ]
       (if (or (empty? coll) (> cnt num))
         ans
         (let [p (rand-int len)]
           (recur (remove-at coll (+ 1 p))
                  (+ 1 cnt)
                  (+ -1 len)
                  (conj ans (nth coll p))))))))

2008-10-13

ClojureでL-99 (P22 指定した範囲の数列のリスト)

| 06:26 | ClojureでL-99 (P22 指定した範囲の数列のリスト) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P22 指定した範囲の数列のリスト) - わだばLisperになる

fromの反対のdownfromとか定義してみましたが、もう一工夫という感じです。

ちなみに、標準で、Clojureには、rangeがありますが、このお題と同じ動きではありません。

(defn downfrom 
  ([start]
     (downfrom start 1))
  ([start step]
     (iterate #(- % step) start)))

(defn
  #^{:doc "P22 (*) Create a list containing all integers within a given range."
     :test (do (test= (my-range 4 9)
                      '(4 5 6 7 8 9))
               (test= (my-range 9 4)
                      '(9 8 7 6 5 4))
               (test= (my-range 3 3)
                      '(3)))}
; --------
  my-range
; --------
  ([start end]
     (cond (< start end) 
           (take (+ 1 (- start) end) (from start))
           (> start end) 
           (take (+ 1 start (- end)) (downfrom start))
           :else
           (list start))))

2008-10-10

ClojureでL-99 (P21 指定した位置に要素を挿入する)

| 06:42 | ClojureでL-99 (P21 指定した位置に要素を挿入する) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P21 指定した位置に要素を挿入する) - わだばLisperになる

前回と同じく無限リストを利用してみました。あとおまけで、EmacsのC-tのような操作でくるくるひっくり返してゆくパターンを思い付いたので書いてみました。

とりあえず、condの節の括弧はやっぱりあった方が良いと思うんですよねー。

(defn
  #^{:doc "P21 (*) Insert an element at a given position into a list."
     :test (do (test= (insert-at 'alfa '(a b c d) 2)
                      '(a alfa b c d))
               (test= (insert-at 'alfa [] 2)
                       '(alfa))        
               (test= (insert-at 'alfa '(a b c d) -2)
                      '(alfa a b c d))
               (test= (insert-at 'alfa '(a b c d) 100)
                      '(a b c d alfa))) }
; ---------
  insert-at
; ---------
  ([item coll pos]
     (let [len (count coll)]
       (cond 
        (empty? coll) 
        (list item)
        ;; 
        (>= 0 pos) 
        (cons item coll)
        ;; 
        (<= len pos) 
        (concat coll (list item))
        ;; 
        :else 
        (mapcat #(if (= pos %1) 
                   (list item %2)
                   (list %2))
                (from 1)
                coll)))))

;; 要素をくるくるひっくり返しつつ送ってゆくパターン
(defn insert-at
  ([item coll pos]
     (loop [coll (cons item coll), cnt pos, acc [] ]
       (if (or (>= 1 cnt) (nil? (rest coll)))
         (concat (reverse acc) coll)
         (recur (cons (first coll) (rrest coll))
                (+ -1 cnt)
                (cons (second coll) acc))))))

2008-10-09

ClojureでL-99 (P20 指定した要素を削除)

| 21:31 | ClojureでL-99 (P20 指定した要素を削除) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P20 指定した要素を削除) - わだばLisperになる

1..∞ な遅延リストと、リストを対応付けて解いてみました。

fromは、pfcから拝借(pfcのことなのでHaskellとかが元ネタかも…)。

fromの中のiterateは、初期値に関数を適用して、その結果にまた関数を適用して…な遅延リストを作成します。

stepはオプショナルにしていますが、clojureの場合、オプショナル引数は、オプションがある場合とない場合を分けて記述します。この辺がCLとはちょっと違うところ。

(defn
  #^{:doc "P20 (*) Remove the K'th element from a list."
     :test (do (test= (remove-at [] 3) [])
               (test= (remove-at '(a b c d) -3)
                      '(a b c d))
               (test= (remove-at '(a b c d) 100)
                      '(a b c d))
               (test= (remove-at '(a b c d) 2)
                      '(a c d))) }
; ---------
  remove-at
; ---------
  ([coll pos]
     (if (empty? coll)
       []
       (mapcat #(if (= pos %1) [] (list %2))
               (from 1)
               coll))))

(defn from 
  ([start]
     (from start 1))
  ([start step]
     (iterate #(+ step %) start)))

2008-10-06

ClojureでL-99 (P18 範囲切り出し)

| 21:31 | ClojureでL-99 (P18 範囲切り出し) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P18 範囲切り出し) - わだばLisperになる

Clojureには標準でsubseqがあります。

(defn
  #^{:doc "P18 (**) Extract a slice from a list."
     :test (do (test= (slice [] 3 7) [])
               (test= (slice '(a b c d e f g h i k) 3 7)
                      '(c d e f g))
               (test= (slice '(a b c d e f g h i k) -3 7)
                      (slice '(a b c d e f g h i k) 1 7))
               (test= (slice '(a b c d e f g h i k) -3 100)
                      '(a b c d e f g h i k))) }
; -----
  slice
; -----
  ([coll start end]
     (if (empty? coll)
       []
       (let [len (count coll), start (max start 1), end (min end len)]
         (loop [coll coll, pos 1, acc [] ]
           (if (or (empty? coll) (< end pos))
             (reverse acc)
             (recur (rest coll)
                    (+ 1 pos)
                    (if (<= start pos end)
                      (cons (first coll)
                            acc)
                      acc))))))))

2008-10-05

ClojureでL-99 (P17 指定した位置でリストを分割)

| 17:18 | ClojureでL-99 (P17 指定した位置でリストを分割) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P17 指定した位置でリストを分割) - わだばLisperになる

ありあわせの関数を使っちゃいけないということなので自前で処理しましたが、take、drop、take-while等々あるのでそれを使えば簡単に書けます。

(defn 
  #^{:doc "P17 (*) Split a list into two parts; the length of the first part is given."
     :test (do (test= (split [] 3) [[] []])
               (test= (split '(a b c d e f g h i k) 3)
                      '((a b c) (d e f g h i k)))
               (test= (split '(a b c d e f g h i k) -3)
                      '(()(a b c d e f g h i k)))
               (test= (split '(a b c d e f g h i k) 100)
                      '((a b c d e f g h i k) () ))) }
; -----
  split
; -----
  ([coll pos]
     (let [len (count coll)]
       (cond 
        (<= len pos) (list coll [])
        (>= 0 pos) (list [] coll)
        :else
        (loop [coll coll, cnt pos, head [] ]
          (if (or (empty? coll) (zero? cnt))
            (list (reverse head) coll)
            (recur (rest coll)
                   (+ -1 cnt)
                   (cons (first coll) head))))))))

2008-10-03

ClojureでL-99 (P16 周期Nで要素を間引く)

| 18:34 | ClojureでL-99 (P16 周期Nで要素を間引く) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P16 周期Nで要素を間引く) - わだばLisperになる

このお題では、関数名がdropとなっているのですが、dropはClojureにも存在するので、my-dropとしています。

clojure/dropの動作としては、SRFIのdropと同じです。

Clojureの場合、名前空間を分けられるので、競合を防ぐことも可能だと思いますが、とりあえず今回は大元のdropも使っていて紛らわしいので、それはなしの方向で。

(defn 
  #^{:doc "P16 (**) Drop every N'th element from a list."
     :test (do (test= (my-drop [] 3) [])
               (test= (my-drop '(a b c d e f g h i k) -1)
                      '(a b c d e f g h i k))
               (test= (my-drop '(a b c d e f g h i k) 0)
                      '(a b c d e f g h i k))
               (test= (my-drop '(a b c d e f g h i k) 3)
                      '(a b d e g h k))) }
; ----
  my-drop
; ----
  ([coll n]
     (if (empty? coll)
       []
       (loop [coll coll, acc [] ]
         (if-let block (butlast (take n coll))
           (recur (drop n coll) (concat acc block))
           (concat acc coll))))))

2008-10-02

ClojureでL-99 (P15 要素を任意回数複製する)

| 18:37 | ClojureでL-99 (P15 要素を任意回数複製する) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P15 要素を任意回数複製する) - わだばLisperになる

この問題は、2つ星で難しめということになっているのですが、Prologだとこういうのは難しかったりするんでしょうか。

(defn 
  #^{:doc "P15 (**) Replicate the elements of a list a given number of times."
     :test (do (test= (repli [] -1) [])
               (test= (repli [1 2] 0) nil)
               (test= (repli [1 2] -1) nil)
               (test= (repli '(a b c) 3)
                      '(a a a b b b c c c))) }
; -----
  repli
; -----
  ([coll n]
     (reduce #(concat %1 (take n (repeat %2)))
             []
             coll)))

2008-10-01

ClojureでL-99 (P14 要素を2回繰り返す)

| 13:09 | ClojureでL-99 (P14 要素を2回繰り返す) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P14 要素を2回繰り返す) - わだばLisperになる

Clojureにも畳み込み用のreduceがあります。

(defn
  #^{:doc "P14 (*) Duplicate the elements of a list."
     :test (do (test= (dupli []) [])
               (test= (dupli '(a b c c d))
                      '(a a b b c c c c d d))) }
; -----
  dupli
; -----
  ([coll]
     (reduce #(concat % (list %2 %2))
             []
             coll)))

2008-09-30

ClojureでL-99 (P12 ランレングス圧縮 その3)

| 13:13 | ClojureでL-99 (P12 ランレングス圧縮 その3) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P12 ランレングス圧縮 その3) - わだばLisperになる

packの結果を加工せずに直接作成せよという問題。

Clojureのletは分割束縛の機能があるのでリスト分解 & 合成が楽です。

(defn 
  #^{:doc "P13 (**) Run-length encoding of a list (direct solution)."
     :test (do (test= (encode-direct []) [] )
               (test= (encode-direct [1]) [1] )
               (test= (encode-direct '(a a a a b c c a a d e e e e))
                      '((4 a) b (2 c) (2 a) d (4 e)))) }
; -------------
  encode-direct
; -------------
  ([coll]
     (if (empty? coll)
       []
       (loop [coll (concat coll (list (gensym))),
              tem (list 1 (gensym))
              acc [] ]
         (let [[car & cdr] coll, [cnt item] tem]
           (cond (empty? coll)
                 (rest (reverse acc))
                 ;; 
                 (= car item)
                 (recur cdr (list (+ 1 cnt) car) acc)
                 ;; 
                 :else
                 (recur cdr 
                        (list 1 car)
                        (cons (if (= 1 cnt)
                                item
                                tem)
                              acc))))))))

2008-09-29

ClojureでL-99 (P12 ランレングス圧縮の伸長)

| 11:54 | ClojureでL-99 (P12 ランレングス圧縮の伸長) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P12 ランレングス圧縮の伸長) - わだばLisperになる

repeatという、アイテムの繰り返しの遅延リストを作れるので、こういうのは割と簡潔に書けます。

(defn
  #^{:doc "P12 (**) Decode a run-length encoded list."
     :test (do (test= (decode []) [])
               (test= (decode '((4 a) b (2 c) (2 a) d (4 e)))
                      '(a a a a b c c a a d e e e e))) }
; ------
  decode
; ------
  ([coll]
     (if (empty? coll)
       []
       (mapcat #(if-let [n item] (and (list? %) %)
                  (take n (repeat item))
                  (list %))
               coll))))

2008-09-28

ClojureでL-99 (P11 ランレングス圧縮 その2)

| 14:37 | ClojureでL-99 (P11 ランレングス圧縮 その2) - わだばLisperになる を含むブックマーク はてなブックマーク - ClojureでL-99 (P11 ランレングス圧縮 その2) - わだばLisperになる

書くのを忘れてましたが、defnに:testを付けると定義した時点で:testの部分が実行されます。

ということで、適切なテストケースを付ければ、きっと便利だと思います。

ただ単にassertだけを書いたテストケースでは、最初に定義した時点で意図通り動かない場合、逆にいらっと来るかもしれません(笑)

また、lengthがないのはなんでだろうと思っていましたが、countという名前で存在していたことを発見。

うーん、確かにcountという名前も妥当ではありますが…。

length、len、size、count等、同じ機能でも方言によって色んな名前がありますね。

(defn
  #^{:doc "P11 (*) Modified run-length encoding."
     :test (do (test= (encode-modified '(a a a a b c c a a d e e e e))
                       '((4 a) b (2 c) (2 a) d (4 e)))
               (test= (encode-modified []) [])
               (test= (encode-modified [1]) [1]))}
; ---------------
  encode-modified
; ---------------
  ([coll]
     (if (empty? coll)
       []
       (map #(if (single? %)
               (first %)
               (list (count %) (first %)))
            (pack coll)))))

(defn single? [coll]
  (nil? (rest coll)))