26th Euler project in Haskell : "process stopped"

Question

I'm trying to solve the 26th Project Euler problem and I wrote something which compiles fine but when I launch it I get an error.

The program is:

module Main where

import Data.List (maximumBy, unfoldr)

liste :: Int -> [(Int,Int)]
liste i = unfoldr étape (1,i)
  where étape (n,m) = if mod (n*10) m == 0 
                      then Nothing 
                      else Just ((mod (n*10) m, div (n*10) m), (mod (n*10) m, i))

longueur :: Int -> Maybe Int
longueur i =
  let maxRecherche = 5000
      laListe = liste i
      assignAttribute :: Int -> Maybe Int
      assignAttribute j = if ((laListe !! j) == (laListe !! maxRecherche)) 
                          then Just (maxRecherche - j)
                          else if (j==1) then Nothing
                               else assignAttribute(j-1)
  in if (length laListe < maxRecherche)
     then Nothing
     else assignAttribute(maxRecherche-1) 
                          -- éléments comparés à maxRacherche, dv dc etre avant (a=a)
main :: IO()
main = do
  putStrLn "hello"
  let longueur370 = longueur 370
  putStrLn $ "370 : " ++ show longueur370
  let longueurs = Data.List.maximumBy tri $ map (\i -> (i,longueur i)) [1..1000]
  putStrLn $ "resultats : " ++ (show longueurs)
    where tri (_,Nothing)(_,Nothing) = EQ
          tri (_,Nothing)(_,_) = LT
          tri (_,_)(_,Nothing) = GT
          tri (_,Just u)(_,Just v) = compare u v

Here are some short explanations :

the function liste creates an infinite list of pairs, a pair containing (rest,digit) where rest and digit are the result of the computation of the i-th digit of 1/n (see the Project Euler for why I'm computing 1/n) this function seems to work well, as proved by the test with 370.
the function longueur extract the 5000 first pairs and try to find the length of any cycle. I assumed that the 5000th pair is contained in a possible cycle ie the cycle has already begun. Note that it's totally empiric but the 1/n to compute are limited to [1..1000], which is not very huge. Finally, all this is a little complicated by the fact that a list of pairs can stop if there is no cycle.

The error is given by the OS: after some minutes, I get the message "processus stopped"...

Edit

I found how to make it : I test if the list contains a given number of elements, by dropping this number of elements, and checking the list remaining is not null.

ErikR ErikR · Accepted Answer · 2015-11-14T13:32:37

Your problem is that liste 370 produces an infinite list, and you're trying to to take the length of it in longeur:

longeur i =
  let ...
      laliste = liste i
      ...
  in if (length laliste < maxRecherche)
       ...

Most likely the process terminates because it runs out of memory.

26th Euler project in Haskell : "process stopped"

Edit

1 Answers