• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 21st, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. concat: List<List<Int>> -> List<Int>
2.
3. concat(empty) = empty
4. concat(cons(l, x)) = app(l, concat(x))
5.
6. deomonstrati ca
7. size(concat(l)) == sum(map(size, l)))
8.
9. pentru inceput vom demonstra prin inductie structurala ca
10. size(app(l, l1)) = size(l) + size(l1)
11. cazul de baza: size(app(empty, l1)) = size(l1)
12.                   size(empty) + size(l1) = size(l1)
13.
14. pasul de inductie:
15.  size(app(cons(a, l), l1)) = size(cons(a, app(l, l1))) = 1 + size(l) + size(l1)
16.  size(cons(a, l)) + size(l1) = 1 + size(l) + size(l1)
17.
18. inapoi la problema noastra:
19. cazul de baza
20. l = empty
21.
22. size(concat(empty)) = size(empty) = 0
23.
24. sum(map(size, empty)) = sum(empty) = 0 => concluzia
25.
26.
27. pasul de inductie: presupunem adevarata pentru l (List<List<Int>>) si demonstram pentru cons(l1, l) unde l1 este List<int>
28.
29. size(concat(cons(l1, l))) = size(app(l1, concat(l))) =(din ce am demonstrate anterior) size(l1) + size(concat(l))
30.
31.
32. sum(map(size, cons(l1, l))) = sum(cons(size(l1), map(size, l))) = size(l1) + sum(map(size, l)) = size(l1) + size(concat(l))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top