Many uses of higher-order functions can be readily replaced with function templates in ATS. In particular, higher-order functions are often implemented in ATS based on the corresponding function templates. Let us start with a concrete example. Following is a standard implementation of list mapping as a higher-order function (template):

// extern fun {a:t@ype} {b:t@ype} list_map_fun{n:nat} (xs: list(a, n), fopr: a -> b): list_vt(b, n) // implement {a}{b} list_map_fun (xs, fopr) = let // fun aux{n:nat} (xs: list(a, n)): list_vt(b, n) = ( case+ xs of | list_nil() => list_vt_nil() | list_cons(x, xs) => list_vt_cons(fopr(x), aux(xs)) ) // in aux(xs) end // end of [list_map_fun] //

// extern fun {a:t@ype} {b:t@ype} list_map_cloref{n:nat} (xs: list(a, n), fopr: a -<cloref1> b): list_vt(b, n) //

A proper way to implement list mapping (as I see it) is given as follows:

// extern fun {a:t@ype} {b:t@ype} list_map{n:nat} (xs: list(a, n)): list_vt(b, n) // extern fun {a:t@ype}{b:t@ype} list_map$fopr(x: a): b // implement {a}{b} list_map (xs) = let // fun aux{n:nat} (xs: list(a, n)): list_vt(b, n) = ( case+ xs of | list_nil() => list_vt_nil() | list_cons(x, xs) => list_vt_cons(list_map$fopr<a><b>(x), aux(xs)) ) (* end of [aux] *) // in aux(xs) end // end of [list_map] //

With list_map, we can implement list_map_fun as follows in a straightforward manner:

implement {a}{b} list_map_fun(xs, fopr) = let // implement list_map$fopr<a><b> (x) = fopr(x) // in list_map<a><b> (xs) end // end of [list_map_fun]

implement {a}{b} list_map_cloref(xs, fopr) = let // implement list_map$fopr<a><b> (x) = fopr(x) // in list_map<a><b> (xs) end // end of [list_map_cloref]

Please find on-line the file list_map.dats containing the entirety of the code presented in this section plus some testing code.