# The most important thing you can know about Haskell and Functional Programming

The Haskell equations `f x y = ...`

used in the definition
of a function `f`

are genuine mathematical equations. They
state that the left hand side of the right hand side of the equation
have the same value. This is *very* different from the use of
`=`

in imperative languages like C or Java. In a C or Java
program the statement `x = x*y`

does *not mean* that
`x`

and `x*y`

have the same value, but rather it
is a command to throw away the old value of `x`

and put the
value of `x*y`

in its place. It is a so-called
*destructive assignment statement:* the old value of a variable
is destroyed and replaced by a new one.

Reasoning about Haskell definitions is a lot easier than reasoning
about programs that use destructive assignment. In Haskell, standard
reasoning about mathematical equations applies. E.g. after the Haskell
declarations `x= 1`

and `y = 2`

, the Haskell
declaration `x = x + y`

will raise an error ```
"x"
multiply defined
```

. **... = in Haskell has
the meaning "is by definition equal to"...**

This was a huge landslide victory for me. Because I quit trying to write programs to get data here, data there. Values here, values there. Instead, I simply began to rewrite the original function as a new definition.

I became so confident that I was able to write a program to return all the leaves of a tree. and here it is:

Looking back at "Algorithms in Haskell" by Rabhi and "Craft of FP" by Simon Thompson, they do both make this same statement, but somehow it never really hit me right.

- metaperl's blog
- Login to post comments

One of my favorite spiritual quotes is actual said by a number of people. I think it covers what I was frantically trying to do in imperative languages and what Haskell never does:

It seems more natural to me to define leaves in such a way that it is of type Tree a -> [a].

Then you can simple collect the leaves in a bottom-up fashion:

(Note that the use (++) of is actually quite expensive. One usually circumvents this by introducing a so-called accumulating parameter, very much like you did:

)

Why should ++ be expensive? I thought that a list was implemented internally as a lazy linked list, and I would have thought that ++ should be cheap, just like : is.

`xs ++ ys`

takes time proportional to the size of`xs`

, rendering the running time of a naive version of`leaves`

quadratic.++ is defined as (in module GHC.Base):

(++) :: [a] -> [a] -> [a]

(++) [] ys = ys

(++) (x:xs) ys = x : xs ++ ys

So it adds a constant overhead to the lazy evaluation of (:) in the first part of the combined list (i.e. the pattern match to decide between the two cases). Unless I'm misunderstanding something this is not proportional to the sizes of the lists in the concatentation.

Note that the two appearances of the cons constructor actually refer to different nodes here: you're rebuilding the first list. So, you evaluate and reconstruct every cons node in the first argument list. Clearly, this takes time proportional to the length of the first argument list. Admittedly, implementations, e.g. GHC, do offer some ad-hoc optimizations.

Perhaps, I'm not explaining this too clear. I'm sorry for that. However, although it has been a while for me, as far as I can remember, this stuff is convered in almost all beginner's tutorials on the language.

Consult, for instance, Section 8.3 of A Gentle Introduction to Haskell. Furthermore, the text book on algorithms in functional languages by Rabhi and LaPalme as well as Okasaki's standard work on Purely Functional Data Structures do a good job in explaining how to analyze the efficiency of functional programs.

Well, that's if you are using lists. Functional dequeues or something else could be better...