Hailstones and the Collatz Conjecture

The Collatz Conjecture is related to a type of problem called a Hailstone problem; because hailstones circulate up and down through a cloud around a planet until they eventually fall. The Collatz conjecture posits that for the function

$$
f(n) = \begin{cases} \text{even: } & n/2\\ \text{odd: } & 3n+1\end{cases}
$$

the sequence \$n, f(n), f(f(n)), \cdots, f^i(n), \cdots\$ will eventually arrive at the value 1.

The following example code, which calculates the sum of all even members of the sequence obtained for a given starting value \$n\$, is given as part of an exercise, but I'm looking to improve it. By improving it, I mean: shorten via composition; via mapping; via folding; or any other more powerful and better practice.

foo :: Integer -> Integer
foo 1 = 0
foo n 
  | even n    = n + foo (n `div` 2)
  | otherwise = foo (3 * n + 1)

Here's what I got. I'm using point-free style with composition in foo'. However, I'm not so sure how to improve f.

foo' :: Integer -> Integer
foo' = (sum . f)

f :: Integer -> [Integer]
f x 
 | x == 1    = []
 | even x    = x : f (x `div` 2)
 | otherwise = f (3*x + 1)

Please critique this improvement.

Every piece of code should have a clear purpose. If you need to conduct some maintenance on a piece of code, you obtain its description first. You consult users, manuals, previous developers as needed.

I assume this code is bug-free and it's doing some calculation on some hailstone numbers.

First of all, you extracting the implicit sequence is an improvement on the original, provided we know we are dealing with a sequence.

Further improvements

That only even numbers are included in the sum is not part of the Collatz Problem. By moving the condition we can rename the unnamed sequence as hailstones. Also f is not a good name for a sequence, as f and g usually denote parameters which are functions.

foo' :: Integer -> Integer
foo' = sum . filter even . hailstones -- removed unnecessary parentheses

hailstones :: Integer -> [Integer]
hailstones x 
 | x == 1    = []
 | even x    = x : hailstones (x `div` 2)
 | otherwise = x : hailstones (3 * x + 1) -- space around *

Stopping condition is not part of the original Collatz problem, either. Hailstone sequences do not stop at 1, but rather go \$ \cdots, 1, 4, 2, 1, 4, 2, \cdots \$ forever.

foo' :: Integer -> Integer
foo' = sum . filter even . takeWhile (/= 1) . hailstones

hailstones :: Integer -> [Integer]
hailstones x 
 | even x    = x : hailstones (x `div` 2)
 | otherwise = x : hailstones (3 * x + 1)

Make the recursive nature of these sequences explicit:

collatzStep n
 | even n    = n `div` 2
 | otherwise = 3 * n + 1

hailstones x = x : collatzStep x

Last line can be written as hailstones = iterate collatzStep.

Altogether:

collatzStep n
 | even n    = n `div` 2
 | otherwise = 3 * n + 1

hailstones = iterate collatzStep

foo' = sum . filter even . takeWhile (/= 1) . hailstones

Now, of course if you were to hand this in as a homework, TAs or the professor would have asked you to add a lot of comments. First of all you do not tell them that "Comments are a code smell." Or describe what you did as KISS, DRY, readability etc.

Since this probably is a Programming Languages homework, you should add a comment mentioning that collatzStep is "lambda lifted", not "factored out"; that hailstones is an anamorphism and this, of course, makes foo an hylomorphism (correct the greek, and add more of it as necessary desired).

StackExchange Code Review Q#63734, answer score: 4