计算包含列表的列表的长度（SML）

Question

SML长度函数：

fun length(L) =
    if (L=nil) then 0
    else 1+length(tl(L));

例如：

length [1,2,3] = 3;
length [ [5], [4], [3], [2,1] ] = 4;

根据代码，如果我也想统计list的list中的元素怎么改？

例如：

length [ [5], [4], [3], [2,1] ] = 5;

Answer 1

您可以创建另一个函数来使用您的函数，如下所示：

fun d_length ( [] ) = 0
| d_length ( l :: l' ) = length(l) + d_length(l');

d_length[ [5], [4], [3], [2,1] ];

或者，使用内置减速器：

List.foldl (fn(e,a) => length(e) + a) 0 [ [5], [4], [3], [2,1] ];

Answer 2

您不想进行比较 L=nil 因为这只适用于可比较的类型列表（例如，不是函数列表）。相反，您需要 Kevin Johnson 建议的模式匹配；

fun length [] = 0
  | length (x::xs) = 1 + length xs

或者使用尾递归：

fun length xs =
    let fun len [] n = n
          | len (x::xs) n = len xs (1+n)
    in len xs 0 end

与 length : 'a list -> int 不同，此函数的类型为 'a list list -> int.

所有子列表的总长度可以通过多种方式实现。例如

fun length2 xss = List.foldl op+ 0 (List.concat xss)

但是凯文的回答也利用了这一点，当我们所做的只是稍后再次销毁它时，用 List.concat xss 构建一个新列表真的没有任何意义。所以无耻地撕毁他的解决方案：

fun length2 xss = List.foldl (fn (xs, sum) => length xs + sum) 0 xss

这可能也是表达该函数最易读的方式，但是如果您尝试 code golf 该函数非常短，您也可以使用高阶函数重写内部闭包：

fun curry f x y = f (x, y)
fun uncurry f (x, y) = f x y
fun length2 xss = List.foldl (uncurry (curry op+ o length)) 0 xss

Answer 3

这是一个模式匹配的直接递归版本，它不使用内置的 length 函数而是直接计算总长度 ("tol")：

fun tol [] = 0
|   tol ([]::xss) = tol xss
|   tol ((x::xs)::xss) = 1 + tol (xs::xss);

最后一个子句中括号的顺序很重要。它覆盖了 :: 的右结合性，因此 (x::xs)::xss 中的 x 被解释为 xss 中第一个列表的头部，而不是 xss 中的头部本身。

这些答案的模式似乎是折叠结束，我不想打破模式。这是一个折叠，它将通过在列表列表上映射长度获得的列表折叠成总和：

fun tol xss = foldl op+ 0 (map length xss);

computes the length of list which contains list (SML)