Lisp 風のシンプルな連結リストライブラリ slist を作成します。Lisp のリストは複数の「コンスセル (cons cell)」を連結したものです。ひとつのコンスセルには、データを格納する CAR (カー) という場所と、次のセルを連結する CDR (クダー) という場所からなっています。次の図を見てください。
CAR CDR CAR CDR
┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼→終端 (nil)
└┼┴─┘ └┼┴─┘
↓ ↓
１ ２
図 : リストの構造
上図では、コンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。上図の例では、先頭のコンスセルの CAR には 1 が格納され、CDR は次のコンスセルと連結しています。2 番目のコンスセルには CAR に 2 というデータが格納されています。このあとに接続されるコンスセルはもうないので、CDR にはリストの終わりを示す特別なデータ (nil) が格納されます。このようなリストを Lisp では (1 2) と表記します。
Lisp のリストは CAR にリストを格納して、リストを入れ子にすることができます。次の図を見てください。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│ ／ : nil
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ │ │
１ │ │
│ ↓
│ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・│・┼→│・│・┼→│・│／│
│ └┼┴─┘ └┼┴─┘ └┼┴─┘
│ ↓ ↓ ↓
│ ３ １２ １３
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
２ １０ １１
図 : リストの階層構造
上図のリストを Lisp で記述すると (1 (2 10 11) (3 12 13)) になります。なお、Lisp のリストは CDR 部にコンスセルと nil だけではなく他の値を格納することができますが、今回はプログラムを簡単にするため、CDR 部にはコンスセルと nil だけしか格納できないものとします。
今回はコンスセルを次のように定義します。
リスト : セルの定義
type Any interface{}
type Cell struct {
item Any
next *Cell
}
セルを生成する関数 Cons, リストの先頭要素を取り出す関数 Car, リストの先頭要素を取り除く関数 Cdr を定義してください。なお、リストの終端は nil で表し、Car と Cdr は引数が nil であれば nil を返すものとします。
func Cons(x Any, xs *Cell) *Cell func Car(xs *Cell) Any func Cdr(xs *Cell) *Cell
Cons(1, nil) => (1) Cons(2, Cons(1, nil)) => (2 1) Car(Cons(1, nil)) => 1 Cdr(Cons(1, nil)) => () Car(Cons(2, Cons(1, nil)) => 2 Cdr(Cons(2, Cons(1, nil)) => (1)
引数 x がセル以外であれば真を返す述語 Atom, x がリスト (nil も含む) であれば真を返す述語 Listp, x がセルであれば真を返す述語 Consp, x が空リスト (nil) であれば真を返す述語 Null を定義してください。
func Atom(x Any) bool func Listp(x Any) bool func Consp(x Any) bool func Null(x *Cell) bool
Atom(1) => true Atom(Cons(1, nil)) => false Listp(1) => false Listp(Cons(1, nil)) => true Listp(Cdr(Cons(1, nil))) => true Consp(1) => false Consp(Cons(1, nil)) => true Consp(Cdr(Cons(1, nil))) => false Null(Cdr(Cons(1, nil))) => true Null(Cdr(Cons(2, Cons(1, nil)))) => false
リスト xs を Lisp 風に表示する関数 Print とリストを文字列に変換して返す関数 Sprint を定義してください。
func Print(xs Any) func Sprint(xs Any) string
Sprint(Cons(1, nil)) => "(1)" Sprint(Cons(3, Cons(2, Cons(1, nil)))) => "(3 2 1)" Sprint(Cons(Cons(3, nil), Cons(Cons(2, nil), Cons(Cons(1, nil), nil)))) => "((3) (2) (1))"
可変個の引数をリストに格納して返す関数 List, リスト xs の n 番目の要素を参照する関数 Nth, 2 つのリスト xs, ys を連結する関数 Append, リスト xs を反転する関数 Reverse, リスト xs の長さ (要素の個数) を求める関数 Length を定義してください。
func List(xs ... Any) *Cell func Nth(xs *Cell, n int) (Any, bool) func Append(xs, ys *Cell) *Cell func Reverse(xs *Cell) *Cell func Length(xs *Cell) int
List(1, 2, 3, 4) => (1 2 3 4) Nth(List(1, 2, 3, 4), 0) => 1 true Nth(List(1, 2, 3, 4), 3) => 4 true Nth(List(1, 2, 3, 4), 4) => <nil> true Append(List(1, 2, 3), List(4, 5, 6)) => (1 2 3 4 5 6) Reverse(List(1, 2, 3, 4, 5)) => (5 4 3 2 1) Length(List(1, 2, 3, 4, 5)) => 5
リスト xs の先頭から n 個の要素を取り出す関数 Take, xs の先頭から n 個の要素を取り除く関数 Drop, xs の後ろから n 個の要素を取り出す関数 Last, xs の後ろから n 個の要素を取り除く関数 ButLast を定義してください。
func Take(xs *Cell, n int) *Cell func Drop(xs *Cell, n int) *Cell func Last(xs *Cell, n int) *Cell func ButLast(xs *Cell, n int) *Cell
Take(List(1, 2, 3, 4), 0) => () Take(List(1, 2, 3, 4), 2) => (1 2) Take(List(1, 2, 3, 4), 4) => (1 2 3 4) Drop(List(1, 2, 3, 4), 0) => (1 2 3 4) Drop(List(1, 2, 3, 4), 2) => (3 4) Drop(List(1, 2, 3, 4), 4) => () |
Last(List(1, 2, 3, 4, 5), 1) => (5) Last(List(1, 2, 3, 4, 5), 2) => (4 5) Last(List(1, 2, 3, 4, 5), 4) => (2 3 4 5) ButLast(List(1, 2, 3, 4, 5), 1) => (1 2 3 4) ButLast(List(1, 2, 3, 4, 5), 2) => (1 2 3) ButLast(List(1, 2, 3, 4, 5), 4) => (1) |
引数 xs, ys の等値を判定する述語 Equal を定義してください。
func Equal(xs, ys Any) bool
引数 xs, ys の型がインターフェースの場合、実際の値が演算子 == で比較できる型であれば、== で等値を判定することができます。xs と ys の型が異なるときは false になります。xs と ys がリストの場合、型はポインタになるので、== はアドレスを比較して等値を判定します。リストの内容を比較するわけではないので、== で等値判定することはできません。
この場合、リストの要素同士が等しいかチェックしていきます。リストは入れ子にすることができるので、要素のチェックは Equal を再帰呼び出しすると簡単です。すべての要素が Equal を満たしていれば、2 つのリストは等しいことになります。
Equal(1, 1) => true Equal(1, 1.0) => false Equal(List(1, 2, 3), List(1, 2, 3)) => true Equal(List(Cons(1, nil), 2, 3), List(Cons(1, nil), 2, 3)) => true Equal(List(Cons(1, nil), 2, 3), List(Cons(5, nil), 2, 3)) => false
高階関数 MapCar, Filter, Foldl, Foldr, ForEach を定義してください。
func MapCar(f func(x Any) Any, xs *Cell) *Cell func Filter(f func(x Any) bool, xs *Cell) *Cell func Foldl(f func(a, x Any) Any, g Any, xs *Cell) Any func Foldr(f func(x, a Any) Any, g Any, xs *Cell) Any func ForEach(f func(x Any), xs *Cell)
times := func(x Any) Any { return x.(int) * 2 }
MapCar(times, List(1, 2, 3, 4, 5)) => (2 4 6 8 10)
isOdd := func(x Any) bool { return x.(int) % 2 != 0 }
Filter(isOdd, List(1, 2, 3, 4, 5)) => (1 3 5)
add := func(x, y Any) Any { return x.(int) + y.(int) }
Foldl(add, 0, List(1, 2, 3, 4, 5)) => 15
Foldr(add, 0, List(1, 2, 3, 4, 5)) => 15
var Nil *Cell
xcons := func(x, y Any) Any { return Cons(y, x.(*Cell)) }
Foldl(xcons, Nil, List(1, 2, 3, 4, 5)) => (5 4 3 2 1)
kons := func(x, y Any) Any { return Cons(x, y.(*Cell)) }
Foldr(kons, Nil, List(1, 2, 3, 4, 5)) => (1 2 3 4 5)
ForEach(func(x Any){ fmt.Println(x) }, List(1,2,3,4,5)) => (画面に出力)
1
2
3
4
5
リスト xs から x を探索する関数 Member, Find, Position, x と等しい要素をカウントする関数 Count, 高階関数 MemberIf, FindIf, PositionIf, CountIf を定義してください。
func Member(x Any, xs *Cell) *Cell func MemberIf(f func(x Any) bool, xs *Cell) *Cell func Find(x Any, xs *Cell) bool func FindIf(f func(x Any) bool, xs *Cell) (Any, bool) func Position(x Any, xs *Cell) int func PositionIf(f func(x Any) bool, xs *Cell) int func Count(x Any, xs *Cell) int func CountIf(f func(x Any) bool, xs *Cell) int
Member は xs の中に x が含まれているか調べます。もし見つからなければ nil を返します。見つけた場合は、それ以降のリストの残りを返します。Find は x を見つけたら true を返します。Position は x を見つけたらその位置を、見つからない場合は -1 を返します。
xs := List(1, 2, 3, 4, 5)
Member(1, xs) => (1 2 3 4 5)
Member(3, xs) => (3 4 5)
Member(5, xs) => (5)
Member(6, xs) => ()
isEven := func(x Any) bool { return x.(int) % 2 == 0 }
MemberIf(isEven, xs) => (2 3 4 5)
Find(3, xs) => true
Find(6, xs) => false
FindIf(isEven, xs) => 2 true
Position(3, xs) => 2
PositionIf(isEven, xs) => 1
Count(3, xs) => 1
CountIf(isEven, xs) => 2
リスト xs から x と等しい要素を削除する関数 Remove と、述語 f が真を返す要素を削除する高階関数 RemoveIf, x と等しい要素を y と置換する関数 Substitute, 述語 f が真を返す要素を引数 y と置換する関数 SubstituteIf を定義してください。
func Remove(x Any, xs *Cell) *Cell func RemoveIf(f func(x Any) bool, xs *Cell) *Cell func Substitute(x, y Any, xs *Cell) *Cell func SubstituteIf(f func(x Any) bool, y Any, xs *Cell) *Cell
xs := List(1, 2, 3, 4, 5)
Remove(3, xs) => (1 2 4 5)
isEven := func(x Any) bool { return x.(int) % 2 == 0 }
RemoveIf(isEven, xs) => (1 3 5)
Substitute(3, 30, xs) => (1 2 30 4 5)
SubstituteIf(isEven, 100, xs) => (1 100 3 100 5)
2 つのリスト xs, ys を受け取り、同じ位置にある要素をリストにまとめ、それをリストに格納して返す関数 Zip, Zip したリストを元に戻す関数 UnZip, 連想リスト xs からキー x とその値を探索する関数 Assoc, 連想リスト xs から述語 f が真を返すキーと値を求める関数 AssocIf を定義してください。
func Zip(xs, ys *Cell) *Cell func UnZip(xs *Cell) (*Cell, *Cell) func Assoc(x Any, xs *Cell) *Cell func AssocIf(f func(x Any) bool, xs *Cell) *Cell
xs := Zip(List("a", "b", "c"), List(4, 5, 6))
xs => ((a 4) (b 5) (c 6))
UnZip(xs) => (a b c) (4 5 6)
Assoc("a", xs) => (a 4)
Assoc("d", xs) => ()
AssocIf(func(x Any) bool { return x.(string) == "c" }, xs) => (c 6)
リスト : リストの基本操作
// セルの生成
func Cons(x Any, xs *Cell) *Cell {
return &Cell{x, xs}
}
// 要素を取り出す
func Car(xs *Cell) Any {
if xs == nil { return nil }
return xs.item
}
// 先頭要素を取り除く
func Cdr(xs *Cell) *Cell {
if xs == nil { return nil }
return xs.next
}
Cons は引数 x をセルの item に、xs をセルの next にセットして返すだけです。Car はセルの item を返し、Cdr はセルの next を返します。
リスト : 基本的な述語
// アトムか？
func Atom(x Any) bool {
_, ok := x.(*Cell)
return !ok
}
// セルか？
func Consp(x Any) bool {
xs, ok := x.(*Cell)
return ok && xs != nil
}
// リストか？
func Listp(x Any) bool {
_, ok := x.(*Cell)
return ok
}
// 空リストか？
func Null(xs *Cell) bool {
return xs == nil
}
Atom は型アサーションで引数 x がセルかチェックし、そうでなければ true を返します。Consp は型アサーションで引数 x がセルかチェックします。セルでかつ nil でなければ true を返します。Listp は引数 x がセルか型アサーションで調べるだけです。Null は引数 xs と nil を演算子 == で比較するだけです。
リスト : リストの表示
func sprintList(xs *Cell) string {
s := "("
for ; !Null(xs); xs = Cdr(xs) {
s += Sprint(Car(xs))
if !Null(Cdr(xs)) {
s += " "
}
}
s += ")"
return s
}
func Sprint(x Any) string {
if Listp(x) {
return sprintList(x.(*Cell))
} else {
return fmt.Sprint(x)
}
}
func Print(x Any) {
fmt.Print(Sprint(x))
}
func Println(x Any) {
fmt.Println(Sprint(x))
}
Sprint は引数 x がリストか Listp でチェックし、そうであれば関数 sprintList を呼び出します。そうでなければ、fmt.Sprint で x を文字列に変換します。sprintList は最初に変数 s を "(" に初期化します。そして、for ループでリスト xs を順番にたどり、Sprint を再帰呼び出しして要素 Car(xs) を文字列に変換します。これで Car(xs) がリストの場合でも文字列に変換することができます。次に、Cdr(xs) が空リストか Null でチェックして、そうでなければ次の要素があるので s に空白文字を連結します。最後に s と ")" を連結して返すだけです。
Print と Println は Sprint を呼び出して引数 x を文字列に変換し、fmt.Print または fmt.Println で画面に表示します。
リスト : リスト操作関数
// リストの生成
func List(xs... Any) *Cell {
var zs *Cell
for i := len(xs) - 1; i >= 0; i-- {
zs = Cons(xs[i], zs)
}
return zs
}
// リストの参照
func Nth(xs *Cell, n int) (Any, bool) {
for ; !Null(xs); xs = Cdr(xs) {
if n == 0 {
return Car(xs), true
}
n--
}
return nil, false
}
// 反転
func Reverse(xs *Cell) *Cell {
var zs *Cell
for ; !Null(xs); xs = Cdr(xs) {
zs = Cons(Car(xs), zs)
}
return zs
}
// 長さ
func Length(xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
c++
}
return c
}
// 連結
func Append(xs, ys *Cell) *Cell {
if Null(xs) {
return ys
}
return Cons(Car(xs), Append(Cdr(xs), ys))
}
List は可変長引数 xs (スライス) から要素を取り出してリストに格納していきます。リストの先頭にデータを追加するのは Cons で簡単にできますが、最後尾に追加していくのはちょっと面倒です。そこで、xs の末尾から要素を取り出して、リスト zs の先頭に Cons で追加します。
Nth は for ループでリスト xs をたどり、n 番目の要素を求めるだけです。途中で xs が nil になったならば、for ループを終了して nil と false を返します。Reverse は for ループでリスト xs をたどり、その要素を順番にリスト zs の先頭に追加します。これで xs を反転したリストを作ることができます。Lengh は簡単です。for ループでリストをたどり、変数 c の値を +1 していくだけです。
Append は再帰呼び出しを使うと簡単です。xs が nil ならば ys を返します。これは空リスト (nil) と ys を連結すると ys になることを表していて、再帰呼び出しの停止条件になります。そうでなければ、xs を Car と Cdr で分割して、Cdr(xs) と ys を連結したリストの先頭に Cons で Car(xs) を追加します。これで xs と ys を連結したリストを生成することができます。このとき、xs のリストはコピーされることに注意してください。
リスト : リスト操作関数 (2)
// 先頭から n 個の要素を取り出す
func Take(xs *Cell, n int) *Cell {
if Null(xs) || n <= 0 {
return nil
}
return Cons(Car(xs), Take(Cdr(xs), n - 1))
}
// 先頭から n 個の要素を取り除く
func Drop(xs *Cell, n int) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if n <= 0 {
break
}
n--
}
return xs
}
// 後ろから n 個の要素を取り出す
func Last(xs *Cell, n int) *Cell {
return Drop(xs, Length(xs) - n)
}
// 後から n 個の要素を取り除く
func ButLast(xs *Cell, n int) *Cell {
return Take(xs, Length(xs) - n)
}
Take は引数 n が 0 以下または引数 xs が空リストの場合は nil を返します。そうでなければ Take を再帰呼び出しして、その返り値にリストの先頭要素 Car(xs) を追加します。Drop は簡単です。引数 n が 0 以下または引数 xs が空リストになるまで Drop を再帰呼び出しするだけです。
Last は xs の先頭から (Length(xs) - n) 個の要素を Drop で取り除くだけです。逆に、ButLast は Take で (Length(xs) - n) 個の要素を取り出すだけです。
リスト : 等値の判定
func Eq(x Any, y Any) bool {
return x == y
}
func Equal(x Any, y Any) bool {
if Atom(x) && Atom(y) {
return Eq(x, y)
}
xs, ox := x.(*Cell)
ys, oy := y.(*Cell)
if ox && oy {
for !Null(xs) && !Null(ys) {
if !Equal(Car(xs), Car(ys)) {
return false
}
xs = Cdr(xs)
ys = Cdr(ys)
}
return Null(xs) && Null(ys)
}
return false
}
Equal の引数 x, y がセルでなければ関数 Eq で比較します。Eq は演算子 == で引数 x, y を比較するだけです。そうでなければ、x, y を型アサーションでリスト xs, ys に変換します。どちらかがリストに変換できない場合は false を返します。
x, y がリストの場合、Equal を再帰呼び出しして要素 Car(xs), Car(ys) を比較します。これでリストが入れ子の場合でも比較することができます。Equal の返り値が false であれば return で false を返します。そうでなければ、要素の比較を続けます。for ループが終了したら、xs, ys がともに nil であることを確認します。そうでなければ、リストの長さが異なるので結果は false になります。
リスト : 高階関数
// マッピング
func MapCar(f func(x Any) Any, xs *Cell) *Cell {
if Null(xs) {
return nil
}
return Cons(f(Car(xs)), MapCar(f, Cdr(xs)))
}
// フィルター
func Filter(f func(x Any) bool, xs *Cell) *Cell {
if Null(xs) {
return nil
} else if f(Car(xs)) {
return Cons(Car(xs), Filter(f, Cdr(xs)))
}
return Filter(f, Cdr(xs))
}
// 畳み込み
func Foldl(f func(a, x Any) Any, a Any, xs *Cell) Any {
for ; !Null(xs); xs = Cdr(xs) {
a = f(a, Car(xs))
}
return a
}
func Foldr(f func(x, a Any) Any, a Any, xs *Cell) Any {
if Null(xs) {
return a
}
return f(Car(xs), Foldr(f, a, Cdr(xs)))
}
// 巡回
func ForEach(f func(x Any), xs *Cell) {
for ; !Null(xs); xs = Cdr(xs) {
f(Car(xs))
}
}
MapCar は簡単です。引数 xs が空リストであれば nil を返します。これが再帰呼び出しの停止条件になります。そうでなければ、xs を Car と Cdr で分解し、Car(xs) に関数 f を適用した結果と MapCar(f, Cdr(xs)) の結果を Cons で結合します。Filter も簡単です。述語 f が真を返すとき要素 Car(xs) をリストに追加し、偽を返すときはリストに加えません。
Foldl は for ループで簡単にプログラムできます。累積変数 a と Car(xs) を関数 f に渡して評価し、その返り値で変数 a の値を書き換えます。Foldr は再帰呼び出しでプログラムします。引数 xs が空リストであれば a を返します。そうでなければ、Foldr を再帰呼び出しして、その返り値と要素 Car(xs) を関数 f に渡して評価します。
ForEach も簡単です。for ループでリストを先頭から順番にたどり、要素 Car(xs) を関数 f に渡して評価するだけです。
リスト : リストの探索
func Member(x Any, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) { break }
}
return xs
}
func MemberIf(f func(x Any) bool, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) { break }
}
return xs
}
func Find(x Any, xs *Cell) bool {
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
return true
}
}
return false
}
func FindIf(f func (x Any) bool, xs *Cell) (Any, bool) {
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
return Car(xs), true
}
}
return nil, false
}
func Position(x Any, xs *Cell) int {
n := 0
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
return n
}
n++
}
return -1
}
func PositionIf(f func(x Any) bool, xs *Cell) int {
n := 0
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
return n
}
n++
}
return -1
}
func Count(x Any, xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
c++
}
}
return c
}
func CountIf(f func(x Any) bool, xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) { c++ }
}
return c
}
これらの関数は線形探索なので難しいところはないと思います。詳細はプログラムリストをお読みください。
リスト : リストの修正
func Remove(x Any, xs *Cell) *Cell {
return Filter(func(y Any) bool { return !Eq(x, y) }, xs)
}
func RemoveIf(f func(x Any) bool, xs *Cell) *Cell {
return Filter(func(y Any) bool { return !f(y) }, xs)
}
func SubstituteIf(f func(x Any) bool, y Any, xs *Cell) *Cell {
if Null(xs) {
return nil
} else if f(Car(xs)) {
return Cons(y, SubstituteIf(f, y, Cdr(xs)))
}
return Cons(Car(xs), SubstituteIf(f, y, Cdr(xs)))
}
func Substitute(x, y Any, xs *Cell) *Cell {
return SubstituteIf(func(z Any) bool { return Eq(z, x) }, y, xs)
}
Remove と RemoveIf は Filter を呼び出すだけなので説明は割愛します。SubStituteIf は再帰呼び出しを使うと簡単です。引数 xs が空リストならば nil を返します。f(Car(xs)) の返り値が真ならば、SubstituteIf の返り値のリストに y を追加します。そうでなければ Car(xs) を追加します。Subustitute は SubstituteIf を呼び出すだけです。
リスト : 連想リスト
func Zip(xs, ys *Cell) *Cell {
if Null(xs) || Null(ys) {
return nil
}
return Cons(List(Car(xs), Car(ys)), Zip(Cdr(xs), Cdr(ys)))
}
func UnZip(xs *Cell) (*Cell, *Cell) {
if Null(xs) {
return nil, nil
}
ys, zs := UnZip(Cdr(xs))
x := Car(xs).(*Cell)
return Cons(Car(x), ys), Cons(Car(Cdr(x)), zs)
}
func Assoc(key Any, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
ys, ok := Car(xs).(*Cell)
if !ok { break }
if Eq(key, Car(ys)) {
return ys
}
}
return nil
}
func AssocIf(f func (x Any) bool, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
ys, ok := Car(xs).(*Cell)
if !ok { break }
if f(Car(ys)) {
return ys
}
}
return nil
}
Zip は引数 xs または ys が空リストならば nil を返します。そうでなければ、Zip を再帰呼び出しして、その返り値に List(Car(xs), Car(ys)) を追加します。Unzip は再帰呼び出しでプログラムすると簡単です。xs が空リストの場合、2 つの空リストを多値で返します。そうでなければ、Unzip を再帰呼び出しして、返り値 (多値) を多重代入で受け取ります。そして、受け取ったリストに要素を追加して、それを多値で返すだけです。
Assoc, AsscoIf はリスト xs を線形探索するだけですが、要素がリストなので型アサーションを使っていることに注意してください。*Cell に変換できない場合は、break で for ループを脱出して nil を返します。panic でエラーを送出してもよいでしょう。
//
// slist.go : Lisp 風の連結リスト
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package slist
import "fmt"
// 型の定義
type Any interface{}
// セルの定義
type Cell struct {
item Any
next *Cell
}
// 基本操作
// セルの生成
func Cons(x Any, xs *Cell) *Cell {
return &Cell{x, xs}
}
// 要素を取り出す
func Car(xs *Cell) Any {
if xs == nil {
return nil
}
return xs.item
}
// 先頭要素を取り除く
func Cdr(xs *Cell) *Cell {
if xs == nil {
return nil
}
return xs.next
}
// 述語
// アトムか？
func Atom(x Any) bool {
_, ok := x.(*Cell)
return !ok
}
// セルか？
func Consp(x Any) bool {
xs, ok := x.(*Cell)
return ok && xs != nil
}
// リストか？
func Listp(x Any) bool {
_, ok := x.(*Cell)
return ok
}
// 空リストか？
func Null(xs *Cell) bool {
return xs == nil
}
// 等値
func Eq(x Any, y Any) bool {
return x == y
}
func Equal(x Any, y Any) bool {
if Atom(x) && Atom(y) {
return Eq(x, y)
}
xs, ox := x.(*Cell)
ys, oy := y.(*Cell)
if ox && oy {
for !Null(xs) && !Null(ys) {
if !Equal(Car(xs), Car(ys)) {
return false
}
xs = Cdr(xs)
ys = Cdr(ys)
}
return Null(xs) && Null(ys)
}
return false
}
// リスト操作
// リストの生成
func List(xs... Any) *Cell {
var zs *Cell
for i := len(xs) - 1; i >= 0; i-- {
zs = Cons(xs[i], zs)
}
return zs
}
// リストの参照
func Nth(xs *Cell, n int) (Any, bool) {
for ; !Null(xs); xs = Cdr(xs) {
if n == 0 {
return Car(xs), true
}
n--
}
return nil, false
}
// 反転
func Reverse(xs *Cell) *Cell {
var zs *Cell
for ; !Null(xs); xs = Cdr(xs) {
zs = Cons(Car(xs), zs)
}
return zs
}
// 連結
func Append(xs, ys *Cell) *Cell {
if Null(xs) {
return ys
}
return Cons(Car(xs), Append(Cdr(xs), ys))
}
// 長さ
func Length(xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
c++
}
return c
}
// 先頭から n 個の要素を取り除く
func Drop(xs *Cell, n int) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if n <= 0 {
break
}
n--
}
return xs
}
// 先頭から n 個の要素を取り出す
func Take(xs *Cell, n int) *Cell {
if Null(xs) || n <= 0 {
return nil
}
return Cons(Car(xs), Take(Cdr(xs), n - 1))
}
// 後ろから n 個の要素を取り出す
func Last(xs *Cell, n int) *Cell {
return Drop(xs, Length(xs) - n)
}
// 後から n 個の要素を取り除く
func ButLast(xs *Cell, n int) *Cell {
return Take(xs, Length(xs) - n)
}
// 高階関数
func MapCar(f func(x Any) Any, xs *Cell) *Cell {
if Null(xs) {
return nil
}
return Cons(f(Car(xs)), MapCar(f, Cdr(xs)))
}
func Filter(f func(x Any) bool, xs *Cell) *Cell {
if Null(xs) {
return nil
} else if f(Car(xs)) {
return Cons(Car(xs), Filter(f, Cdr(xs)))
}
return Filter(f, Cdr(xs))
}
func Foldl(f func(a, x Any) Any, a Any, xs *Cell) Any {
for ; !Null(xs); xs = Cdr(xs) {
a = f(a, Car(xs))
}
return a
}
func Foldr(f func(x, a Any) Any, a Any, xs *Cell) Any {
if Null(xs) {
return a
}
return f(Car(xs), Foldr(f, a, Cdr(xs)))
}
func ForEach(f func(x Any), xs *Cell) {
for ; !Null(xs); xs = Cdr(xs) {
f(Car(xs))
}
}
// 探索
func Member(x Any, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) { break }
}
return xs
}
func MemberIf(f func(x Any) bool, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) { break }
}
return xs
}
func Find(x Any, xs *Cell) bool {
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
return true
}
}
return false
}
func FindIf(f func (x Any) bool, xs *Cell) (Any, bool) {
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
return Car(xs), true
}
}
return nil, false
}
func Position(x Any, xs *Cell) int {
n := 0
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
return n
}
n++
}
return -1
}
func PositionIf(f func(x Any) bool, xs *Cell) int {
n := 0
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
return n
}
n++
}
return -1
}
func Count(x Any, xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
if Eq(x, Car(xs)) {
c++
}
}
return c
}
func CountIf(f func(x Any) bool, xs *Cell) int {
c := 0
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) { c++ }
}
return c
}
// リストの修正
func Remove(x Any, xs *Cell) *Cell {
return Filter(func(y Any) bool { return !Eq(x, y) }, xs)
}
func RemoveIf(f func(x Any) bool, xs *Cell) *Cell {
return Filter(func(y Any) bool { return !f(y) }, xs)
}
func SubstituteIf(f func(x Any) bool, y Any, xs *Cell) *Cell {
if Null(xs) {
return nil
} else if f(Car(xs)) {
return Cons(y, SubstituteIf(f, y, Cdr(xs)))
}
return Cons(Car(xs), SubstituteIf(f, y, Cdr(xs)))
}
func Substitute(x, y Any, xs *Cell) *Cell {
return SubstituteIf(func(z Any) bool { return Eq(z, x) }, y, xs)
}
// 連想リスト
func Zip(xs, ys *Cell) *Cell {
if Null(xs) || Null(ys) {
return nil
}
return Cons(List(Car(xs), Car(ys)), Zip(Cdr(xs), Cdr(ys)))
}
func UnZip(xs *Cell) (*Cell, *Cell) {
if Null(xs) {
return nil, nil
}
ys, zs := UnZip(Cdr(xs))
x := Car(xs).(*Cell)
return Cons(Car(x), ys), Cons(Car(Cdr(x)), zs)
}
func Assoc(key Any, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
ys, ok := Car(xs).(*Cell)
if !ok { break }
if Eq(key, Car(ys)) {
return ys
}
}
return nil
}
func AssocIf(f func (x Any) bool, xs *Cell) *Cell {
for ; !Null(xs); xs = Cdr(xs) {
ys, ok := Car(xs).(*Cell)
if !ok { break }
if f(Car(ys)) {
return ys
}
}
return nil
}
// 表示
func sprintList(xs *Cell) string {
s := "("
for ; !Null(xs); xs = Cdr(xs) {
s += Sprint(Car(xs))
if !Null(Cdr(xs)) {
s += " "
}
}
s += ")"
return s
}
func Sprint(x Any) string {
if Listp(x) {
return sprintList(x.(*Cell))
} else {
return fmt.Sprint(x)
}
}
func Print(x Any) {
fmt.Print(Sprint(x))
}
func Println(x Any) {
fmt.Println(Sprint(x))
}
//
// yagp05.go : Yet Another Golang Problems
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
. "yagp/slist"
)
func main() {
fmt.Println("----- P41 -----")
Println(Cons(1, nil))
Println(Cons(2, Cons(1, nil)))
Println(Car(Cons(1, nil)))
Println(Cdr(Cons(1, nil)))
Println(Car(Cons(2, Cons(1, nil))))
Println(Cdr(Cons(2, Cons(1, nil))))
fmt.Println("----- P42 -----")
Println(Atom(1))
Println(Atom(Cons(1, nil)))
Println(Listp(1))
Println(Listp(Cons(1, nil)))
Println(Listp(Cdr(Cons(1, nil))))
Println(Consp(1))
Println(Consp(Cons(1, nil)))
Println(Consp(Cdr(Cons(1, nil))))
Println(Null(Cdr(Cons(1, nil))))
Println(Null(Cdr(Cons(2, Cons(1, nil)))))
fmt.Println("----- P43 -----")
fmt.Println(Sprint(Cons(1, nil)))
fmt.Println(Sprint(Cons(3, Cons(2, Cons(1, nil)))))
fmt.Println(Sprint(Cons(Cons(3, nil), Cons(Cons(2, nil), Cons(Cons(1, nil), nil)))))
fmt.Println("----- P44 -----")
Println(List(1, 2, 3, 4))
fmt.Println(Nth(List(1, 2, 3, 4), 0))
fmt.Println(Nth(List(1, 2, 3, 4), 3))
fmt.Println(Nth(List(1, 2, 3, 4), 4))
Println(Append(List(1, 2, 3), List(4, 5, 6)))
Println(Reverse(List(1, 2, 3, 4, 5)))
Println(Length(List(1, 2, 3, 4, 5)))
fmt.Println("----- P45 -----")
Println(Take(List(1, 2, 3, 4), 0))
Println(Take(List(1, 2, 3, 4), 2))
Println(Take(List(1, 2, 3, 4), 4))
Println(Drop(List(1, 2, 3, 4), 0))
Println(Drop(List(1, 2, 3, 4), 2))
Println(Drop(List(1, 2, 3, 4), 4))
Println(Last(List(1, 2, 3, 4, 5), 1))
Println(Last(List(1, 2, 3, 4, 5), 2))
Println(Last(List(1, 2, 3, 4, 5), 4))
Println(ButLast(List(1, 2, 3, 4, 5), 1))
Println(ButLast(List(1, 2, 3, 4, 5), 2))
Println(ButLast(List(1, 2, 3, 4, 5), 4))
fmt.Println("----- P46 -----")
fmt.Println(Equal(1, 1))
fmt.Println(Equal(1, 1.0))
fmt.Println(Equal(List(1, 2, 3), List(1, 2, 3)))
fmt.Println(Equal(List(Cons(1, nil), 2, 3), List(Cons(1, nil), 2, 3)))
fmt.Println(Equal(List(Cons(1, nil), 2, 3), List(Cons(5, nil), 2, 3)))
fmt.Println("----- P47 -----")
times := func(x Any) Any { return x.(int) * 2 }
Println(MapCar(times, List(1, 2, 3, 4, 5)))
isOdd := func(x Any) bool { return x.(int) % 2 != 0 }
Println(Filter(isOdd, List(1, 2, 3, 4, 5)))
add := func(x, y Any) Any { return x.(int) + y.(int) }
fmt.Println(Foldl(add, 0, List(1, 2, 3, 4, 5)))
fmt.Println(Foldr(add, 0, List(1, 2, 3, 4, 5)))
var Nil *Cell
xcons := func(x, y Any) Any { return Cons(y, x.(*Cell)) }
Println(Foldl(xcons, Nil, List(1, 2, 3, 4, 5)))
kons := func(x, y Any) Any { return Cons(x, y.(*Cell)) }
Println(Foldr(kons, Nil, List(1, 2, 3, 4, 5)))
ForEach(func(x Any){ fmt.Println(x) }, List(1,2,3,4,5))
fmt.Println("----- P48 -----")
xs := List(1, 2, 3, 4, 5)
Println(Member(1, xs))
Println(Member(3, xs))
Println(Member(5, xs))
Println(Member(6, xs))
isEven := func(x Any) bool { return x.(int) % 2 == 0 }
Println(MemberIf(isEven, xs))
fmt.Println(Find(3, xs))
fmt.Println(Find(6, xs))
fmt.Println(FindIf(isEven, xs))
fmt.Println(Position(3, xs))
fmt.Println(PositionIf(isEven, xs))
fmt.Println(Count(3, xs))
fmt.Println(CountIf(isEven, xs))
fmt.Println("----- P49 -----")
Println(Remove(3, xs))
Println(RemoveIf(isEven, xs))
Println(Substitute(3, 30, xs))
Println(SubstituteIf(isEven, 100, xs))
fmt.Println("----- P50 -----")
xs = Zip(List("a", "b", "c"), List(4, 5, 6))
Println(xs)
ys, zs := UnZip(xs)
Println(ys)
Println(zs)
Println(Assoc("a", xs))
Println(Assoc("d", xs))
Println(AssocIf(func(x Any) bool { return x.(string) == "c" }, xs))
}
$ cd yagp $ ls go.mod slist yagp01.go yagp02.go yagp03.go yagp04.go yagp05.go $ cat go.mod module yagp go 1.23.2 $ ls slist slist.go $ go run yagp05.go ----- P41 ----- (1) (2 1) 1 () 2 (1) ----- P42 ----- true false false true true false true false true false ----- P43 ----- (1) (3 2 1) ((3) (2) (1)) ----- P44 ----- (1 2 3 4) 1 true 4 truefalse (1 2 3 4 5 6) (5 4 3 2 1) 5 ----- P45 ----- () (1 2) (1 2 3 4) (1 2 3 4) (3 4) () (5) (4 5) (2 3 4 5) (1 2 3 4) (1 2 3) (1) ----- P46 ----- true false true true false ----- P47 ----- (2 4 6 8 10) (1 3 5) 15 15 (5 4 3 2 1) (1 2 3 4 5) 1 2 3 4 5 ----- P48 ----- (1 2 3 4 5) (3 4 5) (5) () (2 3 4 5) true false 2 true 2 1 1 2 ----- P49 ----- (1 2 4 5) (1 3 5) (1 2 30 4 5) (1 100 3 100 5) ----- P50 ----- ((a 4) (b 5) (c 6)) (a b c) (4 5 6) (a 4) () (c 6)