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-02-23

ArcでL-99 (P19 指定した位置でローテーションさせる)

| 23:56 | ArcでL-99 (P19 指定した位置でローテーションさせる) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P19 指定した位置でローテーションさせる) - わだばLisperになる

今回は、リストの指定した位置でローテーションさせるというお題です。

ヒントとしては、P17を参照せよとのこと。

また、インデックスはマイナスの数値も扱えるようにするみたいです。

(rotate '(a b c d e f g h) 3)
;=> (d e f g h a b c)

(rotate '(a b c d e f g h) -2)
;=> (g h a b c d e f)

(def rotate (lst pos)
  (let pos (mod pos len.lst)
     ((afn (lst acc cnt)
	(if (or no.lst (is pos cnt))
	    (join lst rev.acc)
	    (self cdr.lst
		  (cons car.lst acc)
		  (+ 1 cnt))))
      lst () 0)))

再帰が難しいのか、それとも考え方が難しいのか

| 03:39 | 再帰が難しいのか、それとも考え方が難しいのか - わだばLisperになる を含むブックマーク はてなブックマーク - 再帰が難しいのか、それとも考え方が難しいのか - わだばLisperになる

再帰は難しいと良く言われます。自分も再帰を使ったアプローチでは、何だかこんがらがることが多いです。

しかし、良く良く考えてみると、再帰が難しいというよりも、問題を解く方法がややこしいだけで、それをもって再帰がややこしいというのは何だか変な気がしてきました。

再帰するということと、問題に対するアプローチは別の物なのに、それが一緒くたにされて、「再帰は難しい」とされているような。

例えば、リストの長さを調べるlenという関数を作ってみるとします。

まず、この問題に対してアプローチは色々取れると思うのですが、

1. 要素を勘定していって、最後に勘定した数を返す

2. リスト中の要素を全部1に置き換えて、最後に内容を全部足し算する

3. リスト中の要素を全部1を足す関数に入れ子状に置き換えて、その一番内側の関数に0という引数を与える。

等々あるかと思います。

自分が単純に考えると、やはり1番のアプローチが一番最初に思い付くのですが、再帰の入門解説等では、一番単純なものとして

(defun len (lst)
  (if (null lst)
      0
      (+ 1 (len (cdr lst)))))

のようなものが取り上げられることが多いと思います。これは、

(defun len (lst)
  (if (null lst)
      0
      ((lambda (x) (+ 1 x)) (len (cdr lst)))))

ということで、考え方としては、3番目のものに該当するかと思いますが、再帰云々の前に、考え方が既にややこしいんじゃないかと思うんですよね。

それで、1番目のアプローチですが、これは再帰でも書けて

(defun len (lst acc)
  (if (null lst)
      acc
      (len (cdr lst)
	   (+ 1 acc))))

のようになるかと思います。

リストを一個ずつ手繰って行く部分と、合計を溜めて行くところがあって、リストが空になったら終了。最後に溜めていた合計を返すというもの。

2番目のアプローチも、1番目に似ていますが、合計を溜めて置く代わりに要素を1に置き換えたリストを溜めていって、最後に+という関数をリストに適用します。

(defun len (lst acc)
  (if (null lst)
      (apply #'+ acc)
      (len (cdr lst)
	   (cons 1 acc))))

ということで、再帰を使ったからといって難しくなる訳ではないのではないかと。

1番目と2番目のアプローチは普通のループに書き直すことも容易で、末尾再帰とも呼ばれ、ループ自体が再帰の特殊形であるということもなんとなく分かります。

逆に考え方としては分かりやすいと思われているループを使ったアプローチならば何でも簡単かというと、そうでもなく、例えば、lenを拡張して、中身にリストがある場合ば、中身の個数も全部数えるような、super-lengthというものを作るとします。

これもアプローチは色々あると思うのですが、

1. 要素がリストでないならば、1を足し、リストならば、今迄計算した内容をどこかに退避させて、そのリストを調べ、その合計を退避した内容と合計し…を繰り返す。

2. リスト中の要素を全部1を足す関数に置き換え最後に0という引数を与える。要素がリストの場合、そのリストに自分自身を適用する。

のようなものがあると思います。1はループで表現可能で、2は自分自身を再度呼び出すので、再帰でアプローチすると簡単です。

つまり、当然といえば当然ですが、問題というかデータ構造自体が再帰的な場合は、ループで考えることの方がややこしくなってきます。

(super-length '(1 2 3 (4 5 6 ((((((((7 8)9)10)))))))11))
;=> 11

;; 再帰で
(defun super-length (lst)
  (cond ((null lst) 0)
	((atom (car lst)) 
	 (+ 1 (super-length (cdr lst))))
	(:else 
	 (+ (super-length (car lst)) 
	    (super-length (cdr lst))))))

;; ループで
(defun super-length (lst)
  (prog (l stack len)
	(setq l lst)
	(setq len 0)
     L  (when (null l)
	  (if (null stack)
	      (return len)
	      (setq l (pop stack))))
	(if (atom (car l))
	    (incf len)
	    (push (car l) stack))
	(pop l)
	(go L)))

;; ループで その2
(defun super-length (lst)
  (loop :with l := lst :and stack :and len := 0
        :if (null l)
           :if (null stack)
              :return len
           :else
              :do (setq l (pop stack))
           :end
        :else
           :if (atom (car l))
              :do (pop l) 
                  (incf len)
           :else
              :do (push (pop l) stack)
           :end
        :end))

;; 末尾再帰で
(defun super-length (lst &optional (len 0) stack)
  (if (null lst)
      (if (null stack)
	  len
	  (super-length (car stack) len (cdr stack)))
      (if (atom (car lst)) 
	  (super-length (cdr lst) (1+ len) stack)
	  (super-length (cdr lst) len (cons (car lst) stack)))))

以上、難しさは、問題のアプローチに左右されるものであり「再帰」という概念とは別個のものなんじゃないかなあと、適当に考えたことを書いてみましたが、なんとなく纏め切れずに終わります…。

ArcでL-99 (P18 指定した範囲を切り出す)

| 00:26 | ArcでL-99 (P18 指定した範囲を切り出す) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P18 指定した範囲を切り出す) - わだばLisperになる

今回は、リストの指定した範囲を切り出すというお題です。

CLでいうところのsubseqの作成ですね。

Arcもこの前までは、subseqだったんですが、cutって名前に変更になっちゃったみたいです。

マイナスのインデックスは、配列の後から数えた位置になります。また、配列のサイズより大きい数値でもエラーにはなりません。

(def slice (lst start end)
  (unless (<= 0 start end (len lst))
    (err "The bounding indices are bad for a sequence of length."))
  ((afn (lst acc cnt)
	(if (or no.lst (< end cnt))
	    rev.acc
	    (self cdr.lst
		  (if (<= start cnt end)
		      (cons car.lst acc)
		      acc)
		  (+ 1 cnt))))
   lst () 1))

(slice '(a b c d e f g h i k) 3 7)
;=> (c d e f g)

(cut '(a b c d e f g h i k) 3 7)  
;=> (d e f g)
; 0オリジン

(cut '(a b c d e f g h i k) 3 -3)
;=> (d e f g)