Created
November 26, 2019 21:21
-
-
Save AndreasKostler/bd38cf7ea8b9f36f20748a4d5abac50a to your computer and use it in GitHub Desktop.
Theorem flatten
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Super simple, recursive flatten | |
| // The _ means we have a weakly polymorphic type | |
| // i.e. we don't care about what type _ is (it will, or will not, be resolved later) | |
| // the type signature for flatMap on Seq is Seq[A] => (A => Seq[B]) => Seq[B] | |
| def flatten(s: Seq[_]): Seq[_] = s flatMap { | |
| case s: Seq[_] => flatten(s) // If s is a Seq, we recursively flatten | |
| case s => Seq(s) // If s is atomic, we're done; just package up s | |
| } | |
| // degenerate case | |
| flatten(List()) == List() | |
| // 0 level nesting | |
| flatten(List(1, 2, 3, 4)) == List(1, 2, 3, 4) | |
| // 1 level nesting | |
| flatten(List(1, List(2, 3), List(4))) == List(1,2,3,4) | |
| // 2 level nesting | |
| flatten(List(1, List(2, List(3, 4)), List(5))) == List(1,2,3,4,5) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment