concat: List<List<Int>> -> List<Int>

concat(empty) = empty
concat(cons(l, x)) = app(l, concat(x))

deomonstrati ca
size(concat(l)) == sum(map(size, l)))

pentru inceput vom demonstra prin inductie structurala ca
size(app(l, l1)) = size(l) + size(l1)
cazul de baza: size(app(empty, l1)) = size(l1)
                  size(empty) + size(l1) = size(l1)

pasul de inductie:
 size(app(cons(a, l), l1)) = size(cons(a, app(l, l1))) = 1 + size(l) + size(l1)
 size(cons(a, l)) + size(l1) = 1 + size(l) + size(l1)

inapoi la problema noastra:
cazul de baza
l = empty

size(concat(empty)) = size(empty) = 0

sum(map(size, empty)) = sum(empty) = 0 => concluzia


pasul de inductie: presupunem adevarata pentru l (List<List<Int>>) si demonstram pentru cons(l1, l) unde l1 este List<int>

size(concat(cons(l1, l))) = size(app(l1, concat(l))) =(din ce am demonstrate anterior) size(l1) + size(concat(l))


sum(map(size, cons(l1, l))) = sum(cons(size(l1), map(size, l))) = size(l1) + sum(map(size, l)) = size(l1) + size(concat(l))