Continuing in my introduction to Functional Programming, here are some concepts I have encountered.
Tail Recursive Optimization
"Certain recursive calls can be replaced by iterations. When the last statement executed in a procedure body is a recursive call of the same procedure, the call is said to be tail recursive... We can speed up a program by replacing tail recursion by iteration. For a procedure without parameters, a tail-recursive call can be simply replaced by a jump to the beginning of the procedure."
- Compilers, Principles, Techniques and Tools - Aho, Sethi and Ullman
Options
There are no nulls in functional languages like ML. Instead, there is a type called option that is either
SOME x
or
NONE
In the Java library, TotallyLazy, Options are modelled by a superclass Option and subclasses None and Some.
Option defines a get method that returns some value x for Some, while the None throws an Exception. If given an Option and you don't know what it is, you can experiment like with methods getOrNull that don't throw exceptions even if your Option is a None.
Currying
Currying is a "closure idiom... it's a new way to deal with with conceptually multi-argument functions. It takes one argument and return a function that takes the next argument. It will still be able to use the first argument because it will be in the environment."
In ML it looks like this:
"Example:
val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x
val t1 = ((sorted3 7) 9) 11
Calling (sorted3 7) returns a closure with:
Calling that closure with 9 returns a closure with:
Calling that closure with 11 returns true"
- Prof Dan Grossman, Coursera.
Pattern Matching
Nothing to do with String pattern matching that you find in PERL and Java, this is about how which path to follow through some code is determined by the type of a certain object.
An example in ML looks like:
case all_except_option(s, substitutions) of
NONE => []
| SOME x => x
where either an empty list. [], or x is returned depending on the type of the Option (see above).
There is a reflective version in the TotallyLazy library here (and its test that may prove enlightening here). This will guide which code block is executed given the type to an argument. Ideally, you'd do this using normal polymorphism. But this utility proves very useful if you don't have control of the classes that determine what functionality is to be invoked - say they belong to somebody else's library.
Lazy Evaluation
"Lazy evaluation is a method of delaying expression evaluation which avoids multiple evaluation of the same expression. Thus, it combines the advantages of normal order and applicative order evaluation. With lazy evaluation, an expression is evaluated when its value is needed, that is, when it appears in the function position in a function application. However, after evaluation, all copies of that expression are updated with the new value."
- An Introduction to Functional Programming Through Lambda Calculus - Greg Michaelson
Tail Recursive Optimization
"Certain recursive calls can be replaced by iterations. When the last statement executed in a procedure body is a recursive call of the same procedure, the call is said to be tail recursive... We can speed up a program by replacing tail recursion by iteration. For a procedure without parameters, a tail-recursive call can be simply replaced by a jump to the beginning of the procedure."
- Compilers, Principles, Techniques and Tools - Aho, Sethi and Ullman
Options
There are no nulls in functional languages like ML. Instead, there is a type called option that is either
SOME x
or
NONE
In the Java library, TotallyLazy, Options are modelled by a superclass Option and subclasses None and Some.
Option defines a get method that returns some value x for Some, while the None throws an Exception. If given an Option and you don't know what it is, you can experiment like with methods getOrNull that don't throw exceptions even if your Option is a None.
Currying
Currying is a "closure idiom... it's a new way to deal with with conceptually multi-argument functions. It takes one argument and return a function that takes the next argument. It will still be able to use the first argument because it will be in the environment."
In ML it looks like this:
"Example:
val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x
val t1 = ((sorted3 7) 9) 11
Calling (sorted3 7) returns a closure with:
- Code fn y => fn z => z >= y andalso y >= x
- Environment maps x to 7
Calling that closure with 9 returns a closure with:
- Code fn z => z >= y andalso y >= x
- Environment maps x to 7, y to 9
Calling that closure with 11 returns true"
- Prof Dan Grossman, Coursera.
Pattern Matching
Nothing to do with String pattern matching that you find in PERL and Java, this is about how which path to follow through some code is determined by the type of a certain object.
An example in ML looks like:
case all_except_option(s, substitutions) of
NONE => []
| SOME x => x
where either an empty list. [], or x is returned depending on the type of the Option (see above).
There is a reflective version in the TotallyLazy library here (and its test that may prove enlightening here). This will guide which code block is executed given the type to an argument. Ideally, you'd do this using normal polymorphism. But this utility proves very useful if you don't have control of the classes that determine what functionality is to be invoked - say they belong to somebody else's library.
Lazy Evaluation
"Lazy evaluation is a method of delaying expression evaluation which avoids multiple evaluation of the same expression. Thus, it combines the advantages of normal order and applicative order evaluation. With lazy evaluation, an expression is evaluated when its value is needed, that is, when it appears in the function position in a function application. However, after evaluation, all copies of that expression are updated with the new value."
- An Introduction to Functional Programming Through Lambda Calculus - Greg Michaelson
No comments:
Post a Comment