Common Lisp始めました

Common Lisp始めました💕

先生や友人から「憧れの言語はCommon LispC++」という話を聞きました。 どうして身の回りの強い人たちは揃いも揃って同じことを言うのだろうか(N=2)。 というわけで、まずは片方初めてみることにします。

Common Lispはカッコがいっぱいあるよくわからない言語、C++は暗記ゲーという偏見がありました。 どちらも習得には時間がかかりそうだが、知らなかった概念を早く学べるのはどちらだろうと考え、 Common Lispを選択することにした。 f:id:mi12cp:20180930070200j:plain 以下、やったことをだらだらと書いているだけなので、記事としての有用性は期待しないでください。

インストール

Mac環境では

$ brew instal clisp

で一発。 REPLの実行は$ clisp, ファイルの実行は$clisp example.lisp

とりあえずやってみる

まずは他人のコードを見よう見まねでAtCoder Beginner ContestのA, B問題を解いてみる。

ABC102 A - Multiple of 2 and N

入力: 数字一つ、出力: 数字ひとつの簡単な例。 多分最初に書いたのがこれかなあ。他人のコードをほぼ丸写しになったと思う。

; A - Multiple of 2 and N
; https://beta.atcoder.jp/contests/abc102/tasks/abc102_a

(defun solve (n)
  (if (= (mod n 2) 0)
    n
    (* n 2)))

(format t "~A" (solve (read)))

だいたいこれを見れば基本的な構文がイメージがつく。

  • 関数と引数のペアをカッコでくくる
  • 全て前置記法で書かれる。そのため演算子の優先順位など気にしなくてよい(そもそも演算子という概念があるのかわからないが)
  • インデントや改行に規定はないが、おそらく次のような慣習があると思われる
    • (で終わる行は書かない
    • )で始まる行は書かない
    • 同じ関数に対する引数のリストは横に並べても良いし、縦に並べても良い。縦に並べる時はインデントを揃える

ABC110 B - 1 Dimensional World's Tale

早速、別の問題を試してみる。

; B - 1 Dimensional World's Tale
; https://beta.atcoder.jp/contests/abc110/tasks/abc110_b
 
(defun split-and-parse-integer (string)
  (loop for i = 0 then (1+ j)
    as j = (position #\Space string :start i)
    collect (parse-integer (subseq string i j))
    while j))
 
(defun input-format ()
  (let ((n (read)) (m (read)) (x (read)) (y (read)))
    (let ((xs (split-and-parse-integer (read-line)))
          (ys (split-and-parse-integer (read-line))))
      (let ((xx (cons x xs))
            (yy (cons y ys)))
        (list xx yy)))))
 
(defun solve (lis)
  (let ((xx (car lis))
        (yy (car (cdr lis))))
    (let ((biggest-x  (car (sort (copy-list xx) #'>)))
          (smallest-y (car (sort (copy-list yy) #'<))))
      (if (< biggest-x smallest-y)
          "No War"
          "War"))))
 
(format t "~A" (solve (input-format)))

入力例が若干複雑であった。 split-and-parse-integerは入力の一行の文字列をスペース区切りにし、数字のリストにするもの。 loopの書き方が分からなかったので、ネットで適当に拾ったものを使った。

lispletを初めて知った。letの基本的な構文は下記の通り

(let ((a 2)
      (b 3))
  (+ a b))

変数のスコープの指定を関数のように書くのが面白い。 このletの第二引数の(+ a b)の部分がそのまま(let ...)を評価した値として返る。 つまりletは式で、他の言語でいう即時関数のようなものだ。

解答を見返すと若干冗長な部分や雑な部分があった。 input-formatの中のletは一つ減らせるし、 リストの中の最大の要素を求めるのがわからずソートしたり、 cadrのような書き方を知らなかったりしていますね。

読んだ

1~14章の基本的な構文と、14章の関数型の部分を読んだ これを買った日にリスプモンスターが夢に出てきました。

f:id:mi12cp:20180930070200j:plain

おまけ

ABC109 C - Skip

解いた問題だけ貼るのもなんなので、この記事を書いている最中に一問解いてみよう。 と思ったらTLEを出してしまった。 あとで直しまーす。

; C - Skip
; https://abc109.contest.atcoder.jp/tasks/abc109_c

(defun split-and-parse-integer (string)
  (loop for i = 0 then (1+ j)
    as j = (position #\Space string :start i)
    collect (parse-integer (subseq string i j))
    while j))

(defun input-format ()
  (let ((n (read)) (x (read))
        (xs (split-and-parse-integer (read-line))))
    (cons x xs)))

(defun intervals (as)
  (if (cdr as)
    (cons (- (cadr as) (car as)) (intervals (cdr as)))
    nil))

(defun mygcd (a b)
  (if (= b 0) a (gcd b (mod a b))))

(defun solve (xx)
   (let* ((sxs (sort (copy-list xx) #'<))
          (ixs (intervals sxs)))
      (reduce #'mygcd ixs)))

(format t "~A" (solve (input-format)))

結論

Lispガリガリ積み重ねていく感じが楽しいですね。 再帰とか関数型っぽい書き方を少し知って入れば導入はできるなという感じ。