Tail recursion recognition

Question

I am trying to learn Haskell, and I came across the following:

myAdd (x:xs) = x + myAdd xs myAdd null = 0 f = let n = 10000000 in myAdd [1 .. n] main = do putStrLn (show f) 

When compiling with GHC, this leads to a stack overflow. As a C / C ++ programmer, I expected the compiler to perform tail call optimization.

I don't like that I have to “help” the compiler in simple cases like these, but what options exist? I think it is reasonable to require that the above calculation be done without using O (n) memory and without delaying specialized functions.

If I cannot formulate my problem naturally (even on a toy problem such as this), and expect reasonable performance in terms of time and space, most of Haskell's appeal will be lost.

Answer 1

First, make sure you compile -O2 . This leads to serious performance issues :)

The first problem I see is that null is just a variable name. You want [] . This is equivalent here because the only parameters are x:xs and [] , but it will not always be.

The problem here is simple: when you call sum [1,2,3,4] , it looks like this:

 1 + (2 + (3 + (4 + 0))) 

without reducing any of these additions to a number, due to Haskell's lax semantics. The solution is simple:

 myAdd = myAdd' 0 where myAdd' !total [] = total myAdd' !total (x:xs) = myAdd' (total + x) xs 

(To compile this file, you will need {-# LANGUAGE BangPatterns #-} at the top of the source file.)

This accumulates the addition in another parameter and is actually tail recursive (yours is not, + is in the tail position, not myAdd ). But actually this is not exactly tail recursion, which we care about at Haskell; this distinction mainly refers to strict languages. The secret here is the explosion pattern on total : it forces it to be evaluated every time myAdd' is myAdd' , so no unvalued add-ons are created, and it works in a constant space. In this case, the GHC can actually figure this out with -O2 due to its rigor analysis, but I think it is usually best to clearly state that you want strict and what you are not doing.

Please note that if the addition was lazy, the definition of myAdd will work fine; the problem is that you are doing lazy traversal of the list with a strict operation that ultimately causes a stack overflow. This is mainly due to arithmetic, which is a string for standard numeric types (Int, Integer, Float, Double, etc.).

This is pretty ugly, and it would be painful to write something like this every time we want to write a strict warehouse. Fortunately, Haskell has an abstraction ready for it!

 myAdd = foldl' (+) 0 

(To compile this, you need to add import Data.List .)

foldl' (+) 0 [a, b, c, d] similar to (((0 + a) + b) + c) + d , except that for each application (+) (as we call the binary operator + as a function value) the value is forcibly evaluated. The resulting code is cleaner, faster, and easier to read (as soon as you know how lists are dumped, you can understand any definition written in terms of them easier than a recursive definition).

The main problem here is not that the compiler cannot figure out how to make your program effective - it makes it as efficient as you like, it can change its semantics, which optimization should never do. Haskell’s lax semantics certainly represent a learning curve for programmers in more “traditional” languages ​​such as C, but it gets easier over time, and once you see the power and abstraction that Haskell’s rigor does not offer, you will never want to go back: )

Answer 2

Extension of the example pointed out in the comments:

 data Peano = Z | S Peano deriving (Eq, Show) instance Ord Peano where compare (S a) (S b) = compare ab compare ZZ = EQ compare Z _ = LT compare _ _ = GT instance Num Peano where Z + n = n (S a) + n = S (a + n) -- omit others fromInteger 0 = Z fromInteger n | n < 0 = error "Peano: fromInteger requires non-negative argument" | otherwise = S (fromInteger (n-1)) instance Enum Peano where succ = S pred (S a) = a pred _ = error "Peano: no predecessor" toEnum n | n < 0 = error "toEnum: invalid argument" | otherwise = fromInteger (toInteger n) fromEnum Z = 0 fromEnum (S a) = 1 + fromEnum a enumFrom = iterate S enumFromTo ab = takeWhile (<= b) $ enumFrom a -- omit others infinity :: Peano infinity = S infinity result :: Bool result = 3 < myAdd [1 .. infinity] 

result is True by the definition of myAdd , but if the compiler is converted to a tail-recursive loop, it will not end. Thus, conversion is not only a change in efficiency, but also semantics, so the compiler should not do this.

Answer 3

A little funny example: "The problem is why the compiler cannot optimize something that seems pretty simple to optimize."

Say I'm going from Haskell to C ++. I wrote foldr because in Haskell, foldr usually more efficient than foldl because of laziness and merging lists.

So, I am trying to write foldr for a (singly connected) list in C and complain why it is very inefficient:

 int foldr(int (*f)(int, node*), int base, node * list) { return list == NULL ? base : f(a, foldr(f, base, list->next)); } 

This is inefficient, not because the C compiler in question is an unrealistic toy tool developed by the ivory tower theorists for their own satisfaction, but because this code is roughly non-idiomatic for C.

You can't write efficient foldr in C: you just need a double list. In Haskell, you can write efficient foldl same way; you need strictness annotations for foldl be effective. The standard library provides both foldl (without annotations) and foldl' (with annotations).

The idea of ​​left-handed list folding in Haskell is the same perversion as the desire to repeat a single list back using recursion in C. The compiler is for normal people, not lol perversions.

Since your C ++ projects probably don't have code repeating single lists back, my HNC project only contains 1 foldl , which I wrote incorrectly before I mastered Haskell enough. You are unlikely to ever need foldl in Haskell.

You must wean that advanced iteration is natural and fast, and find out that there is a reverse iteration. Perspective iteration (left bending) does not do what you intend until you annotate: it performs three passes - creating a list, building chains and analyzing tones, instead of two (creating a list and traversing the list). Note that in immutable world lists, you can only effectively create backlinks: a: b - O (1), and a ++ [b] - O (N).

And the reverse iteration does not do what you intend. It makes one pass instead of three, as you might expect against its background C. It does not create the list, crosses it from below, and then crosses it back (2 passes) - it crosses the list as it is created, i.e. 1 pass. When using optimizations, this is just a cycle - elements of the actual list are not created. Optimization disables the operation of O (1) with large fixed costs, but the explanation is slightly longer.

Answer 4

So, there are two things that I will talk about your problem: firstly, the performance problem, and then the second expressive problem is to help the compiler with something that seems trivial.

Performance

The fact is that your program is not really a recursive tail, that is, there is no single function call that can replace recursion. Let's see what happens when we deploy myAdd [1..3] :

 myAdd [1,2,3] 1 + myAdd [2,3] 1 + 2 + myAdd [3] 

As you can see, at any given step we cannot replace recursion with a function call, we could simplify the expression by reducing 1 + 2 to 3, but this is not what the tail recursion has.

So here is a version that is tail recursive:

 myAdd2 = go 0 where go a [] = a go a (x:xs) = go (a + x) xs 

Let's see how go 0 [1,2,3] is evaluated go 0 [1,2,3] :

 go 0 [1,2,3] go (1+0) [2,3] go (2 + 1 + 0) [3] 

As you can see, at each step we only need to track one function call, and as soon as the first parameter is strictly evaluated, we should not get the exponential space to explode, and in fact, if you compile with the optimization ( -O1 or -O2 ) ghc is enough smart to figure it out on your own.

expressiveness

Well, it's a little harder to talk about performance in haskell, but most of the time you don't need it. The fact is that you can use combinators that provide efficiency. This particular template above is captured by foldl (and its strict cousin foldl' ), so myAdd can be written as:

 myAdd = foldl (+) 0 

and if you compile it with optimization, it will not give you exponential blurring of space!