How does function evaluation work in Haskell

Question

I felt my knowledge of functional programming was a bit lacking so I decided to look online and follow a tutorial to get better when I cam across this where it states on the first page

"Say you have an immutable list of numbers xs = [1,2,3,4,5,6,7,8] and a function doubleMe which multiplies every element by 2 and then returns a new list. If we wanted to multiply our list by 8 in an imperative language and did doubleMe(doubleMe(doubleMe(xs))), it would probably pass through the list once and make a copy and then return it. Then it would pass through the list another two times and return the result."

From my knowledge of functional programming this seems wrong, let me show you why:

doubleMe = (\x.* 2 x)

so

doubleMe doubleMe doubleMe xs

would beta reduce to:

(\x.* 2 x) doubleMe doubleMe xs ->beta
(* 2 doubleMe) doubleMe xs 
(* 2 (\x.* 2 x)) doubleMe xs ->eta
(\x.* 2 * 2 x) doubleMe  xs ->beta
(* 2 * 2 doubleMe)  xs
(* 2 * 2 (\x.* 2 x)) xs ->eta
(\x.* 2 * 2 * 2 x) xs ->beta
(* 2 * 2 * 2 xs) ->beta
(* 4 * 2 xs) -> beta
(* 8 xs)

which means the function is beta equivalent to (\x. * 8 x)

I was under the impression the Haskell compiler carried out this reduction prior to execution, meaning no, it wouldn't make 3 passes over the list like this tutorial suggested, it would only make one. Am I wrong? If so then why doesn't Haskell do this? Surely it would make large improvements to performance.

I think this kind of optimization is called "fusion" and the compiler will try to do it, but it is tricky in general and an ongoing area of research. stackoverflow.com/q/38905369/14955 — Thilo
Note that the quoted section says imperative language, so isn’t talking about what Haskell does there. That said, the LYAH snippet is confused—the distinction it’s describing has nothing to do with imperative versus functional programming languages and everything to do with strict vs lazy languages. In any case, your definition of doubleMe isn’t the one LYAH is describing, since your definition has type Num a => a -> a, but LYAH’s hypothetical function has type Num a => [a] -> [a]. — Alexis King
@Alexis King I see, so it does do the reduction I thought it did, it just doesn't go all the way to * 8, it does 2*2*2*x for each element carrying out 3 operations instead of one, and only doing one pass. (I'm a bit daft, should have paid more attention to the next paragraph). — James
You are confusing doubleMe doubleMe doubleMe xs with doubleMe (doubleMe (doubleMe xs)). — chepner

Maxpm Maxpm · Accepted Answer · 2018-10-21T02:18:22

I think you're just misreading that paragraph. It says (emphasis mine):

If we wanted to multiply our list by 8 in an imperative language and did doubleMe(doubleMe(doubleMe(xs))), it would probably pass through the list once and make a copy and then return it.

An imperative language is a language like C or Python. Not Haskell.

That same paragraph goes on to contrast that behavior with what a "lazy language" does:

In a lazy language ... it only does one pass through the list and only when you really need it. That way when you want something from a lazy language you can just take some initial data and efficiently transform and mend it so it resembles what you want at the end.

Which is closer to what you expect.

How does function evaluation work in Haskell

1 Answers