Iterating a function and analysing the result in haskell

Question

Ok, referring back to my previous question, I am still working on learning haskell and solving the current problem of finding the longest chain from the following iteration:

 chain n    | n == 0     = error "What are you on about?"
     | n == 1    = [1]
     | rem n 2 == 0 = n : chain (n `div` 2) 
     | otherwise    = n : chain (3 * n + 1)

I have this bit sorted, but I need to find the longest chain from a starting number below 1,000,000. So how do I make it do each starting number up to 1,000,000 and then print the one with the longest chain length. I can do it for one example with:

Main> length (chain n)

I assume I need the output as an array and then use the maximum function to find the value largest chain length and then see how far along it is in the array of answers.

Is this a good way to go about finding a solution or is there a better way (perhaps with better efficiency)?

Answer 1

You are right about the maximum part. To get the list (that's what Haskell's []s are, arrays are different structures) you need to use the map higher-order function, like this:

chainLength n = length (chain n)

lengths = map chainLength [1..1000000]

Essentially, map takes as arguments a function and a list. It applies the function to each element in the list and returns the list of the results.

Since you will be needing the number whose chain has that length, you may want change the chainLength function to return the number as well, like this:

chainLength n = (n, length (chain n))

That way you will have an array of pairs, with each number and its chain length.

Now you need to get the pair with the largest second component. That's where the maximumBy function comes in. It works just like maximum but takes a function as a parameter to select how to compare the values. In this case, the second component of the pair. This comparison function takes two numbers and returns a value of type Ordering. This type has only three possible values: LT, EQ, GT, for less than, equal, and greater than, respectively.

So, we need a function that given two pairs tells us how the second components compare to each other:

compareSnd (_, y1) (_, y2) = compare y1 y2
-- Or, if you import Data.Function, you can write it like this (thanks alexey_r):
compareSnd = compare `on` snd                  -- reads nicely

I used the default compare function that compares numbers (well, not just numbers).

Now we only need to get the maximum using this function:

longestChain = maximumBy compareSnd lengths

That gets you a pair of the number with the longest chain and the corresponding length. Feel free to apply fst and snd as you please.

Note that this could be more much more concisely using zip and composition, but since you tagged the question as newbie, I thought it better to break it down like this.

Answer 2

Something like

fst $ maximumBy (length . snd) $ zip [1..1000000] $ map chain [1..1000000]

(untested)

i.e. don't work out how far along the longest chain is in the list of longest chains, but carry around the seed values with the chains instead.

Answer 3

SPOILER (solving the problem for positive integers under 100):

module Test where
import Data.List   -- this contains maximumBy

chain n
        | n == 0       = error "What are you on about?"
        | n == 1       = [1]
        | rem n 2 == 0 = n : chain (n `div` 2) 
        | otherwise    = n : chain (3 * n + 1)

chains = map (\x -> (x,chain x)) [1..100]

cmpSnd (a,b) (c,d)
       | length b > length d     = GT
       | length b == length d    = EQ
       | otherwise               = LT

solve = (fst . maximumBy cmpSnd) chains

The chains function makes use of map. It applies a function to every element of a list of a values, so

map succ [1,2]

is the same as

[succ 1,succ 2]

The cmpSnd function is a comparison function that probably exists somewhere deep in the Hierarchical Libraries, but I could not find it, so I created it. GT means "the first value is greater than the second", the rest is trivial.

Solve takes the maximum (by utilizing the comparison function we defined earlier) of the list. This will be a pair of an integer and a list. It will return the integer only (because of the fst).

A comment: Your chain function is not tail-recursive. This means that large chains will inevitably result in a Stack Overflow. You shall add an explicit accumulator variable and make it tail-recursive.

Answer 4

I studied Haskell years ago, so I don't remember it that well. On the other hand I've tested this code and it works. You will get the max chain and the number that generates it. But as fiships has stated before, it will overflow for big values.

chain :: Int -> [Int]
chain n
    | n == 0 = []
    | n == 1 = [1]
    | rem n 2 == 0 = n : chain (n `div` 2) 
    | otherwise = n : chain (3 * n + 1)

length_chain :: Int -> Int
length_chain n = length (chain n)

max_pos :: (Int,Int) -> Int -> [Int] -> (Int,Int)
max_pos (m,p) _ [] = (m,p)
max_pos (m,p) a (x:xs)
    | x > m = max_pos (x,a) (a+1) xs
    | otherwise = max_pos (m,p) (a+1) xs

The instruction will be

Main> max_pos (0,0) 1 (map length_chain [1..10000])
(262,6171)