web developer & system programmer

coder . cl

ramblings and thoughts on programming...

collatz problem and haskell

published: 11-04-2012 / updated: 29-04-2012
posted in: development, haskell, programming
by Daniel Molina Wegener

The Collatz problem is Math problem related to a pair of operations which applied recursively will make a number reach 1 always. «The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers, or as wondrous numbers.»

Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called “Half Or Triple Plus One”, or HOTPO[4]) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness.

It was proposed as problem as part of the Project Euler and by Eduardo Díaz on his blog, I have implemented my solution in Haskell, because I want to enhance my skills with this language, to reach the most professional coding on it.

My first solution is as follows, is using recursion and if statements. Where if statements should be avoided, also the colmax function can be reduced and eliminated.

module Main (main) where

import System.Environment

collatz :: Int -> [Int] -> [Int]
collatz 1 xs = xs ++ [1]
collatz n xs = if even n
                  then collatz (n `div` 2) $ xs ++ [n]
               else collatz (n * 3 + 1) $ xs ++ [n]

colmax :: [Int] -> Int -> Int -> Int
colmax [] _ m = m
colmax (x:xs) n m = let r = length $ collatz x []
                        in if r > n
                              then colmax xs r x
                           else colmax xs n m

main :: IO ()
main = do [x] <- getArgs
          print $ colmax [1..(read x)] 0 0

My second solution uses the Haskell features to avoid if statements and some reductions to allow more concise code, mainly due to the lazyness of used functions.

module Main (main) where

import System.Environment
import Data.List
import Data.Ord
import Data.Function

collatz :: Int -> [Int] -> [Int]
collatz n xs | n == 1 = xs ++ [1]
             | even n = collatz (n `div` 2) $ xs ++ [n]
             | otherwise = collatz (n * 3 + 1) $ xs ++ [n]

main :: IO ()
main = do [x] <- getArgs
          print $ fst $ maximumBy (comparing length `on` snd)
            $ fmap (\ x -> (x, collatz x []) ) [1..(read x)]

This code looks really well, and seems to be more clear to understand, mainly due to the inline pointfree lambda expression comparing length `on` snd. So, the code is easy to understand and clear enough. Without if statements and using guards rather than if.

one comment to “collatz problem and haskell”

  1. [...] Haskell, con 2 respuestas, aunque la segunda es la que implementa el requerimiento, Daniel incluso escribió un post en su blog e investigó un poco más sobre este problema. A la solución correcta de Daniel la llamaremos [...]

post a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>