Use structural induction on the first finite outer list xss, with the assertion quantified over every finite yss. For xss = [], both sides are []. For the nonempty case of structural induction, write xss = xs:xss'. If yss = [], both sides again truncate to []. Otherwise write yss = ys:yss'. Expanding the definitions gives
(1)
The second equality uses the defining equation for list concatenation and the induction hypothesis for the smaller outer list xss'. The argument covers unequal outer lengths because the empty second list was handled explicitly. Hence
(2)

Ancestors (11)

  1. 1
  2. Functional programming, data structures and algorithms, procedural programming, and digital hardware
  3. 2003
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version