From Imperative to Functional: how to make the leap | Hacker News Reader

From Imperative to Functional: how to make the leap

loup-vaillant.fr

45 pointsloup-vaillant30 comments

Hi L-V,

I'm a C programmer, and I've gone through the article a couple times without enlightenment. This isn't necessarily the fault of the article, but thought I'd offer the places I couldn't follow. Perhaps they will be useful for understanding a beginners viewpoint.

  *int square(int n)    │    square :: Int -> Int*

Would be great if you offered an example where the argument and return type differed. As is, I don't know which order the Haskell declaration uses.

  Now it is possible to write the Haskell program that will
  naturally read from left to write

If this is essential at this point, it should be fleshed out more. Otherwise it feels like a distracting aside and out of place in a short introduction.

  -- before                        │    -- after
  compute n = baz (bar (foo n))    │    wiz     n = bar (foo n)
                                   │    compute n = baz (wiz n)

This seems perfectly clear, which makes me suspect the other parts are intended to be simple as well.

  (.) :: (b -> c) -> (a -> b) -> (a -> c)

Not clear why the left side is (.). Is this because it's non-alpha? Because it's infix? Something else? Order to read right hand side still unclear. Also don't know if reuse of a, b, and c as variables is significant.

  g . f = λx -> g (f x)

Can't quite follow, but this might be because I'm not sure if the λ is syntactically important, or just a naming convention.

  be expressed literally (see 1 vs λx -> g (f x));

I can't figure out what this means, possibly because I'm not sure what 'literally' means in this context. Also wasn't clear at first that "1" was meant as a number (or is that an 'L'), not a footnote or reference.

                       -- A List is either
  data List a = Empty  -- an empty node,  
  | Cons a (List a)    -- or a cons cell

Would help to define a "cons cell". Is Cons a data type or a function here? Is there a standard for capitalization? Not clear to me how the 'a' on the left side relates to the two on the right. Is 'data' a keyword, a type, or something else?

  inc-all l = map (λe -> e + 1) l

Throughout this whole section, I had no idea which characters were one's and which were L's. I ended up cutting and pasting into emacs and capitalizing. Perhaps something other than 'l' for the placeholder variable? Or it is more than a placeholder? The concept seemed straightforward, but the example was very hard to figure out.

  It is not obvious from the syntax, but Haskell functions      
  only have one argument.

Would help to mention this before the (.) example.

  Multiple arguments are emulated by returning functions.

So I guess this means the argument is on the left of the first '->' and the return type is to the right? And how should '->' be pronounced when spoken?

  inc-all (Cons e l) = Cons (foo e + 1) (inc-all l)

I'm guessing 'e' is 'element', and lower-case 'L' is list. Why/when did we switch from 'a' in the definition of List? And where did 'foo' come from? Is this a builtin function? A user defined function?

  map (a -> b) -> List a -> list b

Is the lower case for the last 'list' important? For that matter, is case important at all in Haskell? Also, are the types on the left for 'a' and 'b' defined by the given types on the right? Also haven't figured out why this declaration(?) has no '::' as the others do.

  dbl-all (Cons e l) = Cons (foo e * e) (inc-all l)

Is that supposed be 'dbl-all' at the end? And should that be "2 * e" instead of "e * e"? I'm hoping these are typos, otherwise I'm understanding even less than I thought.

  Note that the first argument is a function, hence the (a -> b) between parentheses.

Great! Confirmation on how to read the function declarations. Now back to reread the first half of the article again. Hopefully this means the return type is after the last '->'?

  Very simple, but without the fundamentals I just gave, 
  one hardly stands a chance at deciphering it.

Unfortunately, I still don't feel confident in my ability to decipher now that I have have the been given those fundamentals. I think a gloss of what 'λe' actually means would help. As a type, is it parallel to "void * (* e)( void * )" in C?

Despite this long list, I appreciate that you wrote the article. Much better to have something possibly flawed than nothing at all. Maybe one day I'll actually understand it!

That article was more about declarative/functional programming than about the details of the Haskell syntax.

Types are capitalized. Lower-case types in signatures are placeholders in polymorphic functions. The signature

    (.) :: (b -> c) -> (a -> b) -> (a -> c)

means: The function that is the . takes a first argument (g) that maps some type b to some type c. The second argument (f) maps some type a to the type b. This ensures that you can always do g(f(x)). The result of the function . is a function that maps the type a (what f takes) to type c (what g returns).

The type signature only deals with types; this is not connected to the names of the function parameters.

Lambda expressions are written without types; they can be inferred (i.e. the return type is not void* , but exactly determined by the compiler). A lambda expression in lambda calculus notation would be written "λx.(+ x 1)". Haskell slightly modifies this, and allows infix operators: "\x -> x + 1"(the \ looks a bit like λ). Punctuation functions are infix by default.

About the data expression: This constructs a new type (typedef). The "|" operator is just used in a declarative fashion. Every time you write Empty in your source code, that thing is a list. The expression "list = Cons foo Empty" would create a list of one element (foo). A cons cell is a pair, this terminology is popular in Lisp. These confusing data type constructors allow pattern matching, as you have seen in the definition of "map": If the list is Empty, return Empty. If the list is a Cons of an element and another list, then return a Cons of (result of our function applied to that element) and (the rest of the list mapped) – recursion.

That is one of the most enlightening criticisms I have ever read. Thank you. I'll try and fix my post tonight.

Now, about your questions…

  float foo(int);

translates to

  foo :: Int -> Float

Now there's still a slight difference: in C, the prototype can be used as a forward declaration. The Haskell equivalent is merely a type restriction. Here it says "dear compiler, whatever you may think about that 'foo' thing, I'm telling you this is a function from integers to floating points.

Oh, and type names are capitalized in Haskell. "list" was a typo.

Now,

  (.) :: (b -> c) -> (a -> b) -> (a -> c)

reads in a similar way. On the left side of '::', we have an identifier (which here happens to be an infix operator, hence the surrounding parentheses). On the right side of '::', we have the type we wish to declare (which here is a bit complicated).

  g . f = λx -> g (f x)

I'm just defining a new value here. The left side of '=' tells us we define the dot operator (which is a function with two arguments), and the right hand side is just the body of the function.

  λx -> blah_blah

is a functional value. 'λ' and '->' are the syntax constructs. 'x' is the parameter, and 'blah_blah is the body. This code reads "the function which produces 'blah_blah' from 'x'". I call this a "literal" function, or a functional literal, because it is analogous to integer literals

and string literals:

"Hello World"

(Oh and in Haskell, we actually use '\', not 'λ'.)

A cons cell is just a place where you store two values. Here this particular cons cell contains an element, and a pointer to the rest of the list. I reckon I was going way too fast on that one.

In type declarations, the arrow is right associative. So,

  foo :: a -> b -> c

is the same as

  foo :: a -> (b -> c)

You can think of it as a functions with two arguments, or as a function with one arguments, which returns a function with the remaining argument.

  map (a -> b) -> List a -> list b

Lacks the '::' because I forgot to write it. Good catch. Likewise 'dbl_all' is a typo, it should be 'square_all' or something.

First, if you are interested in Haskell, check out Learn You a Haskell For Great Good (http://learnyouahaskell.com/). I can not recommend it highly enough for actually understanding Haskell. I will try to answer your queries, but I think you may understand it better if you just flick through the chapter on Higher Order Functions.

> Would be great if you offered an example where the argument and return type differed. As is, I don't know which order the Haskell declaration uses.

In Haskell, the last (rightmost) type is the return type. eg. countLetters :: String -> Int means it takes an argument of type String and returns an argument of type Int. Also, types are chained together so for example, foobar :: String -> Int -> Bool is a function that takes two arguments, the first being a String, the second an Int and it returns a Bool and foobarbaz :: String -> Int -> Bool -> Char is a function that takes three arguments, the first a String, the second an Int, the third a Bool and it returns a Char. This syntax makes a lot of sense when exploiting "higher-order functions" and "currying". I mention this only to provide keywords for your personal search.

> If this is essential at this point, it should be fleshed out more. Otherwise it feels like a distracting aside and out of place in a short introduction.

In my view this is an aside.

> Not clear why the left side is (.). Is this because it's non-alpha? Because it's infix? Something else? Order to read right hand side still unclear. Also don't know if reuse of a, b, and c as variables is significant.

To write a function whose name starts with a punctuation character, Haskell syntax demands that it is wrapped by brackets and I think its automatically infix. You can use any function infix by wrapping it in ` eg. x `f` y is the same as f x y which means (f x) y which means apply the function f to the argument x, and then to the argument y.

'a', 'b' and 'c' are type variables, similar to type variables in Java and C# when dealing with generics. They can stand for any type. So, 'a' could be String or Char or Bool or any other type. As could 'b' and 'c'. So 'a' may or may not be the same type as 'b' or 'c'.

I'm not sure I can make it any clearer but note the signature of (.) has two arguments and a single return type. The first argument is (b -> c) which means it is a function that takes a single argument 'b' and returns a value of type 'c'. So the first argument of (.) is a function. The second argument is (a -> b) which is also a function. Its return type is also a function.

Personally I think (.) is a very hard function to grok and certainly far too complex for the first higher order function you see, exponentially so if you're still trying to understand Haskell syntax.

> Would help to define a "cons cell". Is Cons a data type or a function here? Is there a standard for capitalization? Not clear to me how the 'a' on the left side relates to the two on the right. Is 'data' a keyword, a type, or something else?

data is a keyword. Its how you define a data structure in Haskell. In this case, its defining a data structure called List which will wrap elements of type 'a'. In other words, 'List Int' is a type, 'List Bool' is a type, 'List Char' is a type. List is broadly the same as generic in Java or C# where List<String> is a type and List<Bool> is a different type. Cons is a data constructor (and yes, its standard to capitalise data contructors), which you can think of as being a function Cons :: a -> List a -> List a. It takes two arguments, an 'a' and a 'List a' and returns a 'List a'. Here the type variable 'a' does something as Haskell ensures that if the first argument is an Int, then the second must be a List Int and will return a List Int. If the first argument is a String however, then the second must be a List String and will return a List String.

> I think a gloss of what 'λe' actually means would help

λe means "create an anonymous function that takes an argument called e with any type". And (λe -> e + 1) is an anonymous function that adds one to every element passed to it.

Seriously, check out Learn You a Haskell.

"Your program isn't about what it does, but about what things are"

This is exactly backwards. OOP programming is about what things are. As Steve Yegge put it, functional programming is about verbs, about what your program does to the data passing through it.

Steve's original post, "Execution in the Kingdom of Nouns," is much clearer: http://steve-yegge.blogspot.com/2006/03/execution-in-kingdom...

"Your code isn't just a linear sequence of instructions, but a tree of nested expressions."

This is also off the mark. If you're working in a Lisp, sure, you're directly manipulating abstract syntax trees. But this is a mark of a homoiconic language, not a functional one.

"Functions are ordinary mathematical objects, just like an integer is."

Also wrong. In a functional language, functions are first-class objects, meaning they have an existence independent of classes. But they're something different from integers, which are usually defined as primitives in the language.

Verb vs nouns. Well, what are objects in OO? They're things that do this, and change that… This is a lot about what objects do, and what we do to them. On the other hand, in FP, one "does" only one thing: create new values. There is a lot of verbs in FP, but they don't do anything… Anyway, I guess I'll need to review that.

Instruction sequence vs Expression tree It's jot just Lisp. Ocaml and Haskell apply as well. We don't manipulate the syntax tree, but it doesn't mean it isn't there. For instance, the following is a valid Ocaml or Haskell expression:

  if condition
  then foo
  else bar (if condition2
            then baz
            else wiz)

This is not unusual code. Here is the C equivalent:

  condition
  ? foo
  : bar(condition2 ? baz : wiz)

This is a tree of nested expressions.

Functions as ordinary mathematical objects. I'm just saying that functions belong to the bucket of mathematical objects. As are integers. And sets. And lists… "First class" just mean we treat them as such. From https://en.wikipedia.org/wiki/First-class_function

> In languages with first-class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type.

"There is [sic] a lot of verbs in FP, but they don't do anything"

This is both misleading and false. Functions, by their very nature, "do something."

Perhaps you're referring to the immutability of data in a functional language? If so, say so.

"We don't manipulate the syntax tree, but it doesn't mean it isn't there."

A statement so ambiguous as to be meaningless. All compiled languages have a "syntax tree" lurking in the background. It just so happens that Lisp and its variants let you manipulate that tree directly, rather than writing in code that gets converted to that tree at compile time.

Perhaps you're referring to the fact that in Haskell, you often don't control the order in which code is executed, unlike in an imperative language where you have explicit control?

"...just saying that functions belong to the bucket of mathematical objects. As are integers. And sets."

Nope. The quote you use has it right. The names of functions are variables, whose value is looked up like any variable. This lets you pass functions as arguments to other functions, or use functions as the return value for other functions. Functions are most definitely not just like integers in a functional language.

I meant expression tree, sorry. I'm not referring to Haskell non-strict evaluation either. My point stands in Ocaml as well. But yeah, expressions do relinquish explicit control of the evaluation order, for it doesn't matter (assuming purity).

On the other points, let me remind you that a function is a subset of the Cartesian product between its domain and its co-domain. How does that do anything? How does that isn't as ordinary as a mere set? Really, the only reason we feel that functions do something is because we generally perform only one action with them: looking up the result, given a parameter.

I insist because this is precisely this special holy first class status that makes functions scary. Remember the primal fear you felt when your high school teacher told you that there is an operator that can compose functions together? Neither do I. But it did make clear at that point that functions aren't that special. If they were, how could I write "f∘g" just like I would "x+y"? How could I write "f" alone, without an "(x)" right next to it?

Functions do have their specificities, and they are special in the sense that they are a tremendously useful, wickedly powerful concept. But they're still mathematical objects. Making them first class in a programming language just lift restrictions that were there only because it was easier to implement.

I see. You're using function in its mathematical sense, not in terms of programming.

Perhaps the article would be clearer if you stated up front that you're trying to talk about the mathematical underpinnings of the functional programming paradigm, and not how imperative and functional programming languages differ in practice? From a practical programming standpoint, your characterization of functional programming is both incorrect and confusing.

"Your program isn't about what it does, but about what things are"

"In the Haskell code, the data flows from right to left, instead of from top to bottom"

I find this article vague, imprecise, forced. It's like those "lets do OOP for the sake of doing OOP" articles, just swap OOP to functional programming.

The statements you cite are trivial, but I believe they are quite precise. Can you tell me more about how my article spurs a feeling of vagueness? I might be able to fix it.

Also, I didn't mean to advocate FP, at least not there. I have written it for the poor C++/Java programmer who is forced to decipher an OCaml script written by a jerk who since left the company. (Disclaimer: I would be the jerk.)

> Can you tell me more about how my article spurs a feeling of vagueness?

Not just you, approx. 90% of the software industry suffers from it (big IMHO here of course). I think too much emphasis is placed on paradigms and magic approaches, instead of talking about things are.

Something like this:

"Is C++ a big pile of mess? Yes.

Is Haskell a much better designed language, even if its implementations are slower because the higher level of abstraction clashes with the underlying hardware currently in use? Yep."

Also, what you are trying to describe with all those top-bottom-left-right and similar analogies is the fact that in FP languages you mostly work with expressions, while the building blocks of imperative languages are statements.

I don't really have the time to continue here maybe I will write a blog post myself too :).

This article did it for me, it was originally written in 1989:

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pd...

We used to see these articles for object orientation. Now we see them for functional. I look forward with bated breath for the next paradigm!

Actually you could already start to see that with multi-paradigm languages.

I have a possible correction. Might dbl-all not be better named sqr-all? Thanks for the article by the way.

Good catch!

Why do you use 'λ' instead of '\'? Is this normal in haskell projects?

Either the author has a shiny new keyboard with a λ key, or they really really like to copy and paste.

Shiny new keyboard: http://bepo.fr/

Syntax error: Either data constructor not in scope.

Perhaps you meant one of these:

   Left "the author has a shiny new keyboard with a λ key"

   Right "they really really like to copy and paste"

Or a programmable text editor. I bind λ to S-l in emacs.

As far as I know, it isn't. I just figured that anyone who understand '\' might understand 'λ' as well. And those who don't know Haskell might just figure that 'λ' stands for 'function'.

But in that way your Haskell code examples seem to not be valid Haskell anymore. Seems to be a rather pointless change for the sake of simply breaking things.

Well, given this: http://news.ycombinator.com/item?id=5278883 I now believe the notation needs to be explained anyway. I'll switch back to '\'.

Lisp and Ruby, among other languages, actually use the word 'lambda' as a keyword for declaring an anonymous function. It's more typing than "\", but the intent is clear.

I don't think Haskell is really the best choice of language for demonstrating these FP concepts simply because Haskell's syntax is a little cryptic to those who haven't studied it. Lisp would have been a more readable choice since the syntax is trivial.

Also, you didn't touch on recursion, which is a key concept in FP. The idea of having a function call itself repeatedly in order to loop through a data structure, instead of iterating over the data structure by mutating a counter variable, is a huge paradigm shift for people who are new to FP.

Yes. But in practice we almost never recurse through a data structure directly. We once recursively define a combinator to fold the datastructure, and then always use that combinator for working with the data structure.

Again! I've been hearing the "switch to functional!" spiel since the 70s (being honest, since sometime in the 60s, but I digress)... stop it already! Hasn't happened in 40 years, won't happen now.

Dude, why are you so impatient?

It's not like everyone is going to switch, but some people--especially on HN--might, so it's definitely worth reading about. I certainly know some startups considering functional programming, largely because so many people seem to like it.

Also, if you look at other popular technology like OOP, they were pushed even harder than functional programming. When I was initially learning programming, I read a ton of books and articles all advocating it. Similarly, I've seen more people advocating Python than Haskell, and that worked too.

So maybe it's not enough by itself to make seething popular, but it seems necessary or at least very helpful. There's certainly no reason to stop trying!

Reply on news.ycombinator.com