A generator returns a sequence of values, but unlike with a function the values are returned one at a time. This requires less memory for representing large (possibly infinite) sequences because the entire sequence is never stored in-memory at once. The sequence is computed, one value at a time, as needed.
Python
Scala
Tuesday, April 1, 2014
Exploring Tail Recursion
A tail-recursive function does not require a new stack frame for each call. All the recursive calls will execute in a single frame. This is benefiitial because you do not have to worry about recursing too deeply and getting a StackOverflowError, or the overhead of the many function calls.
What makes a function tail-recursive, and not just recursive, is that the call to itself is the last operation in the function. When this happens the compiler can generate bytecodes that are the same as if the function were written with a while-loop. These two examples from Programming in Scala are not only functionally equivalent, but would be optimized to have the same bytecode:
In Scala use the @tailrec annotation so you will get a compiler error if the function's recursion can not be optimized away.
What makes a function tail-recursive, and not just recursive, is that the call to itself is the last operation in the function. When this happens the compiler can generate bytecodes that are the same as if the function were written with a while-loop. These two examples from Programming in Scala are not only functionally equivalent, but would be optimized to have the same bytecode:
In Scala use the @tailrec annotation so you will get a compiler error if the function's recursion can not be optimized away.
Labels:
functional programming,
scala
Exploring Partial Functions, Partially Applied Functions, and Currying
I'm trying to learn more about functional programming. This is the third in a series of posts about functional programming concepts with examples in Scala (and in some cases other languages too).
Partial Functions
A partial function is a function only valid over a specific range. Some functions are not valid for all input values, like asymptotic functions or those only applicable to natural numbers.
Partially Applied Functions
A partially applied function is an expression in which you don’t supply all of the arguments needed by the function.
Currying
A curried function is applied to multiple argument lists. The results are chained together. In this simple example, the 2 would be applied to x + y resulting in 2 + y. Then the 3 is applied resulting in 5.
This technique can be used to make method calls look more like native-language support. Here is a non-trivial example from Programming in Scala:
Notes
Partial functions and partially applied functions are not related, except the names are almost the same. I was confused about this when I started to research this post.
The call to partially applied functions returns immediately. Curried functions return another function in the currying chain.
Partial Functions
A partial function is a function only valid over a specific range. Some functions are not valid for all input values, like asymptotic functions or those only applicable to natural numbers.
Partially Applied Functions
A partially applied function is an expression in which you don’t supply all of the arguments needed by the function.
Currying
A curried function is applied to multiple argument lists. The results are chained together. In this simple example, the 2 would be applied to x + y resulting in 2 + y. Then the 3 is applied resulting in 5.
This technique can be used to make method calls look more like native-language support. Here is a non-trivial example from Programming in Scala:
Notes
Partial functions and partially applied functions are not related, except the names are almost the same. I was confused about this when I started to research this post.
The call to partially applied functions returns immediately. Curried functions return another function in the currying chain.
Labels:
functional programming,
scala