вычисляет длину списка, который содержит список (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; 

на основе кода, как я могу изменить его, если я хочу подсчитать элементы в списке списка?

Например:

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, так как это работает только для списков типа которые сопоставимы (например, а не списки функций). Скорее, вам нужен образец, который предлагает Кевин Джонсон;

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, но вместо этого вычисляет общую длину («тол») непосредственно:

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

Важным является порядок скобок в заключительном разделе. Он переопределяет право-ассоциативность ::, так что x в (x::xs)::xss интерпретируется как глава первого списка в xss, а не глава xss.

Образец этих ответов кажется закрытым со складкой, и я не хочу нарушать шаблон. Вот сгиб, который складывается в сумму списка, полученного путем отображения длины над списком списков:

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