M.Hiroi's Home Page

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home | 2021年 1月, 4月, 5月, 6月, 9月, 10月, 12月 ]

2021 年 12 月

12月31日

●大晦日

今年も残りわずかとなりました。この一年 M.Hiroi's Home Page を更新することができたのは、見に来てくださる皆様のおかげです。本当にありがとうございました。来年はどうなるかわかりませんが、これまでと同様に M.Hiroi's Home Page を続けることができればいいな、と思っております。

それでは、来たるべき新年が皆様にとって素晴らしい年でありますように。


2021 年 10 月

10月9日

●Infinity と Nan

下記ページへ移動しました。


10月3日

●C言語で複素数

下記ページへ移動しました。


2021 年 9 月

9月25日

●Julia で複素数

下記ページへ移動しました。


9月19日

●Python で複素数

下記ページへ移動しました。


9月12日

●Common Lisp で複素数

下記ページへ移動しました。


2021 年 6 月

6月20日

●ちょっと便利な高階関数

関数型言語のお話です。今回は Scheme のライブラリ SRFI-1 の中からちょっと便利な高階関数を紹介しましょう。

take-while pred xs => ys
drop-while pred xs => zs
span pred xs => [ys zs]
break pred xs => [ys zs]

take-while はリスト xs の先頭から述語 pred を満たす要素を取り出し、それをリスト ys に格納して返します。drop-while はリスト xs の先頭から述語 pred を満たす要素を取り除き、残ったリスト zs を返します。

span はリスト xs の先頭から述語 pred を満たす要素を取り出し、リスト ys に格納して返します。逆に、break は pred を満たさない要素を取り出し、リスト ys に格納して返します。span と break の返り値は多値で、2 番目の値 zs は残りのリストになります。

なお、Haskell のライブラリ Data.List にも同様の関数 takeWhile, dropWhile, span, break が用意されています。

Scheme の規格 R7RS-samll の範囲でプログラムを書くと次のようになります。

リスト : take-while, drop-while, span, break (R7RS-small)

(define (take-while pred xs)
  (if (or (null? xs)
          (not (pred (car xs))))
      '()
      (cons (car xs) (take-while pred (cdr xs)))))

(define (drop-while pred xs)
  (if (or (null? xs)
          (not (pred (car xs))))
      xs
      (drop-while pred (cdr xs))))

(define (span pred xs)
  (if (or (null? xs)
          (not (pred (car xs))))
      (values '() xs)
      (let-values (((ys zs) (span pred (cdr xs))))
        (values (cons (car xs) ys) zs))))

(define (break pred xs)
  (if (or (null? xs)
          (pred (car xs)))
      (values '() xs)
      (let-values (((ys zs) (break pred (cdr xs))))
        (values (cons (car xs) ys) zs))))

values は多値を返す関数、let-values は多値を受け取って、それらを局所変数にセットするマクロです。これらの関数やマクロについては拙作のページ Scheme 入門: 多値 をお読みくださいませ。プログラムは単純な再帰なので、多値のはかに難しいところはないと思います。

簡単な実行例を示します。

gosh[r7rs.user]> (take-while even? '(2 4 6 8 1 2 3 4 5))
(2 4 6 8)
gosh[r7rs.user]> (drop-while even? '(2 4 6 8 1 2 3 4 5))
(1 2 3 4 5)
gosh[r7rs.user]> (span even? '(2 4 6 8 1 2 3 4 5))
(2 4 6 8)
(1 2 3 4 5)
gosh[r7rs.user]> (break odd? '(2 4 6 8 1 2 3 4 5))
(2 4 6 8)
(1 2 3 4 5)

ところで、P-99: Ninety-Nine Prolog Problems P09 (pack) のような問題は、span を使うと簡単に解くことができます。Scheme でプログラムすると次のようになります。

リスト : pack の解答例 (Scheme R7RS-samll)

(define (pack xs)
  (if (null? xs)
      '()
      (let-values (((ys zs) (span (lambda (x) (eqv? (car xs) x)) xs)))
        (cons ys (pack zs)))))

;;; 別解
(define (pack1 xs)
  (if (null? xs)
      '()
      (let ((pred (lambda (x) (eqv? (car xs) x))))
        (cons (take-while pred xs) (pack1 (drop-while pred xs))))))

pack1 は take-while と drop-while を使ったプログラムです。簡単な実行例を示します。

gosh[r7rs.user]> (pack '(a b c d e))
((a) (b) (c) (d) (e))
gosh[r7rs.user]> (pack '(a a a b b c d d d d))
((a a a) (b b) (c) (d d d d))
gosh[r7rs.user]> (pack1 '(a b c d e))
((a) (b) (c) (d) (e))
gosh[r7rs.user]> (pack1 '(a a a b b c d d d d))
((a a a) (b b) (c) (d d d d))

Common Lisp と Scheme には多値がありますが、それがないプログラミング言語でも、リストやタプルを使って複数の値を返すことができます。たとえば、ISLisp で span と pack を定義すると次のようになります。

リスト : span と pack (ISLisp)

(defun span (pred xs)
  (if (or (null xs)
          (not (funcall pred (car xs))))
      (cons nil xs)
    (let ((ys (span pred (cdr xs))))
      (cons (cons (car xs) (car ys)) (cdr ys)))))

(defun pack (xs)
  (if (null xs)
      nil
    (let ((ys (span (lambda (x) (eql (car xs) x)) xs)))
      (cons (car ys) (pack (cdr ys))))))

取り出した要素を格納したリストを ys, 残りのリストを zs とすると、span xs はコンスセル (ys . zs) を返します。pack は span を呼び出して変数 ys にセットし、必要なリストを car と cdr で取り出します。簡単な実行例を示します。

ISLisp>(defun evenp (x) (= (mod x 2) 0))
EVENP
ISLisp>(span #'evenp '(2 4 6 8 1 2 3 4 5))
((2 4 6 8) 1 2 3 4 5)
ISLisp>(pack '(a b c d e))
((A) (B) (C) (D) (E))
ISLisp>(pack '(a a a b b c d d d d))
((A A A) (B B) (C) (D D D D))

もちろん、take-while, drop-while を使って pack を定義することもできます。興味のある方は拙作のページ ISLisp 入門: ISLisp ドリル 問題 28, 29 をお読みくださいませ。


2021 年 5 月

5月17日

●Lisp のマップ関数

Lisp のマッピングといえば、伝統的な関数に mapcar があります。Common Lisp にも mapcar がありますし、Scheme には map があります。Common Lisp と ISLisp には、ほかにも次に示すマップ関数が用意されています。

これらの関数の動作は定義をみるとよくわかります。簡単のため引数のリストを一つだけ受け取るマップ関数を作ってみましょう。プログラムは次のようになります。

リスト : マップ関数の簡単な定義 (mymap.lsp)

(defun mapcar1 (func xs)
  (if (null xs)
      nil
    (cons (funcall func (car xs)) (mapcar1 func (cdr xs)))))

(defun maplist1 (func xs)
  (if (null xs)
      nil
    (cons (funcall func xs) (maplist1 func (cdr xs)))))

(defun mapc1 (func xs)
  (labels ((iter (ys)
	     (cond
	      ((null ys) xs)
	      (t
	       (funcall func (car ys))
	       (iter (cdr ys))))))
    (iter xs)))

(defun mapl1 (func xs)
  (labels ((iter (ys)
	     (cond
	      ((null ys) xs)
	      (t
	       (funcall func ys)
	       (iter (cdr ys))))))
    (iter xs)))

(defun mapcan1 (func xs)
  (apply #'nconc (mapcar1 func xs)))

(defun mapcon1 (func xs)
  (apply #'nconc (maplist1 func xs)))

簡単な実行例を示します。動作確認は OK!-ISLisp [*1] と SBCL (Common Lisp) で行いました。

ISLisp>(load "mymap.lsp")
T
ISLisp>(mapcar1 #'identity '(1 2 3 4 5))
(1 2 3 4 5)
ISLisp>(maplist1 #'identity '(1 2 3 4 5))
((1 2 3 4 5) (2 3 4 5) (3 4 5) (4 5) (5))

ISLisp>(defun print (x) (format (standard-output) "~S~%" x))
PRINT
ISLisp>(mapc1 #'print '(1 2 3 4 5))
1
2
3
4
5
(1 2 3 4 5)
ISLisp>(mapl1 #'print '(1 2 3 4 5))
(1 2 3 4 5)
(2 3 4 5)
(3 4 5)
(4 5)
(5)
(1 2 3 4 5)

ISLisp>(mapcan1 (lambda (x) (list x x)) '(1 2 3 4 5))
(1 1 2 2 3 3 4 4 5 5)
ISLisp>(mapcon1 (lambda (x) (mapcar (lambda (y) (* y y)) x)) '(1 2 3 4 5))
(1 4 9 16 25 4 9 16 25 9 16 25 16 25 25)

mapcar は (car xs) でリストの要素を取り出して関数 func に渡しますが、maplist は xs をそのまま func に渡します。mapc と mapl は副作用のために用いられます。違いは mapcar と maplist と同じです。mapc は Scheme の for-each と同様の動作になります。なお、for-each の返り値は仕様で定義されていないので、処理系に依存します。

mapcan は mapcar の結果を nconc で連結する、つまり、マッピングの結果を平坦化する動作になります。いわゆる flatmap とか Haskell のconcatMap などの関数と同様の操作になります。mapcon は maplist の結果を平坦化します。mapcan と mapcon はリストの連結に nconc を使っているので、循環リストが生成されないように注意してください。たとえば、mapcon1 に恒等関数 identity を渡すと無限ループになります。

Common Lisp (ISLisp) の場合、mapcar を使うことが圧倒的に多いと思いますが、それ以外のマップ関数も便利なので、いろいろ使ってみてください。

-- note --------
[*1] Easy-ISLisp の場合、nconc は 2 引数の関数として定義されているので、このままでは動作しません。ISLisp の仕様書に nconc は定義されていないので、OK!-ISLisp や Easy-ISLisp の拡張なのだと思います。Common Lisp ライクな nconc の簡単な実装例を示します。

リスト : Common Lisp ライクな nconc の定義 (Easy-ISLisp)

(import "list")

(defun nconc-cl (&rest xss)
  (when
      xss
    (let ((zs (last-pair (car xss))))
      (dolist (xs (cdr xss) (car xss))
        (set-cdr xs zs)
        (setq zs (last-pair xs))))))
$ ./eisl
Easy-ISLisp Ver1.96
> (load "mymap.lsp")
T
> (defglobal a '(1 2 3))
A
> (defglobal b '(4 5 6 7))
B
> (defglobal c '(8 9))
C
> (nconc-cl)
NIL
> (nconc-cl a b c)
(1 2 3 4 5 6 7 8 9)
> a
(1 2 3 4 5 6 7 8 9)
> b
(4 5 6 7 8 9)
> c
(8 9)

> (mapcan1 (lambda (x) (list x x)) '(1 2 3 4 5))
(1 1 2 2 3 3 4 4 5 5)
> (mapcon1 (lambda (x) (mapcar (lambda (y) (* y y)) x)) '(1 2 3 4 5))
(1 4 9 16 25 4 9 16 25 9 16 25 16 25 25)

2021 年 4 月

4月24日

●Easy-ISLisp

笹川さん が開発中の ISLIsp 処理系 Easy-ISLisp ですが、開発は順調に進んでいてバージョンが 1.93 になりました。おめでとうございます。拙作のプログラム (リスト操作関数やソートなど) もライブラリに追加していただきました。ありがとうございます。拙作のプログラムはどうぞご自由にお使いくださいませ。

ISLisp には Common Lisp と同じく「伝統的なマクロ」があります。Common Lisp には便利なマクロが多数定義されていますが、ISLisp はコンパクトな仕様なので、Common Lisp でよく使われるマクロのほとんどは定義されていません。そこで、今回は簡単に実装できるマクロ (incf, decf, push, pop, loop, return, dotime, dolist) を作ってみました。興味のある方は以下のページをお読みください。

OK! ISLisp と Easy-ISLisp (インタプリタ) で動作確認しています。笹川さん、これからもがんばってください。


2021 年 1 月

1月1日

あけましておめでとうございます

旧年中は大変お世話になりました
本年も M.Hiroi's Home Page をよろしくお願い申し上げます


Copyright (C) 2021 Makoto Hiroi
All rights reserved.

[ Home ]