Список строительство в Haskell

Question

У меня есть следующие рекурсивная функция для проекта 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 

Только я не знаю, правильный синтаксис для построения списка на chain n так, чтобы он созидает список xs и затем возвращает длину xs, как только число появляется снова в списке xs и начинает цикл.

Как исправить мою функцию цепи, чтобы она работала?

Answer 1

Используйте вспомогательную функцию:

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 

Как вы можете видеть, вы были близки к тому, что вы хотели, но вы размыли вместе.

Для развлечения я бросил в точечные эквиваленты fac и sumFac.

Вот точка свободного определения, которое использует view pattern (но, увы, кажется щекотать #2395):

{-# LANGUAGE ViewPatterns #-} 

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

Answer 2

Dunno, если это так просто, но вы не указали, что хотите иметь голову и хвост вместо всего списка в параметрах.

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 

У меня нет decToList, поэтому я не тестировал, работает ли это или нет. Прохладная работа, хотя я многому научился этому.

Answer 3

Я думаю, что ваша функция «цепочки» очень смущена. Вам нужно переосмыслить это. Вы используете в нем значение «xs», которое, похоже, не в сфере видимости. Откуда берется «xs»? Предположительно, это должен быть аргумент.

Лучшим подходом было бы создание бесконечного списка чисел, сгенерированных этой проблемой, а затем обнаружение в нем петель. Вы можете получить бесконечный список для начального значения «n», используя

numberSequence n = iterate sumFac n 

Затем найдите циклы. Вы должны проверить каждый номер по всем предыдущим номерам. Простым, но неэффективным способом является создание списка по ходу, проверка каждого номера на текущий список и последующее добавление числа к списку в рекурсивном вызове. Более эффективным решением было бы использовать Data.Set.

Кстати, fac n = продукт [1..n]. Ваша версия работает, но ее необоснованно многословная. (На самом деле, если вы замените определение «product» и desugar «[1..n]», вы получите свою версию).