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. OK, I Understand
Top