ATSプログラミング入門:
PrevChapter 5. パラメータ多相Next

例: リストに対する関数テンプレート

関数型プログラミングでは、リストはどこででも使われます。 ここでは一般に使われるリストに対する関数テンプレートを実装します。 これらのテンプレートは全て、ATS のライブラリで利用できることに注意すべきです。 それらは線形データ型のようなこれまで紹介してないプログラミングの機能を使って、より効果的な方法で実装されていることがあります。

この章のコード全体と追加のテストコードは オンライン から入手できます。 (訳注: このコードを atscc でコンパイルする際には -DATS_MEMALLOC_LIBC オプションが必要です。 さらにATSコンパイラ本体だけではなく、ATS2-Postiats-contrib のインストールも必要です。)

連結: list0_append

型 T と型 list0(T) の2つのリスト xs と ys が与えられた時、list0_append(xs, ys) は xs と ys を連結した1つのリストを返します: 

fun{
a:t@ype
} list0_append
(
  xs: list0 a
, ys: list0 a
) : list0 a =
(
case+ xs of
| list0_cons (x, xs) =>
    list0_cons{a}(x, list0_append<a> (xs, ys))
| list0_nil ((*void*)) => ys
) (* end of [list0_append] *)

明らかに、この list0_append は末尾再帰ではありません。

逆順連結: list0_reverse_append

型 T と型 list0(T) の2つのリスト xs と ys が与えられた時、list0_reverse_append(xs, ys) は xs と ys の逆順を連結したリストを返します: 

fun{
a:t@ype
} list0_reverse_append
(
  xs: list0 a, ys: list0 a
) : list0 a =
(
case+ xs of
| list0_cons (x, xs) =>
    list0_reverse_append<a> (xs, list0_cons{a}(x, ys))
| list0_nil () => ys
) (* end of [list0_reverse_append] *)

明らかに、 list0_reverse_append のこの実装は末尾再帰です。

逆順: list0_reverse

リスト xs が与えられた時、list0_reverse(xs) は xs の逆順を返します: 

fun{a:t@ype}
list0_reverse
  (xs: list0 a): list0 a = list0_reverse_append<a> (xs, list0_nil)
// end of [list0_reverse]

マップ: list0_map

型 T1、型 T2、型 T1 -<cloref1> T2 のクロージャ関数 f、型 list0(T1) のリスト xs が与えられた時、list0_map(xs, f) は list0(T2) 型のリスト ys を返します: 

fun
{a:t@ype}
{b:t@ype}
list0_map
(
  xs: list0 a, f: a -<cloref1> b
) : list0 b =
(
case+ xs of
| list0_cons (x, xs) =>
    list0_cons{b}(f x, list0_map<a><b> (xs, f))
| list0_nil ((*void*)) => list0_nil ()
) (* end of [list0_map] *)

ys の長さは xs の長さに等しく、ys 中のそれぞれの要素 y は xs 中の関連する要素をxとしたとき f(x) に等しくなります。 明らかに list0_map のこの実装は末尾再帰ではありません。

左 fold: list0_foldleft

xs, ini, f が与えられた時、list0_foldleft(ini, xs, f) は式 f(... f(f(ini, xs[0]), xs[1]) ..., xs[n-1]) の値を計算します。 このとき n は xs の長さで、 xs[i] は i < n のような xs の i 番目の要素です。 次の list0_foldleft の実装は末尾再帰です: 

fun
{a:t@ype}
{b:t@ype}
list0_foldleft
(
  ini: a, xs: list0 (b), f: (a, b) -> a
) : a =
(
  case+ xs of
  | list0_cons
      (x, xs) => list0_foldleft<a><b> (f (ini, x), xs, f)
  | list0_nil ((*void*)) => ini
)

右 fold: list0_foldright

xs, res, f が与えられた時、list0_foldright(xs, res, f) は式 f(xs[0], f(xs[1], f(... f(xs[n-1], res) ...))) の値を計算します。 このとき n は xs の長さで、 xs[i] は i < n のような xs の i 番目の要素です。 次の list0_foldright 実装は末尾再帰ではありません: 

fun
{a:t@ype}
{b:t@ype}
list0_foldright
(
  xs: list0 (a), res: b, f: (a, b) -> b
) : b =
(
  case+ xs of
  | list0_cons
      (x, xs) => f (x, list0_foldright<a><b> (xs, res, f))
  | list0_nil ((*void*)) => res
)

zip 関数: list0_zip

型 T1 と T2、型 list0(T1) と list0(T2) の2つのリスト xs と ys がそれぞれ与えられた時、list0_zip(xs, ys) は型 list0 @(T1, T2) のリスト zs を返します: 

fun{
a,b:t@ype
} list0_zip
(
  xs: list0 a
, ys: list0 b
) : list0 @(a, b) = let
  typedef ab = @(a, b)
in
//
case+ (xs, ys) of
| (list0_cons (x, xs),
   list0_cons (y, ys)) =>
  (
    list0_cons{ab}((x, y), list0_zip<a,b> (xs, ys))
  )
| (_, _) => list0_nil ()
//
end // end of [list0_zip]

zs の長さは xs と ys の長さの小さい方になり、zs のそれぞれの要素 z は x と y をそれぞれ xs と ys の対応する要素としたときの @(x, y) に等しくなります。 明らかに、この list0_zip の実装は末尾再帰ではありません。

zip with 関数: list0_zipwith

型 T1, T2, T3 と、型 (T1, T2) -<cloref1> T3 のクロージャ関数 f と、list0(T1) と list0(T2) 型の2つのリスト xs と ys がそれぞれ与えられた時、list0_zipwith(xs, ys, f) は list0(T3) 型のリスト zs を返します: 

fun
{a,b:t@ype}
{c:t@ype}
list0_zipwith
(
  xs: list0 a
, ys: list0 b
, f: (a, b) -<cloref1> c
) : list0 c =
(
case+ (xs, ys) of
| (list0_cons (x, xs),
   list0_cons (y, ys)) =>
  (
    list0_cons{c}(f (x, y), list0_zipwith<a,b><c> (xs, ys, f))
  )
| (_, _) => list0_nil ()
) (* end of [list0_zipwith] *)

zs の長さは xs と ys の長さの小さい方になり、zs のそれぞれの要素 z は x と y をそれぞれ xs と ys の対応する要素としたときの f(x, y) に等しくなります。 明らかに、この list0_zipwith の実装は末尾再帰ではありません。 3番目の引数 f を lam (x, y) => @(x, y) で置き換えれば、list0_zipwith は list0_zip とまったく同じ振る舞いをすることに注意してください。 この関数テンプレートは list0_map2 という名前も持っています。

PrevHomeNext
多相データ型Up例: リストのマージソート