Or other special guests
Oct 29, 2009 at 8:45PM
The unfoldr function is a "dual" to foldr: while foldr reduces a list to a summary value, unfoldr builds a list from a seed value. For example:
iterate f == unfoldr (\x -> Just (x, f x))
In some cases, unfoldr can undo a foldr operation:
unfoldr f' (foldr f z xs) == xs
if the following holds:
f' (f x y) = Just (x,y)
f' z = Nothing
Oct 15, 2009 at 6:11PM
I can only show you the door, you have to walk through it.
The great programming languages singularity
It is interesting to see the "effects" of this video and the interesting discussions it generates. In particular it is fascinating to see people sharpening their understanding of what functional programming entails.
Just as I like to eat as wide an variety of food as possible (for instance I drink three different kinds of tea at a time), I like to program in and learn about as many different languages as possible. For a while I was literelly collecting every language definition I could lay my hands on. So, I am not taking any sides in this context, and neither am I reflecting the official Microsoft position on this topic. I am making some personal observations, pointing out the fundamental assumptions behind each possible interpretation of what functional programming means, thereby hopefully offering Channel 9 viewers the opportunity to learn and increase their understanding of the field of programming languages and type systems.
According to Graham Hutton (http://www.cs.nott.ac.uk/~gmh/book.html) functional programming is defined as: Broadly speaking, functional programming is a style of programming in which the basic method of computation is the application of functions to arguments. There are at least two ways to interpret this broad definition. First of all you can consider functional programming as a particular style of programming that values compositionality. The second way is to concentrate on the mathematical definition of function, which implies purity. In order to bring clarity is often good to look at both sides of the coin and just like in coding, to really understand something you need to explore the edges of an idea. This is what Seth Godin (http://sethgodin.typepad.com/)%20calls">http://sethgodin.typepad.com/) calls looking for the "purple cow", or the "free prize inside". I just love coins, both heads and tails.
The Haskell interpretation of functional programming is programming with pure mathematical functions. The free prize inside Haskell is the observation that you can deal with effects by making all effects explicit in the type system and distinguishing pure values from side-effecting computations of values via monads. These computations are themselves values that can be combined using pure functions, which allows programmers to define their own "control structures". This is why Simon Peyton Jones calls Haskell the world's best imperative language (http://research.microsoft.com/~simonpj/papers/marktoberdorf/). Another way of looking at this is that Haskell enables Landin's "the next 700 programming languages" http://www.cs.utah.edu/~eeide/compilers/old/papers/p157-landin.pdf where you define a domain specific imperative sublanguage of effects (a monad plus non-proper morphisms) and glue together effectful computations using pure functions.
In Haskell, the type-system keeps track of effects. However, as anyone that has programmed in Haskell has experienced, this purity comes at a high price. As soon as one sub-expression has an effect, every expression that depends on that expression has a potential effect as well, and the monadness percolates all the way up.
The underlying glue language in Haskell is based on three principles abstraction, (b) parameterization, and (c) correspondence (http://people.cis.ksu.edu/~schmidt/text/info.html), which brings us to the functional programming style. In normal words adhering to the functional programming style means allowing programmers to create closures of everything.
The purple cow in languages that use the functional programming style without insisting on absolute purity such as Lisp, Scheme, ML, OCaml, F#, Erlang, Scala, Algol68, Python, Ruby, Smalltalk, C#, Visual Basic, Java, .. is that the compositional style allows for very concise programs, even in the presence of effects. As a "terminology purist", I like to refer to languages that embrace the functional style as “closure oriented” programming. Note that it is no coincidence that there is really just one major pure functional language and many more pragmatic closure-oriented languages.
This pragmatism is invaluable in practice. It is much easier to deal with reality if you are pragmatic. For example, if you write a compiler in F#, you can generate fresh identifiers and still use a nice functional style whereas in Haskell the fact that generating a fresh name is a side effect, you are forced to switch to a monadic style forcing the programming to explicitly order all effects. One of the problems is that Haskell lumps all effects together, so it is not possible to distinguish between "benign" effects that are commutative or idempotent, … and real "bad" effects.
While closure-oriented languages make certain effects implicit (such as evaluation, state, exception, threads, events) that leaves many other effects that need to be dealt with explicitly, for example non-determinism (the IEnumerable monad). So we increasingly see that languages that use the functional programming style also factor out certain effects explicitly and provide a monadic sublanguage for creating effectful computations. Query comprehensions in C# and VB directly correspond to monad comprehensions in Haskell and are applicable way beyond just queries.
F# in particular is a noteworthy language since in F# this trend of making effects explicit is used extremely effectively (pun intended) and elegantly. For example it is advantageous to make events explicit (http://blogs.msdn.com/dsyme/archive/2006/03/24/559582.aspx), or asynchronous workflows (http://blogs.msdn.com/dsyme/archive/2007/10/11/introducing-f-asynchronous-workflows.aspx), or computation expressions (http://blogs.msdn.com/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx), or query expressions (http://research.microsoft.com/fsharp/manual/lexyacc.aspx#Comprehensions). As I have said before, I am especially excited and proud that Microsoft has decided to productize F# (http://www.apress.com/book/view/1590598504).
What is really great to see is that the pragmatic languages were influenced by Haskell, but created much more powerful comprehensions than Haskell to deal with real world problems, which in turn has influenced Haskell to incorporate some of these innovations back into Haskell l(http://homepages.inf.ed.ac.uk/wadler/topics/links.html#list-comp). This is a truly beautiful programming language singularity (http://flakenstein.net/lib/flake-singularity.pdf).
These are great times for language designers and programmers alike!
Erik Meijer aka Head In The Box