List construction in Haskell

Question

Hi
I have the following recursive function for project euler question no. 74:

chain n | n `elem` xs = length xs
     | otherwise = (chain (sumFac n)) : xs
fac n = foldl (*) 1 $ enumFromTo 1 n
sumFac n = sum $ map fac $ decToList n

Except I don't know the correct syntax to construct a list on chain n so that it builds up a list of xs and then returns the length of xs once a number appears again in the list of xs and begins to loop.

How would I correct my chain function to make it work?

Answer 1

Dunno if it's this simple but you didn't specify that you wanted a head and a tail instead of the whole list in the params.

chain [n:xs] | n `elem` xs = length xs
             | otherwise = chain (sumFac n) : xs
fac n = foldl (*) 1 $ enumFromTo 1 n
sumFac n = sum $ map fac $ decToList n

I don't have decToList so I didn't test if this works or not. Cool job of it though, I learned a lot reading this.

Answer 2

I think your "chain" function is very confused. You need to rethink it. You use a value "xs" in it that does not seem to be in scope. Where does "xs" come from? Presumably it should be an argument.

A better approach would be to build up the infinite list of numbers generated by the problem, and then detect loops within it. You can get the infinite list for starting value "n" using

numberSequence n = iterate sumFac n

Then look for cycles. You have to check each number against all the preceeding numbers. A simple but inefficient way is to build up a list as you go, checking each number against the current list, and then prepending the number on to the list in a recursive call. A more efficient solution would be to use Data.Set.

By the way, fac n = product [1..n]. Your version works, but its unecessarily verbose. (Actually if you substitute the definition of "product" and desugar "[1..n]" you get your version).

Answer 3

Use a helper function:

chain n = go [n]
  where go xs | next `elem` xs = reverse $ next : xs
              | otherwise      = go (next:xs)
          where next = sumFac $ head xs

fac = product . enumFromTo 1

sumFac = sum . map fac . map digitToInt . show

As you can see, you were close to what you wanted, but you blurred the two together.

For fun, I tossed in point-free equivalents of fac and sumFac.

Here's a point-free definition that uses a view pattern (but, alas, seems to tickle #2395):

{-# LANGUAGE ViewPatterns #-}

chain = head . filter hasDup . tail . inits . iterate sumFac
  where hasDup (reverse -> (x:xs)) = x `elem` xs