ITコンサルの日常

ITコンサル会社に勤務する普通のITエンジニアの日常です。

「ANSI Common Lisp」3章読了

リストに関する章。LispはLISt Processorの略なので、かなり重要と思われます。

コンス

car(先頭要素へのポインタ)とcdr(残りの要素へのポインタ)の組をコンスというらしい。
Haskell的に書けば、xxs@(x:xs)記法(アズパターンという名前らしい)を使って、

main = putStrLn $ printCons [1..3]

printCons::[Int] -> String
printCons xxs@(x:xs) = "cons = " ++ (show xxs) ++ ", car = " ++ (show x) ++ ", c
dr = " ++ (show xs)

結果はこう。

cons = [1,2,3], car = 1, cdr = [2,3]

こんなイメージなのではないかと思います。

コンスとアトムとリスト

コンスでないものは全てアトムであるが、nilは例外。
表にまとめるとこんな感じみたい。

- consp listp atom
nil nil T T
1 nil nil T
'(a b c) T T nil

(eql (cons 'a nil) (cons 'a nil))はnil

なんかJavaの"a" == "a"はfalseっていわれているのと同じっぽい。
と思ったら、

public class eql
{
        public static void main(String[] args)
        {
                System.out.println("a" == "a");
        }
}

はtrueなんですね。
なんでかと思ったら、言語仕様に

文字列リテラルは,クラス String(4.3.3,20.12)のインスタンス(4.3.1,12.5)への参照(4.3)とする。オブジェクト String は,一定の値をもつ。文字列リテラル,又はもっと一般的には,定数式の値とする文字列(15.27)は,メソッド String.intern(20.12.47)を使って,一意なインスタンスを共有するために収容される。

とか書いてあって、要は同じ文字列リテラルは同じインスタンスになるように作られるということらしい。


こういうコードを動かすと分かるかもしれない。

public class eql
{
        public static void main(String[] args)
        {
                String a = new String("abc");
                String b = new String("abc");
                System.out.println(a == b);

                a = a.intern();
                b = b.intern();
                System.out.println(a == b);
        }
}

結果はこう。

false
true

ちなみにJavaのequalsには、Lispのequal関数が相当するらしい。

(equal (cons 'a nil) (cons 'a nil))

結果はTです。

なぜLispにはポインタがないか

Lispがポインタをもたない理由は全ての値が概念上、ポインタであるからである。

こういうプログラムを書いてみる。

(setf x '(a b c))
(setf y x)

(format t "(eql x y) = ~A" (eql x y))

(setf x (remove 'b x))

(format t "x = ~A, y = ~A" x y)

結果はこう。

* Warning:  Declaring X special.

(A B C)
* Warning:  Declaring Y special.

(A B C)
* (eql x y) = T
NIL
* 
(A C)
* x = (A C), y = (A B C)
NIL
* 

(eql x y)がTになるのは、本書中にもある通り想定内ですが、
xから'Bをremoveした後のyは、(A C)になって欲しかったなあ。
と思ったけど、removeした結果は元のリスト(A B C)に副作用を及ぼさず、別のリストを新しく作って返すから、この結果でいいのか。
サンプルがまずいなあ。気づいたけどとりあえずこのまま載せておく。


ポインタってところでC言語でも同じようなことをやろうと思ってみた。

#include <stdio.h>

main()
{
        char* x = "abc";
        char* y = x;

        x = "ac";

        printf("x = %s, y = %s\n", x, y);
}

結果はこう。

x = ac, y = abc

じゃあ、xが変わるとyも変わるようなサンプルも作ってみようと思った。

#include <stdio.h>
#include <string.h>

main()
{
        char x[4];
        strncpy(x, "abc", 3);
        char* y = x;

        *(x+2) = '\0';

        printf("x = %s, y = %s\n", x, y);
}

char* x = "abc";
って定義すると、読み取り専用になるらしく、Segmentation faultで落ちる。
ので、strncpyするようにしてみた。


結果はこう。

x = ab, y = ab

リストを作る

copy-list関数を使うと、ポインタのコピーでなく、いわゆる値のコピーになるらしい。

(setf x '(a b c))
(setf y (copy-list x))

(eql x y)
(equal x y)

結果はこう。

* 
NIL
* 
T
* 

ランレングス符号化

何も考えずにHaskellに移植してみる。
が、型エラーでハマったので、弱気にIntリストのみバージョンになってしまった。。

compress::[Int] -> [[Int]]
compress [] = [[]]
compress (x:xs) = compr x 1 xs

compr::Int -> Int -> [Int] -> [[Int]]
compr elt n [] = [n_elts elt n]
compr elt n lst = let (next:cdr) = lst
                  in if elt == next
                     then
                       compr elt (n+1) cdr
                     else
                       [n_elts elt n] ++ compr next 1 cdr

n_elts::Int -> Int -> [Int]
n_elts elt n = [n,elt]

uncompress::[[Int]] -> [Int]
uncompress [] = []
uncompress (x:xs) = (list_of (head x) (last x)) ++ uncompress xs

list_of::Int -> Int -> [Int]
list_of 0 _ = []
list_of n elt = [elt] ++ list_of (n-1) elt

donothing = uncompress . compress

main = do print $ compress [1,1,1,0,1,0,0,0,0,1]
          print $ uncompress $ compress [1,1,1,0,1,0,0,0,0,1]
          print $ donothing [1,1,1,0,1,0,0,0,0,1]

mainの3行目はなんとなく関数合成してみた。
結果はこう。

[[3,1],[1,0],[1,1],[4,0],[1,1]]
[1,1,1,0,1,0,0,0,0,1]
[1,1,1,0,1,0,0,0,0,1]

出来てるっぽい。

アクセス関数

リストの3番目の要素にアクセスできるthird関数を最初のころに紹介しましたが、これのバリエーションでfirstからtenthまであるみたいです。

(first '(a b c d e f g h i j k l))
(second '(a b c d e f g h i j k l))
(third '(a b c d e f g h i j k l))
(fourth '(a b c d e f g h i j k l))
(fifth '(a b c d e f g h i j k l))
(sixth '(a b c d e f g h i j k l))
(seventh '(a b c d e f g h i j k l))
(eighth '(a b c d e f g h i j k l))
(ninth '(a b c d e f g h i j k l))
(tenth '(a b c d e f g h i j k l))

結果はこう。

* 
A
* 
B
* 
C
* 
D
* 
E
* 
F
* 
G
* 
H
* 
I
* 
J
* 

さらにn番目のcarを取り出すnth関数と、n番目のcdrを取り出すnthcdr関数もあるらしい。

(defun print-nth-and-nthcdr (n lst)
  (format t "nth = ~A, nthcdr = ~A~%" (nth n lst) (nthcdr n lst)))

(defun main (n)
  (if (> n 0)
    (or (print-nth-and-nthcdr (- n 1) '(a b c d e))
        (main (- n 1)))
    nil))

(main 6)

結果はこう。

* 
PRINT-NTH-AND-NTHCDR
* 
MAIN
* nth = NIL, nthcdr = NIL
nth = E, nthcdr = (E)
nth = D, nthcdr = (D E)
nth = C, nthcdr = (C D E)
nth = B, nthcdr = (B C D E)
nth = A, nthcdr = (A B C D E)
NIL
* 

マッピング関数

mapcar=Haskellのmapみたいなやつですか。

(mapcar (lambda (x) (+ x 1)) '(1 2 3))

結果はこう。

* 
(2 3 4)
* 

maplistってのもある、これはmapcarが各nthに対して作用したのに対して、各nthcdrに作用する。

(maplist (lambda (x) x) '(a b c))

結果はこう。

* 
((A B C) (B C) (C))
* 

HaskellのList.tailsに似てますね。

import List

main = print $ tails "abc"

結果はこう。

["abc","bc","c",""]

空リストが含まれるからちょっと違うか。

コンスは二分木(ツリー)でもある

なるほどと。
carが左側でcdrが右側。
アトムが出てきたら葉っぱで、コンスなら枝になってさらに二つに分かれるというわけですね。

リストは集合でもある

; 和集合
(union '(a b c) '(c b s))

; 積集合
(intersection '(a b c) '(b b c))

; 差集合
(set-difference '(a b c d e) '(b e))

やっとコメントの付け方が分かった(;以降がコメント)
結果はこう。

* 
(A C B S)
* 
(C B)
* 
(D C A)
* 

Haskellでは、Listモジュールのunion / intersect / \\がそれぞれ対応しますね。

import List

main = do print $ union "abc" "cbs"
          print $ intersect "abc" "bbc"
          print $ "abcde" \\ "be"

結果はこう。

"abcs"
"bc"
"acd"

シークエンス

配列とはちょっと違うらしい。
長さを取得するlength、シークエンスの一部をコピーするsubseq、並びを逆転させるreverseなどの関数が使えるらしい。


シークエンスの並び順を入れ替えるsort関数もあるが、破壊的(rubyでいう!付きのメソッド)なので注意とのこと。

(setf x '(3 1 2))

(sort x #'>)

(format t "~A~%" x)

結果はこう。

* Warning:  Declaring X special.

(3 1 2)
* 
(3 2 1)
* (3 2 1)
NIL
* 

ソートする前のxは'(3 1 2)だったのに対し、ソートした後のxは'(3 2 1)になっていて変わっています。

リストはスタックでもある

(setf x '(a b c))

(push 'd x)

(format t "pushed list = ~A" x)

(setf poped (pop x))

(format t "poped = ~A, poped list = ~A" poped x)

結果はこう。

* Warning:  Declaring X special.

(A B C)
* 
(D A B C)
* pushed list = (D A B C)
NIL
* Warning:  Declaring POPED special.

D
* poped = D, poped list = (A B C)
NIL
* 

pushもpopも破壊的な関数ですね。


GHCの標準ライブラリにはStackってないんですね。
リストの演算子を使って割と簡単に時相できます。

push::a -> [a] -> [a]
push x xs = x:xs

pop::[a] -> (a, [a])
pop (x:xs) = (x, xs)

peek::[a] -> a
peek (x:xs) = x

isEmpty::[a] -> Bool
isEmpty [] = True
isEmpty _ = False

main = do print $ push 'D' "ABC"
          print $ pop "DABC"
          print $ peek "ABC"
          print $ isEmpty "ABC"
          print $ isEmpty []

結果はこう。

"DABC"
('D',"ABC")
'A'
False
True

data宣言使ったバージョンは、「ふつうのHaskellプログラミング」に載ってますね。

ドットリスト

真リストはnilか、cdr部が真リストであるコンスである。
真リストでないコンスはドットリスト(dotted list)と呼ばれる。

ということですが、どうもHaskellでいうところのtupleに近い概念のような気がします。

* (setf x (cons 'a 'b))
Warning:  Declaring X special.

(A . B)
* (car x)

A
* (cdr x)

B
* (first x)

A
* (second x)

Type-error in KERNEL::OBJECT-NOT-LIST-ERROR-HANDLER:  B is not of type LIST
   [Condition of type TYPE-ERROR]

Restarts:
  0: [ABORT] Return to Top-Level.

Debug  (type H for help)

(SECOND (A . B))
Source: Error finding source: 
Error in function DEBUG::GET-FILE-TOP-LEVEL-FORM:  Source file no longer exists:
  target:code/list.lisp.
0] Q

* 

ドットリストにはfirstは使えても、secondは使えないのですね。二つで一つの要素とみなされているからでしょうか。

連想リスト

他の言語でHashとか連想配列とか言われているやつですね。

(setf trans '((+ . "add") (- . "subtract")))

(assoc '+ trans)

(assoc '* trans)

結果はこう。

* Warning:  Declaring TRANS special.

((+ . "add") (- . "subtract"))
* 
(+ . "add")
* 
NIL
* 

こうしてみると、リストがあれば他の様々なデータ型がつくり出せることが分かりますね。