1

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.

James
  • 1,259
  • 1
  • 10
  • 21
  • 4
    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. https://stackoverflow.com/q/38905369/14955 – Thilo Oct 21 '18 at 02:15
  • 1
    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 Oct 21 '18 at 02:17
  • @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 Oct 21 '18 at 02:22
  • @Thilo that's what I'm interested in, thank you! – James Oct 21 '18 at 02:26
  • Also note that `doubleMe` operates on lists, not single values, so its code is more complex than `\x -> 2*x`, and more likely something like `map (\x -> 2*x)`, where `map` is defined by recursion on lists. In general, it's not easy to optimize multiple calls to recursive functions away, albeit the compiler might recognize the well-known library function `map` and perform custom optimizations on that one. – chi Oct 21 '18 at 08:39
  • in Haskell, `doubleMe doubleMe doubleMe xs` is `doubleMe(doubleMe)(doubleMe)(xs)`. – Will Ness Oct 21 '18 at 10:04
  • Your beta reduction makes several invalid simplifications in order to reach your assumed conclusion. – chepner Oct 21 '18 at 13:36
  • 1
    You are confusing `doubleMe doubleMe doubleMe xs` with `doubleMe (doubleMe (doubleMe xs))`. – chepner Oct 21 '18 at 13:54

1 Answers1

4

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.

Maxpm
  • 24,113
  • 33
  • 111
  • 170
  • 1
    Yeah I think I did too, but it did leave me wondering if there was a way for haskell to reduce the function all the way down to (\x.* 8 x) rather than doing (\x. * 2 * 2 * 2 x) - which is three operations for each element. – James Oct 21 '18 at 02:24
  • This optimization should actually be quite easy for the compiler to do. – Alexey Romanov Oct 21 '18 at 06:55