[newbie] getting the longest list from a list of lists

[newbie] getting the longest list from a list of lists

Post by klapote » Sat, 06 Nov 2010 09:38:55


I'm just working through http://www.yqcomputer.com/
nice, and wanted to expand on one of the examples in the chapter on
higher order functions when I hit a snag.

The example is:

chain :: (Integral a) => a -> [a]
chain 1 = [1]
chain n
| even n = n:chain (n `div` 2)
| odd n = n:chain (n*3 + 1)

numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
where isLong xs = length xs > 15

which gets me a list of numbers (a 'chain') for examining
http://www.yqcomputer.com/
such chains of at least a given length there are in a range. So far so
good.

I then wanted to know how long the longest chain in a given range
would be. Hey, no problem.

longestChainLength :: Int -> Int
longestChainLength x = maximum (map length (map chain [1..x]))

is what I came up with, and though it does take some time for x >
100000 (recursion takes its toll), it works, and I understand what it
does.

But how do I get not the length of the longest chain, but the actual
longest chain?
Probably just haven't been exposed to Haskell long enough, but I can't
seem to get my head around a solution - any pointers appreciated.

-- Christopher
 
 
 

[newbie] getting the longest list from a list of lists

Post by Nobod » Sat, 06 Nov 2010 15:00:46


Data.List.maximumBy:

maximumBy :: (a -> a -> Ordering) -> [a] -> a

in conjunction with Data.Ord.comparing:

comparing :: Ord a => (b -> a) -> b -> b -> Ordering

gives:

longestChainLength = maximumBy (comparing length)