## 5common list operations defined concisely

See also https://bintanvictor.wordpress.com/2012/05/06/functional-lang-basic-list-operations-python-stl-linq/

Among the languages (STL, Linq, java stream, javascript, perl), I feel python has a simple and clean set of list operations, but in this post I will use generic names for generic operations.

I believe all these operations treat original list as immutable, and produce a new “copy” as return value. STL has a few algorithms in this category.

Every operation is able to take a lambda as input. Alternatives to lambda — function references, functors, function pointers…. Collectively these are known as FirstClassFunctions. See https://bintanvictor.wordpress.com/2012/01/04/functional-programming-personal-observations-fmd/

Operation Filter — like grep, selects a subset of the original. Each item in the selected subset is unchanged.
** Operation FindAll — is a synonym of Filter.
** Operation Find — returns first item of the subset.

The above Filter-family operations are the simplest operations.

Operation Reduce — (as in MapReduce) is an _aggregation/accumulation_ operation, starting with an optional initial value. It aggregates a list into a single value.
** Operation Fold — is similar but without initial value

Operation Map (as in MapReduce) — creates a different (unlike Filter) object from each list item. Output list is same length as input list, unlike Filter. I also call this “decorator”

—–also-ran operations I wouldn’t rank as most common Functional programming operations:

Operation ForEach

Advertisements

higher order function ^ first class function

See also http://stackoverflow.com/questions/10141124/any-difference-between-first-class-function-and-high-order-function.

Higher Order Function — A “boss” function that takes in smaller worker functions. Usually these workers are “applied” on a sequence.

Simplest Example: Python filter()/reduce()/map()

First Class Function — Each function is treated like a regular object and passed in/out of HOF. Often implemented as lambda (or closure). Functor too [[Essential C++]] P127.

Why FirstClass? I think objects are the only first class thing in traditional languages.

Simplest Example: Python lambda
——————
Python has other HOF features. I guess decorator might be.

STL functors qualify as FCF. STL algorithms taking those functors qualify as HOF. For example,
for_each()
transform()
generate()
find_if()
copy_if()

C# Linq has many HOF functions like ForEach(), Aggregate() and many aggregate functions. Many other C# function take (unicast) delegate arguments.
C# lambda (and anonymous delegates) is the typical FCF.

first class functions, my educated guess

First Class Function as a concept is over-complicated for someone looking for simple concrete, non-abstract explanations. In the primary usage, we pass a FCF into a function. Callable parameter. Most tutorials would apply the FCF on a list/sequence/stream.

Lambda is the most common example of a callable parameter. Arguably the most useful example of FCF.

Command pattern is more sophisticated than FCF. Command often has state to hold configuration and additional payload.

* Delegate in c# is a more complete example, a well-integrated component of the language. In c#, Lambda is implemented using delegates
* most scripting languages have good support for callable parameters.
* Before java 8, an interface and an anon class are the only implementations in java
* C offers function pointers, as a primitive support of callable params.
* C++ offers functors esp. in STL
—-
I don’t want a language lawyer over the exact definition of “first class function” or FCF. I’m trying to get the essence of “first class function”. I think the basic distinctions are

1) a FCF can be passed in and out of other functions

To understand these features, we must understand the regular, non-first-class functions. In C (and perhaps earlier languages), a function (say, play()) is compiled into a sequence of machine code, which gets loaded into the “text section” of a process memory. Text section is a kind of memory so every chunk of code including play() gets an address. The address of our chunk (play()) is a so-called function pointer. In C, we can pass this pointer (to play()) into a routine, and inside the routine invoke play(). This is the most primitive fist-class function.

2) a FCF can be assigned to a variable, and passed around
3) a FCF Object must have an address

STL supports function pointers but encourages the more advanced functors. Java doesn’t support function ptr or functor and favors interface. A method can receive an argument of type IPlayer, and inside the routine, invoke myPlayer.play(thePiano). This is fundamentally different from first-class function. Java’s Method object is another thing to contrast with FCF.

Anyway, back to FCF. I feel FCF is more of a syntactical construct to ease and encourage certain style of coding. In comparison, the underlying implementation by compilers is less important. Most app developers do not need to care about the compiler implementation of FCF.

Functional lang – common list operations – python, STL, LINQ …

http://www.ibm.com/developerworks/java/library/j-ft2/index.html shows a fundamental Functional Programming technique — A) apply a pure function (possibly a closure[1]) on successive elements of a sequence, B) and then perform accumulation, filter/grep, reduce etc across the entire sequence. Here I described it as a 2-stepper but you do not have to feel this way.

Python offers various elements of this strategy — list comprehension, apply(), filter(), map(), reduce(),  … but are they used with pure functions?

FP favors immutable objects. Basically,

      tuples + list operations in (B) = a major component of FP

Sorry about the loose language… Mine is very different from the academic/textbook presentation of FP, but in terms of techniques, mine is not too far.

STL offers many similar operations to (B), esp. with the *_copy and *_if algorithms in http://bigblog.tanbin.com/2012/04/stl-algos-and-their-if-and-copy.html
– find if
– count if
– remove_copy
– replace_copy

[1] I feel a closure qualifies as a pure function even though the output depends on some data in the “environment”.

I’ll stick my neck out and say that STL iterator concept is a defining feature(?) of a sequence.

functional programming – personal observations #FMD

(( FP]%%projects —
– XSLT
– python – first-class functions, lambda, closure, reduce(), zip(), apply(), map()
– perl – first class functions, closures, sort(), map()
– FMD ))

I feel FP is another buzzword people like to attach liberally (loosely) to various languages and software “Modules” like classes, functions, APIs.

The strict definition of FP is non-trivial, but let’s look at some salient features — the handful of pillars beneath a sprawling complex. If you have a module (a piece of software) that shows any one of these features, you are often free to say it’s kinda FP.

* [t] side-effect-free, always-repeatable functions — for a given set of input values to a function, you get the same output from every invocation
* [t] stateless functions — I guess C functions without static or global variables are simple examples.
* stateless objects? — stateless objects implies immutable. Mutable always refers to some stateful objects. However, I feel strictly stateless object is impractical and useless.
(Q: good example of immutable but stateful? Try google)
* [t] everything immutable — if all objects in your module is immutable, then probably it’s FP

[t = important to multithreading]

Actually, definition of FP is less important than the FP best practices encouraged and embedded in the popular FP languages. If any defining feature of FP isn’t widely adopted, then it gradually loses relevance. Therefore I’d rather spend more time on the common denominators of FP languages than the strict definition.

http://www.ibm.com/developerworks/linux/library/l-prog/index.html?ca=drs- has a similar view.

From now on I’d use “math” to mean “math-like”.
——————
The only FP language I used is Functional Model Deployment (FMD). I confirmed with other FMD users — all objects are immutable but (to be of any use) definitely stateful. Every c++ non-static method becomes a math-function. Host instance i.e. ” *this ” becomes the first argument, and a new instance is returned, to preserve the immutability of original instance.

The truly defining feature is the eval (fn, values, labels) construct.
– value can be any object, like some street address
– label is just a string, like “address”
– fn is what I call an incomplete object. It looks like an object with (potentially complex) state, but when you view it, it is presented as a function — a math function — with at least one variable unbound. If that variable is named “address”, then the above eval() would provide the required variable binding, and transform that function into a complete object.

Each object is written as some math-expression, so it usually depends on some objects. There could be a very long (thousands of nodes) object graph behind an object. Just think of each object in the graph as a math expression, one feeding into the next.

If any upstream object has an unbound variable, then all downstream objects become incomplete objects i.e. math-functions.

list processing — across Functional languages

update — java 8 streams …
—-
I feel FP is an increasingly loose term. A lot of FP-like features are tagged with the FP label. That makes it harder to identify the core FP concepts and syntactical features. You may want to focus on the top 3 “topics” one at a time[1], so let’s start with the #1 — Sequence processing using first class functions — qualifies as the #1 most practical (and identifiable) hallmark of functional programming. Widely used in real world business logic implementations.

In perl, Sequence processing is a fundamental concept and designed into the language core from Day 1.

Python has the most natural Sequence processing. Look at
* list comprehension,
* map() grep() reduce() apply() zip()

STL algorithms and iterators are all about Sequence processing. The data processing logic is often passed in as standard STL functors.

C# linq — all about Sequence processing

Java has fewer identifiable features for Sequence processing, but look at JVM dynamic languages. See
http://www.ibm.com/developerworks/java/library/j-ft1/

–Huskell (new to me)–
Sequence and Functions are the two major building blocks of any Haskell program. (http://en.wikibooks.org/wiki/Haskell/Lists_and_tuples)
fold — like python reduce(). See http://en.wikipedia.org/wiki/Fold_(higher-order_function)
filter — like python filter(), perl grep()
list comprehension — like python

[1] What are some of the other major topics? Here are some of my picks
* functors — functions as first-class objects. Remember in traditional languages functions (including methods) are never objects and objects are never functions
* side effects, repeatability and immutability, like math functions — this is probably where the name “functional” originated

meta programming — personal reflections

I’m no expert on meta programming. I feel MP is an over-popularized buzzword, with increasingly vague and expanding scope. I’m less interested in what buzzwords are part of MP, and more interested in the very few “pillars” beneath this sprawling complex —

– reflection/introspection
** first-class functions — all functions as first-class objects

– run-time byte-code engineering
– dynamic creation and manipulation of program modules
– nested (often anonymous) code modules[1] such as nested functions/classes — nested in Functions. I feel this is basically “dynamic creation”

– More generally, any compile-time task performed at run time (by your clever hack) is subversive, powerful, dangerous and usually part of meta programming.
** I feel one of the earliest use cases is C++ template meta programming. What used to be a compile-time task — creating similar vector classes for int, float, Dog — is now performed at run time.
** another Simple example in Java reflection — removing “private” access modifier at run time.

Reflection is richer in Python than compiled languages. All functions, methods, types … are first-class objects you can look into at run-time.

Perl offers “subref” and closures, too.

[1] beyond data structure